经过周六一天，周一3个小时的晚自习，周二2个小时的疯狂debug，终于凭借自己切掉了这道树套树题.
Code:
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
// 带插入区间 k 小值
// 外层：替罪羊
// 内层：权值线段树
using namespace std;
#define setIO(s) freopen(s".in","r",stdin), freopen(s".out","w",stdout)
#define debug() printf("OK
")
#define maxn 11005000
#define N 70002
int n,lastans;
struct Segment_Tree{
struct Node{
int ls,rs,siz;
Node(int ls=0,int rs=0,int siz=0):ls(ls),rs(rs),siz(siz){}
}node[maxn];
queue<int>Q;
void init(){ for(int i=1;i<maxn;++i) Q.push(i); }
void newnode(int &o) { o=Q.front(), Q.pop(); }
void update(int l,int r,int &o,int pos,int delta){
if(!o) newnode(o);
node[o].siz+=delta;
if(!node[o].siz) { dfs(o); return; }
if(l==r) return;
int mid=(l+r)>>1;
if(pos<=mid) update(l,mid,node[o].ls,pos,delta);
else update(mid+1,r,node[o].rs,pos,delta);
}
void dfs(int &o){
if(!o)return;
dfs(node[o].ls),Q.push(o),dfs(node[o].rs);
node[o].siz=0;
o=0;
}
}segin;
struct Binary_Search_Tree{
inline bool check(int son,int o){
if(son*10>=o*9) return true;
return false;
}
int cnt,root;
int seq[N],count[3];
vector<int>re;
struct Node{
int ls,rs,siz,root,cur,val;
Node(int ls=0,int rs=0,int siz=0,int root=0,int cur=0,int val=0):ls(ls),rs(rs),root(root),cur(cur),val(val){}
}node[maxn];
inline void newnode(int &o,int val){ o=++cnt,node[o].val=val,node[o].siz=1; }
void dfs(int &o){
if(!o) return;
segin.dfs(node[o].root),segin.dfs(node[o].cur);
dfs(node[o].ls),re.push_back(o),dfs(node[o].rs);
node[o].siz=0;
o=0;
}
void construct(int l,int r,int &o){
if(l>r)return;
int mid=(l+r)>>1;
o=re[mid];
for(int i=l;i<=r;++i)
segin.update(0,N,node[o].root,node[re[i]].val,1);
segin.update(0,N,node[o].cur,node[o].val,1);
if(l==r){ node[o].siz=1; return; }
construct(l,mid-1,node[o].ls), construct(mid+1,r,node[o].rs);
node[o].siz=node[node[o].ls].siz+node[node[o].rs].siz+1;
}
inline void Rebuild(int &o){ re.clear(),dfs(o),construct(0,re.size()-1,o); }
void insert(int &o,int k,int val,bool is){
if(!o){
newnode(o,val),segin.update(0,N,node[o].root,val,1),segin.update(0,N,node[o].cur,val,1);
return;
}
++node[o].siz, segin.update(0,N,node[o].root,val,1);
bool tag;
if(k<=node[node[o].ls].siz+1) tag=check(node[node[o].ls].siz+1,node[o].siz), insert(node[o].ls,k,val,is||tag);
else tag=check(node[node[o].rs].siz+1,node[o].siz), insert(node[o].rs,k-node[node[o].ls].siz-1,val,is||tag);
if(!is&&tag) Rebuild(o);
}
int modify(int o,int pos,int delta){
int num;
if(pos==node[node[o].ls].siz+1) {
segin.update(0,N,node[o].root,node[o].val,-1),segin.dfs(node[o].cur),node[o].cur=0;
segin.update(0,N,node[o].root,delta,1),segin.update(0,N,node[o].cur,delta,1);
num=node[o].val,node[o].val=delta;
return num;
}
if(pos<=node[node[o].ls].siz) num=modify(node[o].ls,pos,delta);
else num=modify(node[o].rs,pos-node[node[o].ls].siz-1,delta);
segin.update(0,N,node[o].root,num,-1),segin.update(0,N,node[o].root,delta,1);
return num;
}
void Build(){
scanf("%d",&n),re.clear();
int tmp,x ;
for(int i=1;i<=n;++i)
scanf("%d",&tmp),newnode(x,tmp),re.push_back(x);
construct(0,re.size()-1,root);
}
void Get(int l,int r,int o,int L,int R){
if(l>R||r<L||l>r||!o)return;
if(l>=L&&r<=R) { seq[++count[0]]=node[o].root; return; }
int mid=node[node[o].ls].siz+l;
if(mid>=L&&mid<=R&&mid<=r) seq[++count[0]]=node[o].cur;
Get(l,mid-1,node[o].ls,L,R),Get(mid+1,r,node[o].rs,L,R);
}
int solve(int l,int r,int k){
if(l==r) return l;
int lsum=0;
for(int i=1;i<=count[0];++i) {
lsum+=segin.node[segin.node[seq[i]].ls].siz;
}
int mid=(l+r)>>1;
if(k>lsum)
{
for(int i=1;i<=count[0];++i) seq[i]=segin.node[seq[i]].rs;
return solve(mid+1,r,k-lsum);
}
else
{
for(int i=1;i<=count[0];++i)seq[i]=segin.node[seq[i]].ls;
return solve(l,mid,k);
}
}
void Insert(){
int a,b;
++n,scanf("%d%d",&a,&b),a^=lastans,b^=lastans,insert(root,a,b,0);
}
void Modify(){
int a,b;
scanf("%d%d",&a,&b),a^=lastans,b^=lastans,modify(root,a,b);
}
int Query(){
int L,R,k;
count[0]=0, scanf("%d%d%d",&L,&R,&k),L^=lastans,R^=lastans,k^=lastans;
if(L>R)swap(L,R);
Get(1,n,root,L,R);
return solve(0,N,k);
}
}BST;
int main(){
//setIO("input");
segin.init(), BST.Build();
char opt[10];
int q;
scanf("%d",&q);
while(q--){
scanf("%s",opt);
if(opt[0]=='I') BST.Insert();
if(opt[0]=='M') BST.Modify();
if(opt[0]=='Q') printf("%d
",lastans=BST.Query());
}
return 0;
}