树状数组+主席树，模板题，不多说…
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <iostream>
#include <cstdlib>
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].siz
struct 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;
}
