Description
从前有$n$只跳蚤排成一行做早操，每只跳蚤都有自己的一个弹跳力$a_i$。跳蚤国王看着这些跳蚤国欣欣向荣的情景，感到非常高兴。这时跳蚤国王决定理性愉悦一下，查询区间$k$小值。他每次向它的随从伏特提出这样的问题: 从左往右第$x$个到第$y$个跳蚤中，$a_i$第$k$小的值是多少。
这可难不倒伏特，他在脑袋里使用函数式线段树前缀和的方法水掉了跳蚤国王的询问。
这时伏特发现有些跳蚤跳久了弹跳力会有变化，有的会增大，有的会减少。
这可难不倒伏特，他在脑袋里使用树状数组套线段树的方法水掉了跳蚤国王的询问。（orz 主席树）
这时伏特发现有些迟到的跳蚤会插入到这一行的某个位置上，他感到非常生气，因为……他不会做了。
请你帮一帮伏特吧。
快捷版题意：带插入、修改的区间k小值在线查询。
Solution
因为需要支持插入，所以外层需要一个平衡树，替罪羊树比较好写
内层需要带修改，求K小值，可以使用权值线段树维护平衡树每个节点子树内的所有权值，求K小值时二分查找
所以是平衡树套权值线段树
#include<iostream> #include<vector> #include<cstdio> #include<queue> #include<cmath> using namespace std; int n,val[70005],dfn[70005],root,rt[70005],m,las; const float alpha=0.75; char opt[70005]; inline int read(){ int f=1,w=0; char ch=0; while(ch<'0'||ch>'9'){ch=getchar();} while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return f*w; } namespace SGT{ int lc[10000005],rc[10000005],sum[10000005],cnt; queue<int>rec; int newnode(){ if(rec.size()){ int ret=rec.front(); rec.pop(); return ret; } return ++cnt; } inline void pushup(int i){sum[i]=sum[lc[i]]+sum[rc[i]];} void recyc(int &i){ if(!i)return; rec.push(i),recyc(lc[i]),recyc(rc[i]),sum[i]=0,i=0; } void update(int &i,int l,int r,int p,int v){ if(!i)i=newnode(); if(l==r){sum[i]+=v;return;} int mid=l+r>>1; if(p<=mid)update(lc[i],l,mid,p,v); else update(rc[i],mid+1,r,p,v); pushup(i); if(!sum[i])recyc(i); } } namespace BST{ int lc[70005],rc[70005]; vector<int>ve,pos; void build(int &i,int l,int r){ if(l>r)return; if(l==r){i=dfn[l],SGT::update(rt[i],0,70000,val[i],1);return;} int mid=l+r>>1; i=dfn[mid]; build(lc[i],l,mid-1),build(rc[i],mid+1,r); for(int j=l;j<=r;j++)SGT::update(rt[i],0,70000,val[dfn[j]],1); } void del(int &k){ if(!k)return; SGT::recyc(rt[k]),del(lc[k]),ve.push_back(k),del(rc[k]),k=0; } void rebuild(int &k){ del(k); for(int i=0;i<ve.size();i++)dfn[i+1]=ve[i]; build(k,1,ve.size()),ve.clear(); } int dfs(int k,int x,int v){ SGT::update(rt[k],0,70000,v,1); int temp=SGT::sum[rt[lc[k]]],ret=0; if(temp+1==x)ret=val[k],val[k]=v; else if(temp>=x)ret=dfs(lc[k],x,v); else ret=dfs(rc[k],x-temp-1,v); SGT::update(rt[k],0,70000,ret,-1); return ret; } void insert(int &k,int x,int v){ if(!k){k=++n,SGT::update(rt[k],0,70000,v,1),val[k]=v;return;} SGT::update(rt[k],0,70000,v,1); int temp=SGT::sum[rt[lc[k]]]; if(temp>=x)insert(lc[k],x,v); else insert(rc[k],x-temp-1,v); if((double)SGT::sum[rt[k]]*alpha<max(SGT::sum[rt[lc[k]]],SGT::sum[rt[rc[k]]]))rebuild(k); } void query(int k,int l,int r){ int temp=SGT::sum[rt[lc[k]]],lim=SGT::sum[rt[k]]; if(l==1&&r==lim){ve.push_back(rt[k]);return;} if(l<=temp+1&&r>=temp+1)pos.push_back(val[k]); if(r<=temp)query(lc[k],l,r); else if(l>temp+1)query(rc[k],l-temp-1,r-temp-1); else{ if(l<=temp)query(lc[k],l,temp); if(lim>temp+1)query(rc[k],1,r-temp-1); } } int ask(int l,int r,int K){ query(root,l,r); int L=0,R=70000; while(L<R){ int mid=L+R>>1,s=0; for(int i=0;i<ve.size();i++)s+=SGT::sum[SGT::lc[ve[i]]]; for(int i=0;i<pos.size();i++)if(L<=pos[i]&&pos[i]<=mid)s++; if(K<=s){ for(int i=0;i<ve.size();i++)ve[i]=SGT::lc[ve[i]]; R=mid; } else{ for(int i=0;i<ve.size();i++)ve[i]=SGT::rc[ve[i]]; L=mid+1,K-=s; } } ve.clear(),pos.clear(); return L; } } int main(){ n=read(); for(int i=1;i<=n;i++)val[i]=read(),dfn[i]=i; BST::build(root,1,n),m=read(); for(;m;m--){ scanf("%s",opt); if(opt[0]=='M'){ int x=read()^las,y=read()^las; BST::dfs(root,x,y); } else if(opt[0]=='I'){ int x=read()^las,y=read()^las; BST::insert(root,x-1,y); } else{ int x=read()^las,y=read()^las,K=read()^las; printf("%d ",las=BST::ask(x,y,K)); } } return 0; }