题目传送：P8701 [蓝桥杯 2019 国 B] 第八大奇迹 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这道题的关键在于“只查询第八大”这一特殊限制。因为查询目标固定，不需要维护整个有序信息，而只需要在每个区间里保留前八大的候选值即可。
思路#
第一反应当然可以是主席树，但这个题没必要把结构搞得那么重。
更直接的做法，是在线段树每个节点里维护当前区间的前八大值，pushup 时像归并排序那样合并两个有序数组。
代码#
#include<iostream>
using namespace std;
const int maxn = 1e5 + 10;
struct node {
int v[8] = {0};
} t[maxn << 2]; // 每个节点记录这个区间的前八大
inline void pushup(node &x, node &l, node &r) // 用归并排序思想合并
{
int p1 = 0, p2 = 0, p = 0;
while (p < 8 && p1 < 8 && p2 < 8)
if (l.v[p1] > r.v[p2]) x.v[p++] = l.v[p1++];
else x.v[p++] = r.v[p2++];
}
inline void modify(int x, int l, int r, int &dist, int &v) {
if (l == r) {
t[x].v[0] = v;
return;
}
int mid = l + r >> 1;
if (mid >= dist) modify(x << 1, l, mid, dist, v);
else modify(x << 1 | 1, mid + 1, r, dist, v);
pushup(t[x], t[x << 1], t[x << 1 | 1]);
}
inline node query(int x, int l, int r, int &L, int &R) {
if (l >= L && r <= R) return t[x];
int mid = l + r >> 1;
node t1, t2, ans;
if (mid >= L) t1 = query(x << 1, l, mid, L, R);
if (mid < R) t2 = query(x << 1 | 1, mid + 1, r, L, R);
pushup(ans, t1, t2);
return ans;
}
int l, n, x, y;
char op;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> l >> n;
while (n--) {
cin >> op >> x >> y;
if (op == 'C') modify(1, 1, l, x, y);
else cout << query(1, 1, l, x, y).v[7] << '\n';
}
return 0;
}