把前缀和换成树状数组
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, a[10005], b[20005], rem, cnt, sum[2100005], lson[2100005], rson[2100005], rot[10005], cnt0, cnt1;//空间复杂度(n+q)log^2(n+q)
int lque[25], rque[25];
char ss[25];
struct Ques{
int uu, vv, ww;
bool isq;
}q[10005];
int lowbit(int x){
return x&-x;
}
void update(int &rt, int pre, int l, int r, int x, int val){
if(!rt) rt = ++cnt;
lson[rt] = lson[pre]; rson[rt] = rson[pre]; sum[rt] = sum[pre] + val;
if(l==r) return ;
int mid=(l+r)>>1;
if(x<=mid) update(lson[rt], lson[pre], l, mid, x, val);
if(mid<x) update(rson[rt], rson[pre], mid+1, r, x, val);
}
int query(int l, int r, int k){
if(l==r) return l;
int tmp=0;
for(int i=1; i<=cnt0; i++) tmp -= sum[lson[lque[i]]];
for(int i=1; i<=cnt1; i++) tmp += sum[lson[rque[i]]];
int mid=(l+r)>>1;
if(k<=tmp){
for(int i=1; i<=cnt0; i++) lque[i] = lson[lque[i]];
for(int i=1; i<=cnt1; i++) rque[i] = lson[rque[i]];
return query(l, mid, k);
}
else{
for(int i=1; i<=cnt0; i++) lque[i] = rson[lque[i]];
for(int i=1; i<=cnt1; i++) rque[i] = rson[rque[i]];
return query(mid+1, r, k-tmp);
}
}
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
b[++rem] = a[i];
}
for(int i=1; i<=m; i++){
scanf("%s", ss);
if(ss[0]=='Q'){
scanf("%d %d %d", &q[i].uu, &q[i].vv, &q[i].ww);
q[i].isq = true;
}
else{
scanf("%d %d", &q[i].uu, &q[i].ww);
q[i].isq = false;
b[++rem] = q[i].ww;
}
}
sort(b+1, b+1+rem);
rem = unique(b+1, b+1+rem) - (b + 1);
for(int i=1; i<=n; i++){
int tmp=lower_bound(b+1, b+1+rem, a[i])-b;
for(int j=i; j<=n; j+=lowbit(j)) update(rot[j], rot[j], 1, rem, tmp, 1);
}
for(int i=1; i<=m; i++){
if(q[i].isq){
cnt0 = cnt1 = 0;
for(int j=q[i].uu-1; j; j-=lowbit(j)) lque[++cnt0] = rot[j];
for(int j=q[i].vv; j; j-=lowbit(j)) rque[++cnt1] = rot[j];
printf("%d
", b[query(1, rem, q[i].ww)]);
}
else{
int tmp=lower_bound(b+1, b+1+rem, a[q[i].uu])-b;
for(int j=q[i].uu; j<=n; j+=lowbit(j)) update(rot[j], rot[j], 1, rem, tmp, -1);
a[q[i].uu] = q[i].ww;
tmp = lower_bound(b+1, b+1+rem, q[i].ww)-b;
for(int j=q[i].uu; j<=n; j+=lowbit(j)) update(rot[j], rot[j], 1, rem, tmp, 1);
}
}
return 0;
}