下面附上代码：
#include #include #include #include #include #include #include #include #include #include #include using namespace std; const int INF=0x3f3f3f3f; const int maxn=60010; const int maxm=2500010; int ls[maxm],rs[maxm],c[maxm];//ls,rs左右儿子指针。c存值的个数 int arr[maxn],H[maxn],T[maxn];//arr存原序列.H存排序后值。T[i]第i棵线段树的根 int s[maxn],ua[maxn],ub[maxn],*use;//s为树状数组结点。当然也是线段树的根啦。 int n,m,tot; struct node { int l,r,k; } qs[10010];//由于要先hash。 void init()//hash初始化 { sort(H,H+m); m=unique(H,H+m)-H; } int Hash(int x) { return lower_bound(H,H+m,x)-H; } int build(int L,int R)//建空树 { int rt=tot++,mid; c[rt]=0; if(L!=R) { mid=(L+R)>>1; ls[rt]=build(L,mid); rs[rt]=build(mid+1,R); } return rt; } int Insert(int prt,int x,int val) { int nrt=tot++,tp=nrt,l=0,r=m-1,mid; c[nrt]=c[prt]+val; while(l >1; if(x<=mid) { ls[nrt]=tot++,rs[nrt]=rs[prt];//共享结点 prt=ls[prt],nrt=ls[nrt]; r=mid; } else { ls[nrt]=ls[prt],rs[nrt]=tot++; prt=rs[prt],nrt=rs[nrt]; l=mid+1; } c[nrt]=c[prt]+val; } return tp; } int lowbit(int x) { return x&(-x); } void update(int x,int p,int d)//树状数组更新 { while(x<=n) { s[x]=Insert(s[x],p,d); x+=lowbit(x); } } int sum(int x) { int ret=0; while(x) { ret+=c[ls[use[x]]]; x-=lowbit(x); } return ret; } int qu(int L,int R,int k) { int lrt=T[L-1],rrt=T[R],l=0,r=m-1,mid,tp,i,sa,sb; for(i=L-1,use=ua;i;i-=lowbit(i)) use[i]=s[i]; sb=sum(L-1); for(i=R ,use=ub;i;i-=lowbit(i)) use[i]=s[i]; sa=sum(R); while(l >1; tp=sa-sb+c[ls[rrt]]-c[ls[lrt]];//初始值加改变值 if(k<=tp) { r=mid; lrt=ls[lrt],rrt=ls[rrt]; for(i=L-1,use=ua;i;i-=lowbit(i)) use[i]=ls[use[i]];//计算对应子树改变 sb=sum(L-1); for(i=R ,use=ub;i;i-=lowbit(i)) use[i]=ls[use[i]]; sa=sum(R); } else { l=mid+1; k-=tp; lrt=rs[lrt],rrt=rs[rrt]; for(i=L-1,use=ua;i;i-=lowbit(i)) use[i]=rs[use[i]]; sb=sum(L-1); for(i=R ,use=ub;i;i-=lowbit(i)) use[i]=rs[use[i]]; sa=sum(R); } } return l; } int main() { int i,q,cas; char op[10]; scanf("%d",&cas); while(cas--) { scanf("%d%d",&n,&q); tot=m=0; for(i=1;i<=n;i++) scanf("%d",&arr[i]),H[m++]=arr[i]; for(i=0;i