【题目分析】
听说是树套树。（雾）
怒写树状数组套主席树，然后就Rank1了。23333
单点修改，区间查询+k大数查询=树状数组套主席树。
【代码】
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define maxn 50005
#define mlog 20
int read()
{
int x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int n,m;
int rt[maxn<<1],a[maxn],b[maxn<<1],cnt=0,tot=0,sum,rnk,TMP;
int ls[maxn<<6],rs[maxn<<6],siz[maxn<<6];
int L[maxn],R[maxn],opt[maxn],x[maxn],y[maxn],z[maxn];
void ins(int o1,int & o2,int l,int r,int x,int f)
{
// printf("ins %d %d %d %d %d %d\n",o1,o2,l,r,x,f);
o2=++tot;
siz[o2]=siz[o1]+f;
if (l==r) return ;
int mid=(l+r)/2;
if (x<=mid) rs[o2]=rs[o1],ins(ls[o1],ls[o2],l,mid,x,f);
else ls[o2]=ls[o1],ins(rs[o1],rs[o2],mid+1,r,x,f);
return ;
}
void ready(int l,int r)
{
// cout<<"ready for "<<l<<" "<<r<<endl;
l--;
L[0]=R[0]=0;
for (int j=l;j;j-=j&(-j)) L[++L[0]]=rt[j];
for (int j=r;j;j-=j&(-j)) R[++R[0]]=rt[j];
// cout<<"L "; for (int j=1;j<=L[0];++j) cout<<L[j]<<" "; cout<<endl;
// cout<<"R "; for (int j=1;j<=R[0];++j) cout<<R[j]<<" "; cout<<endl;
// cout<<"L "; for (int j=1;j<=L[0];++j) cout<<siz[L[j]]<<" "; cout<<endl;
// cout<<"R "; for (int j=1;j<=R[0];++j) cout<<siz[R[j]]<<" "; cout<<endl;
}
void cholef()
{
// cout<<"choose left"<<endl;
for (int i=1;i<=L[0];++i) L[i]=ls[L[i]];
for (int i=1;i<=R[0];++i) R[i]=ls[R[i]];
}
void chorig()
{
// cout<<"choose right"<<endl;
for (int i=1;i<=L[0];++i) L[i]=rs[L[i]];
for (int i=1;i<=R[0];++i) R[i]=rs[R[i]];
}
int taksum()
{
int ret=0;
for (int i=1;i<=L[0];++i) ret-=siz[ls[L[i]]];
for (int i=1;i<=R[0];++i) ret+=siz[ls[R[i]]];
return ret;
}
int qrnk(int l,int r,int x)
{
// printf("qrnk %d %d %d\n",l,r,x);
if (l==r) return 1;
int mid=(l+r)/2,tmp=taksum();
// cout<<"take sum "<<tmp<<endl;
if (x<=mid) return cholef(),qrnk(l,mid,x);
else return chorig(),tmp+qrnk(mid+1,r,x);
}
int qnum(int l,int r,int x)
{
if (l==r) return l;
int mid=(l+r)/2,tmp=taksum();
if (x<=tmp) return cholef(),qnum(l,mid,x);
else return chorig(),qnum(mid+1,r,x-tmp);
}
int main()
{
n=read();m=read();
for (int i=1;i<=n;++i) scanf("%d",&a[i]),b[++cnt]=a[i];
for (int i=1;i<=m;++i)
{
scanf("%d%d%d",&opt[i],&x[i],&y[i]);
if (opt[i]!=3) scanf("%d",&z[i]);
if (opt[i]==3) b[++cnt]=y[i];
if (opt[i]==4||opt[i]==5) b[++cnt]=z[i];
}
sort(b+1,b+cnt+1);
cnt=unique(b+1,b+cnt+1)-b-1;
for (int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
for (int i=1;i<=m;++i)
{
if (opt[i]==1||opt[i]==4||opt[i]==5)z[i]=lower_bound(b+1,b+cnt+1,z[i])-b;
if (opt[i]==3) y[i]=lower_bound(b+1,b+cnt+1,y[i])-b;
}
// cout<<endl<<endl;
// for (int i=1;i<=cnt;++i) cout<<i<<" ";cout<<endl;
// for (int i=1;i<=cnt;++i) cout<<b[i]<<" "; cout<<endl;
// for (int i=1;i<=m;++i) cout<<opt[i]<<" "<<x[i]<<" "<<y[i]<<" "<<z[i]<<endl;
// cout<<endl<<endl;
for (int i=1;i<=n;++i)
for (int j=i;j<=n;j+=j&(-j))
ins(rt[j],rt[j],1,cnt,a[i],1);
for (int i=1;i<=m;++i)
{
switch(opt[i])
{
case 1:
ready(x[i],y[i]);
printf("%d\n",qrnk(1,cnt,z[i]));
break;
case 3:
for (int j=x[i];j<=n;j+=j&(-j))
{
ins(rt[j],rt[j],1,cnt,a[x[i]],-1);
ins(rt[j],rt[j],1,cnt,y[i],1);
}
a[x[i]]=y[i];
break;
case 2:
ready(x[i],y[i]);
printf("%d\n",b[qnum(1,cnt,z[i])]);
break;
case 4:
ready(x[i],y[i]);
rnk=qrnk(1,cnt,z[i]);
// printf("rnk is %d\n",rnk);
ready(x[i],y[i]);
printf("%d\n",b[qnum(1,cnt,rnk-1)]);
break;
case 5:
ready(x[i],y[i]);
TMP=0;
TMP-=qrnk(1,cnt,z[i]);
ready(x[i],y[i]);
TMP+=qrnk(1,cnt,z[i]+1);
// printf("it s have %d\n",TMP);
ready(x[i],y[i]);
rnk=qrnk(1,cnt,z[i]);
ready(x[i],y[i]);
printf("%d\n",b[qnum(1,cnt,rnk+TMP)]);
}
}
}