题目描述

难度分:$1659$

输入$n(2 \leq n \leq 2 \times 10^5)$，$q(1 \leq q \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq n)$，所有元素互不相同，下标从$1$开始。

然后输入$q$个询问，每个询问输入两个数$L$和$R(1 \leq L \leq R \leq n)$。

有$n$栋建筑物，第$i$栋建筑物的高度是$a[i]$。如果下标在$[i+1,j-1]$中的建筑物高度都$\leq a[j]$，那么在$i$能看到$j(i \lt j)$。

对于每个询问，输出：在$L$和$R$都能看到的、下标在$[R+1,n]$中的建筑物的数量。

输入样例$1$

5 3
2 1 4 3 5
1 2
3 5
1 4

输出样例$1$

2
0
1

输入样例$2$

10 10
2 1 5 3 4 6 9 8 7 10
3 9
2 5
4 8
5 6
3 8
2 10
7 8
6 7
8 10
4 10

输出样例$2$

1
3
1
2
1
0
1
1
0
0

算法

离线

整体思路是离线，但是用到了很多算法。先做一个简单的线性DP，$dp[i]$表示以$a[i]$开头的最长上升阶梯长度，即对于阶梯上的两个相邻的点$i \lt j$，$a[i] \lt a[j]$且$(i,j)$中没有比$a[j]$大的高度。也就是说，$a[j]$是$a[i]$右边第一个比它大的元素，可以用单调栈预处理出来，存入$R$数组中，有$R[i]=j$。这时候就可以$O(1)$进行状态转移了$dp[i]=dp[R[i]]+1$。

然后将所有的询问存入到一个有序表$v2pos$中，$key$为询问的右端点$r$，它的$value$为一个二元组数组，其中存的是（该询问对应的左端点$l$，询问编号$i$）。

接下来倒序遍历$v2pos$的键值对，对于一个给定的右端点$r$，把$i \gt r$的$a[i]$插入到一棵权值线段树中，线段树的索引为$a[i]$，索引对应的值为$i$，也就是说线段树存的信息是某个数值所在的索引位置。插入完成后就遍历$v2pos[r]$，二元组$(l,i)$对应的就是第$i$个询问$(l,r)$，此时$\gt i$的元素都已经被计入线段树。$(r,n]$中$l$和$r$都要能看到，则要满足条件：

1. $r$的右边最靠左，且满足高度$\gt mx=max_{i \in [l,r]}a[i]$，所以先求$max_{i \in [l,r]}a[i]$，可以通过预处理出一个维护区间最大值的$ST$表来做到$O(1)$查询。有了$mx$，在线段树的$(mx,n]$上查询最小坐标$pos$，当前询问$i$的答案就是$dp[pos]$。
2. 注意如果$mx=a[l]$，会有点特殊，此时要按照$mx=max_{i \in [l+1,r]}a[i]$去做查询。

复杂度分析

时间复杂度

预处理出$ST$表的时间复杂度为$O(nlog_2n)$；预处理出$R$数组需要用到单调栈，它的时间复杂度为$O(n)$；有了$R$数组后，进行线性DP，时间复杂度为$O(n)$（状态数量$O(n)$，单次转移$O(1)$）。线段树建树的时间复杂度为$O(nlog_2n)$；构建有序表$v2pos$时间复杂度为$O(qlog_2q)$。

遍历有序表$v2pos$中$O(q)$个询问计算答案的时间复杂度为$O(nlog_2n+q)$，包括遍历询问和插入$a[i]$到线段树中。但是处理单个询问时需要对线段树进行查询和修改操作，时间复杂度为$O(log_2n)$，整体的时间复杂度为$O((n+q)log_2n)$。

综上，整个算法的时间复杂度为$O(qlog_2q+(n+q)log_2n)$。

空间复杂度

