以前看到这题都瑟瑟发抖，终于过了心情舒畅。
按下标为关键字建替罪羊树，每个结点开一个权值线段树，维护的这个结点代表的子树的信息。
这题还得垃圾回收，自己yy的，不知对不对..
#include <cstdio> #include <algorithm> using namespace std; #define M ((L+R)>>1) #define l(x) t[x].s[0] #define r(x) t[x].s[1] #define L(x) t2[x].s[0] #define R(x) t2[x].s[1] const int N=70005; char op[2]; int n,x,y,z,q,rt,tt,t1,la,tp,tp2,V,st[N],st2[N],rb[N*30],rb2[N*256]; struct nd {int x,v,sz,s[2];}t[N*30],t2[N*256]; void dl(int x) {if(!x) return; rb2[++tt]=x,dl(L(x)),dl(R(x)),t2[x].x=L(x)=R(x)=0;} void upd(int &o,int L,int R,int x,int y) { if(!o) o=rb2[tt--]; t2[o].x+=y; if(L==R) return; if(x<=M) upd(L(o),L,M,x,y); else upd(R(o),M+1,R,x,y); if(!t2[o].x) dl(o),o=0; } void ge(int x) {if(!x) return; ge(l(x)),st[++tp]=x,ge(r(x));} void mr(int l,int r,int &x) { if(!l&&!r) return; t2[x=rb2[tt--]].x=t2[l].x+t2[r].x,mr(L(l),L(r),L(x)),mr(R(l),R(r),R(x)); } void bd(int &x,int L,int R) { if(L>R) return; t[x=rb[t1--]].v=t[st[M]].v; if(L==R) t[x].sz=1; else bd(l(x),L,M-1),bd(r(x),M+1,R),mr(t[l(x)].x,t[r(x)].x,t[x].x),t[x].sz=t[l(x)].sz+t[r(x)].sz+1; upd(t[x].x,1,N,t[x].v,1); } void rm() {for(int i=1;i<=tp;i++) dl(t[st[i]].x),l(st[i])=r(st[i])=t[st[i]].x=t[st[i]].v=t[st[i]].sz=0;} void ins(int &x,int p,int v) { if(!x) x=rb[t1--]; upd(t[x].x,1,N,v,1),t[x].sz++; if(!t[x].v) {t[x].v=v; return;} if(t[l(x)].sz+1>=p) ins(l(x),p,v); else ins(r(x),p-t[l(x)].sz-1,v); if(t[x].sz*0.75<max(t[l(x)].sz,t[r(x)].sz)) tp=0,ge(x),bd(x,1,tp),rm(); } void gt(int x,int l,int r) { if(r-l+1==t[x].sz) {st[++tp]=t[x].x; return;} if(l<=t[l(x)].sz) gt(l(x),l,min(r,t[l(x)].sz)); if(l<=t[l(x)].sz+1&&r>=t[l(x)].sz+1) st2[++tp2]=t[x].v; if(r>t[l(x)].sz+1) gt(r(x),max(l-t[l(x)].sz-1,1),r-t[l(x)].sz-1); } int dfs(int L,int R,int k) { if(L==R) return L; int s=0; for(int i=1;i<=tp;i++) s+=t2[L(st[i])].x; for(int i=1;i<=tp2;i++) if(st2[i]<=M&&st2[i]>=L) s++; if(s>=k) { for(int i=1;i<=tp;i++) st[i]=L(st[i]); return dfs(L,M,k); } else { for(int i=1;i<=tp;i++) st[i]=R(st[i]); return dfs(M+1,R,k-s); } } int qr(int l,int r,int k) {tp=tp2=0,gt(rt,l,r); return dfs(1,N,k);} void gai(int x,int p,int v) { if(t[l(x)].sz+1==p) V=t[x].v,t[x].v=v; else if(t[l(x)].sz>=p) gai(l(x),p,v); else gai(r(x),p-t[l(x)].sz-1,v); upd(t[x].x,1,N,v,1),upd(t[x].x,1,N,V,-1); } int main() { for(int i=1;i<N*30;i++) rb[i]=i; for(int i=1;i<N*256;i++) rb2[i]=i; scanf("%d",&n),tt=N*256-1,t1=N*30-1; for(int i=1;i<=n;i++) scanf("%d",&x),ins(rt,i,x+1); scanf("%d",&q); while(q--) { scanf("%s%d%d",op,&x,&y),x^=la,y^=la; if(op[0]=='Q') scanf("%d",&z),printf("%d ",la=qr(x,y,z^la)-1); else if(op[0]=='I') ins(rt,x,y+1); else gai(rt,x,y+1); } return 0; }