提供一种预处理后支持在线回答询问的做法。

转化一下条件：$i$ 能看到 $j$ 仅当 $(\max\limits_{k=i+1}^{j-1} h_k) \lt h_j$。
考虑对于每个 $j$，我们求出最大的 $i$ 满足 $i \lt j$ 且 $h_i \gt h_j$，此时 $i$ 能看到 $j$。
这可以用单调栈求解左边第一个比它大的元素下标，记为 $pre_j$，于是有一个性质：$i \in [pre_j, j)$ 的元素都可以看到 $j$。

那么对于一个询问 $l,r$，我们需要统计 $j \in (r,n]$ 有多少个 $pre_j \leq l$。
这是一个二维数点的形式，显然可以直接用可持久化线段树维护这个东西。

综上，预处理倒着枚举 $r$ 并单点加，查询就是某个历史版本的前缀和。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 15;
int n, m, tot = 0;
struct Tree {
    int lt, rt;
    int sum;
} tr[N << 5];

void change(int &u, int v, int l, int r, int d) {
    u = ++tot;
    tr[u].lt = tr[v].lt, tr[u].rt = tr[v].rt;
    tr[u].sum = tr[v].sum + 1;
    if (l == r) return;
    int mid = l + r >> 1;
    if (d <= mid) change(tr[u].lt, tr[v].lt, l, mid, d);
    else change(tr[u].rt, tr[v].rt, mid + 1, r, d);
}
int query(int u, int l, int r, int ql, int qr) {
    if (r < ql || l > qr) return 0;
    if (l >= ql && r <= qr) return tr[u].sum;
    int mid = l + r >> 1, res = 0;
    if (ql <= mid) res += query(tr[u].lt, l, mid, ql, qr);
    if (qr > mid) res += query(tr[u].rt, mid + 1, r, ql, qr);
    return res;
}

int a[N], pre[N];
int stk[N], top = 0;
int root[N];
void init() {
    for (int i = 1; i <= n; i++) {
        while (top && a[stk[top]] < a[i]) top--;
        pre[i] = stk[top];
        stk[++top] = i;
    }
    root[n + 1] = 0;
    for (int i = n; i >= 1; i--)
        change(root[i], root[i + 1], 0, n, pre[i]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    init();
    // for (int i = 1; i <= n; i++) cout << pre[i] << ' '; puts("");
    while (m--) {
        int l, r; scanf("%d%d", &l, &r);
        printf("%d\n", query(root[r + 1], 0, n, 0, l));
    }
    return 0;
}