R数组、DP数组、权值线段树的空间复杂度都为$O(n)$；映射表$v2pos$的空间复杂度为$O(q)$；$ST$的空间复杂度为$O(nlog_2n)$。整个算法的额外空间复杂度为$O(q+nlog_2n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;

const int N = 200010, M = 20;
int n, q, a[N], dp[N], R[N], ans[N], st[N][M];

int query(int l, int r) {
    int k = log2(r - l + 1);
    return max(st[l][k], st[r - (1<<k) + 1][k]);
}

class SegmentTree {
public:
    struct Info {
        int l, r, minimum;
        Info() {}
        Info(int left, int right, int val): l(left), r(right), minimum(val) {}
    } seg[N<<2];

    explicit SegmentTree() {}

    void build(int u, int l, int r) {
        if(l == r) {
            seg[u] = Info(l, r, n + 1);
        }else {
            int mid = l + r >> 1;
            build(u<<1, l, mid);
            build(u<<1|1, mid + 1, r);
            pushup(u);
        }
    }

    void modify(int pos, int val) {
        modify(1, pos, val);
    }

    Info query(int l, int r) {
        if(l > r) return Info(0, 0, 0);
        return query(1, l, r);
    }

private:
    void modify(int u, int pos, int val) {
        if(seg[u].l == pos && seg[u].r == pos) {
            seg[u] = Info(pos, pos, val);
        }else {
            int mid = seg[u].l + seg[u].r >> 1;
            if(pos <= mid) modify(u<<1, pos, val);
            else modify(u<<1|1, pos, val);
            pushup(u);
        }
    }

    Info query(int u, int l, int r) {
        if(l <= seg[u].l && seg[u].r <= r) return seg[u];
        int mid = seg[u].l + seg[u].r >> 1;
        if(r <= mid) {
            return query(u<<1, l, r);
        }else if(mid < l) {
            return query(u<<1|1, l, r);
        }else {
            return merge(query(u<<1, l, r), query(u<<1|1, l, r));
        }
    }

    void pushup(int u) {
        seg[u] = merge(seg[u<<1], seg[u<<1|1]);
    }

    Info merge(const Info& lchild, const Info& rchild) {
        Info info;
        info.l = lchild.l;
        info.r = rchild.r;
        info.minimum = min(lchild.minimum, rchild.minimum);
        return info;
    }
};

int main() {
    scanf("%d%d", &n, &q);
    dp[n + 1] = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        dp[i] = 1;
        R[i] = n + 1;
    }
    stack<int> stk;
    for(int i = 1; i <= n; i++) {
        while(stk.size() && a[stk.top()] < a[i]) {
            R[stk.top()] = i;
            stk.pop();
        }
        stk.push(i);
    }
    for(int i = n; i >= 1; i--) {
        dp[i] = dp[R[i]] + 1;
    }
    for(int j = 0; j < M; j++) {
        for(int i = 1; i + (1 << j) - 1 <= n; i++) {
            if(!j) {
                st[i][j] = a[i];
            }else {
                st[i][j] = max(st[i][j - 1], st[i + (1<<(j - 1))][j - 1]);
            }
        }
    }
    map<int, vector<PII>> mp;
    for(int i = 1; i <= q; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        mp[r].push_back({l, i});
    }
    SegmentTree v2pos;
    v2pos.build(1, 1, n);
    int i = n;
    for(auto it = mp.rbegin(); it != mp.rend(); it++) {
        int right = it->first;
        while(i > right) {
            v2pos.modify(a[i], i);
            i--;
        }
        for(auto&pir: it->second) {
            int left = pir.first, index = pir.second;
            // [left,right]上的最大值
            int mx = query(left, right);
            int pos = n + 1;
            if(a[left] > a[right]) {
                if(mx > a[left]) {
                    pos = v2pos.query(mx, n).minimum;
                }else {
                    pos = v2pos.query(query(left + 1, right), n).minimum;
                }
            }else {
                // a[left]<a[right]
                pos = v2pos.query(mx, n).minimum;
            }
            ans[index] = dp[pos];
        }
    }
    for(int i = 1; i <= q; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}