修改+查询第k小值
单纯主席树修改会打乱所有，所以再套一个树状数组维护前缀和使得修改，查询都是log
对了，bzoj上不需要读入组数，蜜汁re。。
#include#include #include #include #include using namespace std;int n,m,sz,T,num_tot,num_cnt,num_l,num_r;int sum[8000005],lon[8000005],ron[8000005],num[60005];int a[50005],k[10005],p[10005],q[10005],root[60005];bool bo[10005];int L[500],R[500];int lowbit(int x){return x&(-x);}void update(int p,int &rt,int l,int r,int x,int y){ rt=++sz; sum[rt]=sum[p]+y; lon[rt]=lon[p]; ron[rt]=ron[p]; if(l==r) return; int mid=(l+r)/2; if(x<=mid) update(lon[p],lon[rt],l,mid,x,y); else update(ron[p],ron[rt],mid+1,r,x,y);}int query(int l,int r,int k){ if(l==r) return l; int suml=0,sumr=0; for(int i=1;i<=num_l;i++) suml+=sum[lon[L[i]]]; for(int i=1;i<=num_r;i++) sumr+=sum[lon[R[i]]]; int mid=(l+r)/2; if(sumr-suml>=k){ for(int i=1;i<=num_l;i++) L[i]=lon[L[i]]; for(int i=1;i<=num_r;i++) R[i]=lon[R[i]]; return query(l,mid,k); } else{ for(int i=1;i<=num_l;i++) L[i]=ron[L[i]]; for(int i=1;i<=num_r;i++) R[i]=ron[R[i]]; return query(mid+1,r,k-(sumr-suml)); }}int main(){ char s[5]; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); num[i]=a[i]; } num_tot=n; for(int i=1;i<=m;i++){ scanf("%s",s); if(s[0]=='Q') scanf("%d%d%d",&p[i],&q[i],&k[i]); else{ scanf("%d%d",&p[i],&q[i]); num[++num_tot]=q[i]; bo[i]=1; } } sort(num+1,num+num_tot+1); int num_cnt=unique(num+1,num+num_tot+1)-num-1; for(int i=1;i<=n;i++){ int t=lower_bound(num+1,num+num_cnt+1,a[i])-num; for(int j=i;j<=n;j+=lowbit(j)) update(root[j],root[j],1,num_cnt,t,1); } for(int i=1;i<=m;i++){ if(bo[i]){ int t=lower_bound(num+1,num+num_cnt+1,a[p[i]])-num; for(int j=p[i];j<=n;j+=lowbit(j)) update(root[j],root[j],1,num_cnt,t,-1); a[p[i]]=q[i]; t=lower_bound(num+1,num+num_cnt+1,q[i])-num; for(int j=p[i];j<=n;j+=lowbit(j)) update(root[j],root[j],1,num_cnt,t,1); } else{ p[i]--; num_l=num_r=0; for(int j=p[i];j>0;j-=lowbit(j)) L[++num_l]=root[j]; for(int j=q[i];j>0;j-=lowbit(j)) R[++num_r]=root[j]; printf("%d\n",num[query(1,num_cnt,k[i])]); } } return 0;}