题意
维护长度为 $n$ 的数组 $a$：
- 区间
chkmax - 撤销某次 1 操作
- 询问某点的值
$N = Q = 2 \times 10^5, 1 \leq A_i \leq 10^9$
题解
线段树上每个节点维护一个 multiset，每次 chkmax 就往 multiset 里加数，每次撤销即是删除数。每次查询操作则是查找根到该点路径上所有 multiset 中的最大值的最大值。
代码
来自 jiangly
#include <bits/stdc++.h>
using i64 = long long;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N;
std::cin >> N;
std::vector<int> A(N);
for (int i = 0; i < N; i++) {
std::cin >> A[i];
}
std::vector<std::multiset<int>> f(4 * N);
auto add = [&](auto self, int p, int l, int r, int x, int y, int v, int t = 1) {
if (l >= y || r <= x) {
return;
}
if (l >= x && r <= y) {
if (t == 1) {
f[p].insert(v);
} else {
f[p].extract(v);
}
return;
}
int m = (l + r) / 2;
self(self, 2 * p, l, m, x, y, v, t);
self(self, 2 * p + 1, m, r, x, y, v, t);
};
auto query = [&](auto self, int p, int l, int r, int x) {
int res = f[p].empty() ? 0 : *f[p].rbegin();
if (r - l == 1) {
return res;
}
int m = (l + r) / 2;
if (x < m) {
res = std::max(res, self(self, 2 * p, l, m, x));
} else {
res = std::max(res, self(self, 2 * p + 1, m, r, x));
}
return res;
};
for (int i = 0; i < N; i++) {
add(add, 1, 0, N, i, i + 1, A[i]);
}
int Q;
std::cin >> Q;
std::vector<int> op(Q), l(Q), r(Q), v(Q);
for (int i = 0; i < Q; i++) {
std::cin >> op[i];
if (op[i] == 1) {
std::cin >> l[i] >> r[i] >> v[i];
l[i]--;
add(add, 1, 0, N, l[i], r[i], v[i]);
} else if (op[i] == 2) {
int x;
std::cin >> x;
x--;
add(add, 1, 0, N, l[x], r[x], v[x], -1);
} else {
int x;
std::cin >> x;
x--;
std::cout << query(query, 1, 0, N, x) << "\n";
}
}
return 0;
}