题目描述

难度分:$1370$

输入$n(1 \leq n \leq 2 \times 10^5)$、$q(1 \leq q \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。下标从$1$开始。然后输入$q$个询问，格式如下：

1. 1 p x：把$a[p]$改成$x(1 \leq x \leq 10^9)$。
2. 2 l r：输出$a$的子数组$[l,r]$中的严格次大值的个数。

注：严格次大值指不等于最大值的数中的最大值。

输入样例$1$

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

输出样例$1$

1
0
2

输入样例$2$

1 1
1000000000
2 1 1

输出样例$2$

0

输入样例$3$

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

输出样例$3$

0
1
0
2
4

算法

线段树

比较明显的一道数据结构题目，单点修改区间查询比较容易想到线段树。关键是每个节点要维护的信息，线段树的节点维护以下$5$个信息：

1. 区间左端点$l$；
2. 区间右端点$r$；
3. 区间最大值$y_1$；
4. 区间次大值$y_2$；
5. 区间最大值和次大值的频数表$counter$。

只需要实现左右孩子$lchild$和$rchild$的信息合并，显然$info.l=lchild.l$，$info.r=rchild.r$。把左右孩子的$counter$表拿出来融合，取出最大的两个值及其频数插入到$info.counter$中，并更新$info.y_1$和$info.y_2$（由于$lchild.counter$和$rchild.counter$两个表的大小最大就是$2$），所以这个操作是常数级别的，只是常数比较大。如果$info.counter$的大小$\lt 2$，说明区间$[l,r]$没有严格次大值，$y_2=0$。

复杂度分析

时间复杂度

建立线段树的时间复杂度为$O(nlog_2n)$；每个询问需要对线段树进行修改或查询操作，时间复杂度为$O(log_2n)$，$q$个询问的时间复杂度就是$O(qlog_2n)$。因此，整个算法的时间复杂度为$O((n+q)log_2n)$。

空间复杂度

除了输入的数组$a$，空间消耗的瓶颈就在于线段树。因此，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int n, q, a[N];

class SegmentTree {
public:
    struct Info {
        int l, r, y1, y2;
        unordered_map<int, int> counter;
        Info() {}
        Info(int left, int right, int val): l(left), r(right) {
            y1 = val;
            y2 = 0;
            counter[y1] = 1;
        }
    } seg[N<<2];

    explicit SegmentTree() {}

    void build(int u, int l, int r) {
        if(l == r) {
            seg[u] = Info(l, r, a[r]);
        }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;
        auto& lcnt = lchild.counter;
        auto& rcnt = rchild.counter;
        unordered_map<int, int> counter;
        for(auto&[num, freq]: lcnt) {
            counter[num] += freq;
        }
        for(auto&[num, freq]: rcnt) {
            counter[num] += freq;
        }
        vector<array<int, 2>> tup;
        for(auto&[num, freq]: counter) {
            tup.push_back({num, freq});
        }
        sort(tup.begin(), tup.end(), [&](auto&x, auto&y) {
            return x[0] > y[0];
        });
        int sz = tup.size();
        if(sz >= 2) {
            info.y1 = tup[0][0];
            info.y2 = tup[1][0];
            info.counter[info.y1] = tup[0][1];
            info.counter[info.y2] = tup[1][1];
        }else {
            info.y1 = tup[0][0];
            info.y2 = 0;
            info.counter[info.y1] = tup[0][1];
        }
        return info;
    }
};

int main() {
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    SegmentTree tr;
    tr.build(1, 1, n);
    while(q--) {
        int type;
        scanf("%d", &type);
        if(type == 1) {
            int p, x;
            scanf("%d%d", &p, &x);
            tr.modify(p, x);
        }else {
            int l, r;
            scanf("%d%d", &l, &r);
            auto info = tr.query(l, r);
            int y2 = info.y2;
            printf("%d\n", y2 == 0? y2: info.counter[y2]);
        }
    }
    return 0;
}