带修改的题主席树不记录前缀，只记录单点，用BIT统计前缀。
对于BIT上每一个点建一棵主席树，修改和询问的时候用BIT跑，在主席树上做就行了。
3k4人AC的题#256...应该不算慢
#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=110010,inf=1e9; struct poi{int size,lt,rt;}tree[maxn*20]; int n,m,tot,sz,cnt1,cnt2,N; int t1[maxn],t2[maxn],a[maxn],b[maxn],x[maxn],y[maxn],z[maxn],root[maxn]; bool q[maxn]; char s[2]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } int lowbit(int x){return x&-x;} void update(int &x,int l,int r,int cx,int delta) { tree[++sz]=tree[x];tree[sz].size+=delta;x=sz; if(l==r)return; int mid=(l+r)>>1; if(cx<=mid)update(tree[x].lt,l,mid,cx,delta); else update(tree[x].rt,mid+1,r,cx,delta); } int query(int l,int r,int k) { if(l==r)return l; int mid=(l+r)>>1,sum1=0,sum2=0; for(int i=1;i<=cnt1;i++)sum1+=tree[tree[t1[i]].lt].size; for(int i=1;i<=cnt2;i++)sum2+=tree[tree[t2[i]].lt].size; if(sum2-sum1>=k) { for(int i=1;i<=cnt1;i++)t1[i]=tree[t1[i]].lt; for(int i=1;i<=cnt2;i++)t2[i]=tree[t2[i]].lt; return query(l,mid,k); } for(int i=1;i<=cnt1;i++)t1[i]=tree[t1[i]].rt; for(int i=1;i<=cnt2;i++)t2[i]=tree[t2[i]].rt; return query(mid+1,r,k-(sum2-sum1)); } int main() { read(n);read(m); for(int i=1;i<=n;i++)read(a[i]),b[++N]=a[i]; for(int i=1;i<=m;i++) { scanf("%s",s+1); read(x[i]);read(y[i]); if(s[1]=='Q')read(z[i]),q[i]=1; else b[++N]=y[i]; } sort(b+1,b+1+N);N=unique(b+1,b+1+N)-b-1; for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+N,a[i])-b; for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=lowbit(j)) update(root[j],1,N,a[i],1); for(int i=1;i<=m;i++) if(q[i]) { cnt1=cnt2=0; for(int j=x[i]-1;j;j-=lowbit(j)) t1[++cnt1]=root[j]; for(int j=y[i];j;j-=lowbit(j)) t2[++cnt2]=root[j]; printf("%d ",b[query(1,N,z[i])]); } else { for(int j=x[i];j<=n;j+=lowbit(j)) update(root[j],1,N,a[x[i]],-1); a[x[i]]=lower_bound(b+1,b+1+N,y[i])-b;; for(int j=x[i];j<=n;j+=lowbit(j)) update(root[j],1,N,a[x[i]],1); } return 0; }