题意：
给定一个长度为n的序列，有m次操作，分别为以下两种情况： 1.Q left right k，查询[left,right]中的第k小数 2.C at data，将第x位的数修改为data题解：①带修改的主席树=主席树+树状数组②与POJ 2104 K-th Number类似，只不过加上了修改操作③考虑每一次修改操作，实际上它只会对[at,n]的区间产生影响④我们可以开一个树状数组来记录这些修改，树状数组的每一个点都是一颗线段树⑤查询的时候只要将原来的查询加上树状数组上的查询即可
#include#include #include using namespace std;const int maxn=50000+10;struct Tree{ int lch,rch; int data;}a[maxn<<5];struct ASK{ int op; int left,right,k; int at,data;}q[maxn];int n,m,A[maxn];int Map[maxn],cnt;int root[maxn],num;int C[maxn],use[maxn];void Init();void Build(int&,int,int);void Update(int&,int,int,int,int,int);int Query(int,int,int,int,int,int,int);int Lowbit(int);void Add(int,int,int);int GetSum(int);signed main(){ // freopen("in.cpp","r",stdin); int t;scanf("%d",&t); while(t--)Init(); return 0;}void Init(){ num=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&A[i]),Map[++cnt]=A[i]; char op; for(int i=1;i<=m;i++){ scanf(" %c",&op); if(op=='Q')q[i].op=1,scanf("%d%d%d",&q[i].left,&q[i].right,&q[i].k); else q[i].op=0,scanf("%d%d",&q[i].at,&q[i].data),Map[++cnt]=q[i].data; } sort(Map+1,Map+1+cnt);cnt=unique(Map+1,Map+1+cnt)-Map-1; Build(root[0],1,cnt); for(int i=1;i<=n;i++){ int x=lower_bound(Map+1,Map+1+cnt,A[i])-Map; Update(root[i],root[i-1],1,cnt,x,1); } for(int i=1;i<=n;i++)C[i]=root[0]; for(int i=1,x;i<=m;i++){ if(q[i].op){ for(int j=q[i].left-1;j;j-=Lowbit(j)) use[j]=C[j]; for(int j=q[i].right;j;j-=Lowbit(j)) use[j]=C[j]; x=Query(root[q[i].left-1],root[q[i].right],q[i].left-1,q[i].right,1,cnt,q[i].k); printf("%d\n",Map[x]); } else{ x=lower_bound(Map+1,Map+1+cnt,A[q[i].at])-Map; Add(q[i].at,x,-1); x=lower_bound(Map+1,Map+1+cnt,q[i].data)-Map; Add(q[i].at,x,1); A[q[i].at]=q[i].data; } }}void Build(int &u,int left,int right){ u=++num; a[u].data=0; if(left==right)return; int mid=(left+right)>>1; Build(a[u].lch,left,mid); Build(a[u].rch,mid+1,right);}void Update(int &u,int y,int left,int right,int pos,int key){ u=++num; a[u].lch=a[y].lch;a[u].rch=a[y].rch; a[u].data=a[y].data+key; if(left==right)return; int mid=(left+right)>>1; if(pos<=mid)Update(a[u].lch,a[y].lch,left,mid,pos,key); else Update(a[u].rch,a[y].rch,mid+1,right,pos,key);}int Query(int u,int v,int L,int R,int left,int right,int k){ if(left==right)return left; int mid=(left+right)>>1; int data=GetSum(R)-GetSum(L)+a[a[v].lch].data-a[a[u].lch].data; if(data>=k){ for(int i=L;i;i-=Lowbit(i)) use[i]=a[use[i]].lch; for(int i=R;i;i-=Lowbit(i)) use[i]=a[use[i]].lch; return Query(a[u].lch,a[v].lch,L,R,left,mid,k); } else{ for(int i=L;i;i-=Lowbit(i)) use[i]=a[use[i]].rch; for(int i=R;i;i-=Lowbit(i)) use[i]=a[use[i]].rch; return Query(a[u].rch,a[v].rch,L,R,mid+1,right,k-data); }}int Lowbit(int x){ return x&(-x);}void Add(int x,int pos,int key){ for(int i=x;i<=n;i+=Lowbit(i)) Update(C[i],C[i],1,cnt,pos,key);}int GetSum(int x){ int ans=0; for(int i=x;i;i-=Lowbit(i)) ans+=a[a[use[i]].lch].data; return ans;}
