树状数组+主席树，模板题，不多说...
#include#include #include #include #include #include #include using namespace std;#define N 50005#define lson l,m,tr[rt].ls#define rson m+1,r,tr[rt].rs#define PushUp(rt) tr[rt].siz=tr[tr[rt].ls].siz+tr[tr[rt].rs].sizstruct node{ int ls,rs,siz;}tr[N*200];int rot[N],a[N],n,Q,nx,ny,rx[N],ry[N],cnt;void insert(int l,int r,int &rt,int v,int c){ if(!rt)rt=++cnt; tr[rt].siz+=c; if(l==r)return ; int m=(l+r)>>1; if(m>=v)insert(lson,v,c); else insert(rson,v,c);}int query_k(int l,int r,int k){ if(l==r)return l; int m=(l+r)>>1,sizls=0; for(int i=1;i<=nx;i++)sizls-=tr[tr[rx[i]].ls].siz; //printf("aaa%d %d %d %d\n",l,r,k,sizls); for(int i=1;i<=ny;i++)sizls+=tr[tr[ry[i]].ls].siz; //printf("bbb%d %d %d %d\n",l,r,k,sizls); if(sizls>=k) { for(int i=1;i<=nx;i++)rx[i]=tr[rx[i]].ls; for(int i=1;i<=ny;i++)ry[i]=tr[ry[i]].ls; return query_k(l,m,k); } for(int i=1;i<=nx;i++)rx[i]=tr[rx[i]].rs; for(int i=1;i<=ny;i++)ry[i]=tr[ry[i]].rs; return query_k(m+1,r,k-sizls);}int query_x(int l,int r,int x){ if(l==r)return 1; int m=(l+r)>>1,sizls=0; for(int i=1;i<=nx;i++)sizls-=tr[tr[rx[i]].ls].siz; for(int i=1;i<=ny;i++)sizls+=tr[tr[ry[i]].ls].siz; if(m>=x) { for(int i=1;i<=nx;i++)rx[i]=tr[rx[i]].ls; for(int i=1;i<=ny;i++)ry[i]=tr[ry[i]].ls; return query_x(l,m,x); } for(int i=1;i<=nx;i++)rx[i]=tr[rx[i]].rs; for(int i=1;i<=ny;i++)ry[i]=tr[ry[i]].rs; return sizls+query_x(m+1,r,x);}void pre(int l,int r){ nx=ny=0; for(int i=l;i;i-=(i&(-i)))rx[++nx]=rot[i]; for(int i=r;i;i-=(i&(-i)))ry[++ny]=rot[i];}int main(){ scanf("%d%d",&n,&Q); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); for(int j=i;j<=n;j+=j&-j) { insert(-1<<30,1<<30,rot[j],a[i],1); } } while(Q--) { int op,x,y,z; scanf("%d%d%d",&op,&x,&y); if(op!=3)scanf("%d",&z),x--; if(op==1) { pre(x,y); printf("%d\n",query_x(-1<<30,1<<30,z)); }else if(op==2) { pre(x,y); printf("%d\n",query_k(-1<<30,1<<30,z)); }else if(op==3) { for(int i=x;i<=n;i+=i&-i)insert(-1<<30,1<<30,rot[i],a[x],-1); a[x]=y; for(int i=x;i<=n;i+=i&-i)insert(-1<<30,1<<30,rot[i],a[x],1); }else if(op==4) { pre(x,y); int rank=query_x(-1<<30,1<<30,z); pre(x,y); printf("%d\n",query_k(-1<<30,1<<30,rank-1)); }else { pre(x,y); int rank=query_x(-1<<30,1<<30,z+1); pre(x,y); printf("%d\n",query_k(-1<<30,1<<30,rank)); } } return 0;}