题解：
修改=删除+插入。
具体实现时保证先删除后插入。
就是对于某一位状态为插入->删除->插入->删除->……->插入。
而不是插入->插入->删除->……->插入->删除。
不然这个无脑错误会让普通线段树挂掉的。
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 100050 inline int rd() { int f=1,c=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();} return f*c; } int n,m,tot,cnt,vl[N],to[3*N],mx,ans[N],qcnt; char ch[2]; struct node { int opt;//0 in 1 out 2 query int l,r,k; int x,id; }p[3*N],tmpl[3*N],tmpr[3*N]; struct Pair { int x,id; Pair(){} Pair(int x,int i):x(x),id(i){} }ar[3*N]; bool cmp(Pair p1,Pair p2) { return p1.x<p2.x; } struct segtree { int siz[N*12],vl[N*12],tag[N*12]; bool rec[N*12]; void add(int u,int d) { tag[u]+=d; vl[u]+=d*siz[u]; } void rece(int u) { vl[u]=tag[u] = 0; rec[u] = 1; } void pushdown(int u) { if(rec[u]) { rece(u<<1); rece(u<<1|1); rec[u] = 0; } if(tag[u]) { add(u<<1,tag[u]); add(u<<1|1,tag[u]); tag[u]=0; } } void update(int u) { vl[u] = vl[u<<1]+vl[u<<1|1]; } void build(int l,int r,int u) { siz[u] = r-l+1; if(l==r)return ; int mid = (l+r)>>1; build(l,mid,u<<1); build(mid+1,r,u<<1|1); } void insert(int l,int r,int u,int qx,int d) { if(l==r) { add(u,d); return ; } pushdown(u); int mid = (l+r)>>1; if(qx<=mid)insert(l,mid,u<<1,qx,d); else insert(mid+1,r,u<<1|1,qx,d); update(u); } int query(int l,int r,int u,int ql,int qr) { if(l==ql&&r==qr)return vl[u]; pushdown(u); int mid = (l+r)>>1; if(qr<=mid)return query(l,mid,u<<1,ql,qr); else if(ql>mid)return query(mid+1,r,u<<1|1,ql,qr); else return query(l,mid,u<<1,ql,mid)+query(mid+1,r,u<<1|1,mid+1,qr); } }tr; void divi(int l,int r,int beg,int ens) { if(beg>ens)return ; if(l==r) { for(int i=beg;i<=ens;i++) if(p[i].opt==2)ans[p[i].id] = to[l]; return ; } int mid = (l+r)>>1; int lt = 0,rt = 0; bool l1=0,r1=0; tr.rece(1); for(int i=beg;i<=ens;i++) { if(!p[i].opt) { if(p[i].x<=mid) { tr.insert(1,mx,1,p[i].id,1); tmpl[++lt] = p[i]; }else tmpr[++rt] = p[i]; }else if(p[i].opt==1) { if(p[i].x<=mid) { tr.insert(1,mx,1,p[i].id,-1); tmpl[++lt] = p[i]; }else tmpr[++rt] = p[i]; }else { int now = tr.query(1,mx,1,p[i].l,p[i].r); if(now<p[i].k) { p[i].k-=now; r1=1; tmpr[++rt] = p[i]; }else { l1=1; tmpl[++lt] = p[i]; } } } for(int i=beg;i<=beg+lt-1;i++)p[i] = tmpl[i-beg+1]; for(int i=beg+lt;i<=ens;i++)p[i] = tmpr[i-beg-lt+1]; if(l1)divi(l,mid,beg,beg+lt-1); if(r1)divi(mid+1,r,beg+lt,ens); } int main() { n = tot = rd(),m = rd(); for(int i=1;i<=n;i++) { p[i].x = vl[i] = rd(),p[i].id = i; ar[++cnt] = Pair(p[i].x,i); } for(int i=1;i<=m;i++) { scanf("%s",ch); if(ch[0]=='C') { tot++; p[tot].opt = 0; p[tot].id = rd(); p[tot].x = rd(); ar[++cnt] = Pair(p[tot].x,tot); tot++; p[tot].opt = 1; p[tot].id = p[tot-1].id; p[tot].x = vl[p[tot].id]; ar[++cnt] = Pair(p[tot].x,tot); vl[p[tot].id] = p[tot-1].x; }else { tot++; p[tot].opt = 2; p[tot].l = rd(); p[tot].r = rd(); p[tot].k = rd(); p[tot].id = ++qcnt; } } sort(ar+1,ar+1+cnt,cmp); for(int las=-1,i=1;i<=cnt;i++) { if(las!=ar[i].x) { las = ar[i].x; to[++mx] = las; } p[ar[i].id].x = mx; } tr.build(1,mx,1); divi(1,mx,1,tot); for(int i=1;i<=qcnt;i++) printf("%d ",ans[i]); return 0; }