官方题解｜可变数组

题目解析

线段树；二分查找；

详情参考 ACL｜通用「线段树」模板

定义二元运算符 op 和单位元 e。

int op(int a, int b) {return std::max(a, b);};
int e() {return 0;};

使用数组 $A$，构建线段树，时间复杂度 $\mathrm{O}(N)$。

Segtree<int, op, e> sgt(a);

1. 对于赋值操作我们直接使用 sgt.set(int p, T x)，时间复杂度 $\mathrm{O}(\log{N})$。

2. 对于交换操作，和赋值操作类似，先使用 sgt.get(int p) 操作获取 $A_L$ 和 $A_R$ 的值，时间复杂度 $\mathrm{O}(1)$；然后再使用 sgt.set(int p, T x) 操作，时间复杂度 $\mathrm{O}(\log{N})$。

3. 查询区间最大值，使用 sgt.prod(l, r) 操作得出，时间复杂度 $\mathrm{O}(\log{N})$。

4. 在线段树上二分查找，使用 sgt.max_right(int l)，若返回值大于 $R$ 则输出 $-1$，否则输出答案。时间复杂度 $\mathrm{O}(\log{N})$。

总的时间复杂度 $\mathrm{O}(N + Q\log{N})$。

AC代码

#include <bits/stdc++.h>

/* Segtree.cpp */

int op(int a, int b) {return std::max(a, b);};
int e() {return 0;};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    Segtree<int, op, e> sgt(a);
    while (q--) {
        int t; std::cin >> t;
        if (t == 1) {
            int x, v;
            std::cin >> x >> v;
            sgt.set(x, v);
        }
        else if (t == 2) {
            int l, r;
            std::cin >> l >> r;
            int al = sgt.get(l), ar = sgt.get(r);
            sgt.set(l, ar);
            sgt.set(r, al);
        }
        else if (t == 3) {
            int l, r;
            std::cin >> l >> r;
            std::cout << sgt.prod(l, r + 1) << '\n';
        }
        else {
            int x, l, r;
            std::cin >> x >> l >> r;
            int p = sgt.max_right(l, [&](int v) {return v < x;});
            std::cout << (p <= r ? p : -1) << '\n';
        }
    }
    return 0;
}