Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：n,m<=50000
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)
直接主席树。然后出现各种bug，慢慢说吧。
1.在查询前驱的时候先二分找到小于x的最大的数的id，然后在主席树上跑，如果id<=mid去左子树，如果不是的话，如果右子树有数就去右子树。
发现少考虑了一个问题就是假设k不在右子树的右端点，那么可能(mid,k]没有数，而[k+1,r]有数，然后就GG了。
2.改用名次查询，找到比k小的有num个，然后在rank上找到第num个数就是答案。
发现如果查前驱的时候，如果该数大于所有的权值，那么由于二分上界，他会返回最大的数的id。然而实际上最大的数都比他小，GG。所以增添两个哨兵节点。（或者可以将询问的所有权值都加到离散化里建树）。
之前说到内存回收对吧。
发现不回收空间复杂度极限是O((n+2*m)*logn*logtot)
用树状数组算了一下，大概1932w*3吧，大概过不了的吧。（汗。。反正我开到125MB<=128MB过了，你管我？？？）
发现由于每次都是同一个根，所以可以内存回收。每次将不用的节点扔到队列里，用的时候可以向队列申请，注意特判0。O(n*logn*logtot)
这样空间复杂度大概减小了3倍。不用提心吊胆了，显然够并且开得下。yeah。
比较性能：
1.反正开不下，直接128MB全用： memory 125436kb time 2436ms
2.开得下，stl队列耗时啊：memory 80544kb time 3068ms（可能写的比较丑）。
下面是两个代码：
1.直接开
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 55000
int n,m;
int a[N],b[N<<1],c[N<<1],tot;
int op[N],ql[N],qr[N],qk[N];
inline int read()
{
char ch=getchar(); int re=0,f=1;
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re*f;
}
void getid()
{
b[++tot]=-1<<30;
sort(b+1,b+tot+1);
c[1]=b[1]; int tmp=1;
for(int i=2;i<=tot;i++)
if(b[i]!=b[i-1]) c[++tmp]=b[i];
tot=tmp;
c[++tot]=1<<30;
}
int toha(int x)
{
int l=1,r=tot+1,mid;
while(l<r)
{
mid=l+r>>1;
if(c[mid]>=x) r=mid;
else l=mid+1;
}
return r;
}
int ls[N*190],rs[N*190],sum[N*190],root[N],cnt;
void update(int l,int r,int &x,int y,int z,int w)
{
x=++cnt; sum[x]=sum[y]+w;
if(l==r) return ;
int mid=l+r>>1;
if(z<=mid) rs[x]=rs[y],update(l,mid,ls[x],ls[y],z,w);
else ls[x]=ls[y],update(mid+1,r,rs[x],rs[y],z,w);
}
void build()
{
for(int i=1;i<=n;i++)
{
a[i]=toha(a[i]);
for(int j=i;j<=n;j+=-j&j)
update(1,tot,root[j],root[j],a[i],1);
}
}
int zr[50],zl[50],tl,tr;
void clear(int l,int r)
{
tl=tr=0;
while(l>0) zl[++tl]=root[l],l-=-l&l;
while(r>0) zr[++tr]=root[r],r-=-r&r;
}
void gors()
{
for(int i=1;i<=tl;i++) zl[i]=rs[zl[i]];
for(int i=1;i<=tr;i++) zr[i]=rs[zr[i]];
}
void gols()
{
for(int i=1;i<=tl;i++) zl[i]=ls[zl[i]];
for(int i=1;i<=tr;i++) zr[i]=ls[zr[i]];
}
int getls()
{
int re=0;
for(int i=1;i<=tr;i++) re+=sum[ls[zr[i]]];
for(int i=1;i<=tl;i++) re-=sum[ls[zl[i]]];
return re;
}
int q_rank(int l,int r,int k)
{
clear(l-1,r); l=1,r=tot;
int i,num=0,mid;
while(l!=r)
{
int mid=l+r>>1;
if(k<=mid) gols(),r=mid;
else num+=getls(),gors(),l=mid+1;
}
return num+1;
}
int q_data(int l,int r,int k)
{
clear(l-1,r); l=1,r=tot;
int num,mid;
while(l!=r)
{
mid=l+r>>1; num=getls();
if(k<=num) gols(),r=mid;
else k-=num,gors(),l=mid+1;
}
return c[l];
}
void fix(int x,int w)
{
for(int i=x;i<=n;i+=-i&i)
{
update(1,tot,root[i],root[i],a[x],-1);
update(1,tot,root[i],root[i],w,1);
}
a[x]=w;
}
int q_befor(int l,int r,int k) {return q_data(l,r,q_rank(l,r,k)-1);}
int q_after(int l,int r,int k) {return q_data(l,r,q_rank(l,r,k));}
int main()
{
scanf("%d%d",&n,&m); tot=n;
for(int i=1;i<=n;i++) b[i]=a[i]=read();
for(int i=1;i<=m;i++)
{
op[i]=read();
if(op[i]==3) {ql[i]=read(); b[++tot]=qk[i]=read();}
else {ql[i]=read(); qr[i]=read(); qk[i]=read();}
}
getid(); build();
for(int i=1;i<=m;i++)
{
switch(op[i])
{
case 1:printf("%d\n",q_rank(ql[i],qr[i],toha(qk[i]))); break;
case 2:printf("%d\n",q_data(ql[i],qr[i],qk[i])); break;
case 3:fix(ql[i],toha(qk[i])); break;
case 4:printf("%d\n",q_befor(ql[i],qr[i],toha(qk[i]))); break;
case 5:printf("%d\n",q_after(ql[i],qr[i],toha(qk[i]+1))); break;
}
}
return 0;
}
2.回收
int ls[N*130],rs[N*130],sum[N*130],root[N],cnt;
void update(int l,int r,int &x,int y,int z,int w)
{
if(q.empty()) x=++cnt; else x=q.front(),q.pop();
sum[x]=sum[y]+w;
if(l==r) {if(y) q.push(y); return ;}
int mid=l+r>>1;
if(z<=mid) rs[x]=rs[y],update(l,mid,ls[x],ls[y],z,w);
else ls[x]=ls[y],update(mid+1,r,rs[x],rs[y],z,w);
if(y) q.push(y);
}