---恢复内容开始---
题意:给出一个序列和操作次数, 每次操作修改一个位置的数 或者 询问一个区间第k小的数
分析:单点修改可以考虑线段树, 区间排名可以用平衡树 所以线段树+Treap
用一颗线段树将序列划分 每颗Treap中插入的是对应区间的数
在每个数加入时, 顺便将该数插入线段树中包含该位置的那些区间上的Treap即可
单点修改同理, 将所有包含要修改的位置的区间上的Treap都删去原数并插入新数
询问第k小的数：由于询问的区间不一定恰好对应某棵Treap, 不便直接求出名次,
但是能够直接求出询问区间中不大于某个数的数的个数, 则对于x, 若满足不大于x
的数有多于k个, 且不大于x-1的数少于k个, 就是原序列中第k小的数二分该数即可
#include<algorithm>
#include<cstring>
#include<cstdio>
const int maxn = 1000007;
int n, m, ret, arr[maxn];
char opt[3];
//...
int read() {
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
struct Treap {
int root[maxn], size, lc[maxn], rc[maxn], val[maxn], sz[maxn], cnt[maxn], rnd[maxn];
void init() {
memset(root, 0, sizeof(root));
size = 0;
}
void update(int k) {
sz[k] = sz[lc[k]] + sz[rc[k]] + cnt[k];
}
void l_rot(int &k) {
int t = rc[k]; rc[k] = lc[t]; lc[t] = k;
sz[t] = sz[k]; update(k); k = t;
}
void r_rot(int &k) {
int t = lc[k]; lc[k] = rc[t]; rc[t] = k;
sz[t] = sz[k]; update(k); k = t;
}
void insert(int &k, int x) {
if(k == 0) {
k = ++size;
lc[k] = rc[k] = 0;//这里写了初始化时就不用全部清零, 节省时间
sz[k] = cnt[k] = 1;
val[k] = x; rnd[k] = rand();
return;
}
sz[k]++;
if(x == val[k]) {cnt[k]++; return;}
if(x > val[k]) {
insert(rc[k], x);
if(rnd[rc[k]] < rnd[k]) l_rot(k);
} else {
insert(lc[k], x);
if(rnd[lc[k]] < rnd[k]) r_rot(k);
}
}
void del(int &k, int x) {
if(k == 0) return;
if(x == val[k]) {
if(cnt[k] > 1) {cnt[k]--; sz[k]--; return;}
if(lc[k] * rc[k] == 0) {k = lc[k] + rc[k]; return;}//考虑某个儿子为空则直接删除
if(rnd[lc[k]] < rnd[rc[k]]) r_rot(k), del(k, x);
else l_rot(k), del(k, x);
} else if(x < val[k]) sz[k]--, del(lc[k], x);
else sz[k]--, del(rc[k], x);
}
void RaNk(int k, int x) {//数x在以k为根的子树中小于等于x的数的数量(不同于求rank)
if(k == 0) return;
if(x >= val[k]) {
ret += sz[lc[k]] + cnt[k];//!!!
RaNk(rc[k], x);
} else RaNk(lc[k], x);
}
}Tr;
void Insert(int k, int l, int r, int x, int num) {
Tr.insert(Tr.root[k], num);
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) Insert(k << 1, l, mid, x, num);
else Insert(k << 1 | 1, mid + 1, r, x, num);
}
void Modify(int k, int l, int r, int x, int to) {
Tr.del(Tr.root[k], arr[x]);
Tr.insert(Tr.root[k], to);
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) Modify(k << 1, l, mid, x, to);
else Modify(k << 1 | 1, mid + 1, r, x, to);
}
void Query(int k, int l, int r, int s, int t, int num) {
if(l == s && t == r) {Tr.RaNk(Tr.root[k], num); return;}
int mid = (l + r) >> 1;
if(mid >= t) Query(k << 1, l, mid, s, t, num);
else if(mid < s) Query(k << 1 | 1, mid + 1, r, s, t, num);
else {
Query(k << 1, l, mid, s, mid, num);
Query(k << 1 | 1, mid + 1, r, mid + 1, t, num);
}
}
int main() {
int T, x, y, z; T = read();
while(T--) {
Tr.init(); n = read(); m = read();
for(int i = 1; i <= n; i++) {
arr[i] = read();
Insert(1, 1, n, i, arr[i]);
}
for(int i = 1; i <= m; i++) {
scanf("%s", opt);
if(opt[0] == 'C') {
x = read(); y = read();
Modify(1, 1, n, x, y);
arr[x] = y;//更新每次修改该位置时需在Treap中删去的数
} else {
x = read(); y = read(); z = read();
int l = 0, r = 1e9;
while(l <= r) {
int mid = (l + r) >> 1;
ret = 0; Query(1, 1, n, x, y, mid);
if(ret >= z) r = mid - 1;
else l = mid + 1;
}
printf("%d
", l);
}
}
}
return 0;
}
---恢复内容结束---