Dynamic Rankings（动态第k大+树套树）

#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL; #define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("D://code//in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0) const double eps = 1e-;
const int mod = ;
const int maxn = 5e4 + ;
const double pi = acos(-);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL; char op[];
int n, q, x, y, tot1, tot2, cnt;
int a[maxn], q1[maxn], q2[maxn], root1[maxn], root2[maxn];
vector<int> v; struct que {
int op, l, r, x;
}ask[maxn]; struct node {
int l, r, sum;
}tree[maxn*]; int getid(int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + ;
} void update(int l, int r, int& x, int y, int pos, int val) {
tree[++cnt] = tree[y], tree[cnt].sum += val, x = cnt;
if(l == r) return;
int mid = (l + r) >> ;
if(pos <= mid) update(l, mid, tree[x].l, tree[y].l, pos, val);
else update(mid + , r, tree[x].r, tree[y].r, pos, val);
} int query(int l, int r, int x, int y, int k) {
if(l == r) return l;
int cnt = tree[tree[y].l].sum - tree[tree[x].l].sum;
for(int i = ; i < tot1; ++i) {
cnt -= tree[tree[q1[i]].l].sum;
}
for(int i = ; i < tot2; ++i) {
cnt += tree[tree[q2[i]].l].sum;
}
int mid = (l + r) >> ;
if(cnt >= k) {
for(int i = ; i < tot1; ++i) {
q1[i] = tree[q1[i]].l;
}
for(int i = ; i < tot2; ++i) {
q2[i] = tree[q2[i]].l;
}
return query(l, mid, tree[x].l, tree[y].l, k);
} else {
for(int i = ; i < tot1; ++i) {
q1[i] = tree[q1[i]].r;
}
for(int i = ; i < tot2; ++i) {
q2[i] = tree[q2[i]].r;
}
return query(mid + , r, tree[x].r, tree[y].r, k - cnt);
}
} int main(){
#ifndef ONLINE_JUDGE
FIN;
#endif
int t;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &q);
cnt = tot1 = tot2 = ;
v.clear();
memset(root2, , sizeof(root2));
for(int i = ; i <= n; ++i) {
scanf("%d", &a[i]);
v.push_back(a[i]);
}
for(int i = ; i <= q; ++i) {
scanf("%s", op);
if(op[] == 'C') ask[i].op = ;
else ask[i].op = ;
if(ask[i].op == ) {
scanf("%d%d", &ask[i].l, &ask[i].x);
v.push_back(ask[i].x);
} else {
scanf("%d%d%d", &ask[i].l, &ask[i].r, &ask[i].x);
}
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
int sz = v.size();
for(int i = ; i <= n; ++i) {
a[i] = getid(a[i]);
update(, sz, root1[i], root1[i-], a[i], );
}
for(int i = ; i <= q; ++i) {
int op = ask[i].op;
if(op == ) {
int pos = ask[i].l, x = ask[i].x, y = a[pos];
x = getid(x);
a[pos] = x;
while(pos <= n) {
update(, sz, root2[pos], root2[pos], y, -);
update(, sz, root2[pos], root2[pos], x, );
pos += lowbit(pos);
}
} else {
int l = ask[i].l, r = ask[i].r, k = ask[i].x;
int x = l - ;
tot1 = tot2 = ;
while(x) {
q1[tot1++] = root2[x];
x -= lowbit(x);
}
x = r;
while(x) {
q2[tot2++] = root2[x];
x -= lowbit(x);
}
printf("%d\n", v[query(, sz, root1[l-], root1[r], k)-]);
}
}
}
return ;
}