树套树写法。

程序应该是两值 Log 的。

求助大佬。

#include<bits/stdc++.h>
#define ls ch[p][0]
#define rs ch[p][1]
#define I inline
#define W while
#define RI register int
#define CI const int 
#define ll long long
#define DB double
#define rep(i,a,b) for(RI i=a;i<=b;++i)
#define dow(i,a,b) for(RI i=a;i>=b;--i)
#define edg(i,u,v) for(RI v,i=head[u];v=e[i].to,i;i=e[i].next)
using namespace std;
CI N=70005,V=70005,SZ=2e7+5;
const DB alpha=0.7;
int n,q,v[N];
char c[20];
struct SegMentTree{
	int ch[SZ][2],sum[SZ],top,st[SZ];
	I void init(CI p){ ls=rs=sum[p]=0; }
	I int NewNode(){ return init(st[top]),st[top--]; }
	I void ins(int &p,CI l,CI r,CI pos,CI v){
		if(!p) p=NewNode();sum[p]+=v;if(l==r) return;RI mid=l+r>>1;
		pos<=mid?ins(ls,l,mid,pos,v):ins(rs,mid+1,r,pos,v);
	}
	I void NewTree(int &x,CI pos){
		x=NewNode();++sum[x];RI l=0,r=70000,p=x;W(l<r){
			RI mid=l+r>>1;pos<=mid?p=ls=NewNode(),r=mid:
			(p=rs=NewNode(),l=mid+1),++sum[p];
		}
	}
	I void merge(int &x,CI y){
		if(!y) return;if(!x) x=NewNode();sum[x]+=sum[y];
		merge(ch[x][0],ch[y][0]),merge(ch[x][1],ch[y][1]);
	}
	I void clear(int &p){
		st[++top]=p;if(ls) clear(ls);if(rs) clear(rs);init(p),p=0;
	}
} Tree;
struct ScapgoatTree{
	int root,ch[N][2],st[N],top,rt[N],val[N],sz[N],valN;
	I void up(CI p){ sz[p]=sz[ls]+sz[rs]+1; }
	I int build(CI l,CI r){
		if(l>r)return 0;RI mid=l+r>>1,p=st[mid];Tree.NewTree(rt[p],v[p]);
		ls=build(l,mid-1),rs=build(mid+1,r),sz[p]=sz[ls]+sz[rs]+1;
		return Tree.merge(rt[p],rt[ls]),Tree.merge(rt[p],rt[rs]),p;
	}
	I void get(CI p){ if(ls)get(ls);st[++top]=p;if(rs) get(rs);}
	I void rebuild(int &p){
		top=0,get(p);rep(i,1,top) Tree.clear(rt[st[i]]),ch[st[i]][0]=ch[st[i]][1]=sz[st[i]]=0;
		p=build(1,top);return;
	}
	I void get(CI p,CI l,CI r,CI ql,CI qr){
		if(ql<=l&&r<=qr){ st[++top]=rt[p];return;}
		if(ls&&sz[ls]+l>ql) get(ls,l,l+sz[ls]-1,ql,qr);
		if(ql<=l+sz[ls]&&l+sz[ls]<=qr) val[++valN]=v[p];
		if(rs&&sz[ls]+l<qr) get(rs,l+sz[ls]+1,r,ql,qr);
	}
	I int query(CI l,CI r,int k){
		valN=top=0;get(root,1,n,l,r);RI L=0,R=70000;W(L<R){
			RI tot=0,mid=L+R>>1;rep(i,1,top)tot+=Tree.sum[Tree.ch[st[i]][0]];
			rep(i,1,valN) tot+=L<=val[i]&&val[i]<=mid;
			if(tot>=k){ R=mid;rep(i,1,top) st[i]=Tree.ch[st[i]][0]; }
			else{ k-=tot;L=mid+1;rep(i,1,top) st[i]=Tree.ch[st[i]][1]; }
		} return L;
	}
	I void get(CI p,CI k){
		st[++top]=p;if(sz[ls]>=k) get(ls,k);
		else if(sz[ls]+1==k)return;else get(rs,k-sz[ls]-1); }
	I void modify(CI p,CI val){
		top=0,get(root,p);rep(i,1,top)
			Tree.ins(rt[st[i]],0,70000,v[st[top]],-1),Tree.ins(rt[st[i]],0,70000,val,1);
		v[st[top]]=val;
	}
	I void insert(int &p,CI k,CI x){
		if(!p){ sz[p=x]++,Tree.NewTree(rt[p],v[x]);return; } 
		sz[p]++,Tree.ins(rt[p],0,70000,v[x],1);
		k<=sz[ls]+1?insert(ls,k,x):insert(rs,k-sz[ls]-1,x);
		up(p);if(sz[p]*alpha<=(DB)max(sz[ls],sz[rs])) rebuild(p);
	}
} tr;
I void init(){
	scanf("%d",&n);rep(i,1,n) scanf("%d",&v[i]),tr.st[i]=i;
	rep(i,1,SZ-6) Tree.st[++Tree.top]=2e7-i;tr.root=tr.build(1,n);
}
I void solve(){
	scanf("%d",&q);RI last=0,x,y,z;
	W(q--){scanf("%s",c+1);
		if(c[1]=='Q')
			scanf("%d%d%d",&x,&y,&z),x^=last,y^=last,z^=last,
			printf("%d\n",last=tr.query(x,y,z));
		if(c[1]=='M')
			scanf("%d%d",&x,&y),x^=last,y^=last,tr.modify(x,y);
		if(c[1]=='I')
			scanf("%d%d",&x,&y),x^=last,y^=last,v[++n]=y,tr.insert(tr.root,x,n);
	}
};
int main(){ init(),solve();return 0;}