Solution
把普通平衡树代码中 rt改成 rt[pos]，然后写一个线段树即可
说说很简单，但是写起来真的麻烦死，后来我是找了一份和我写得有点像的代码改了好久才改出来的，其中一个原因竟然是我原本的平衡树板子就是错的！！！’
复杂度 O(nlog3n)
Code
代码有点慢， bzoj上跑了 9916ms
注释掉的代码旁边若没有文字，则说明是另一种写法，也是对的，只是慢一点，可以直接替换
#include<bits/stdc++.h>
using namespace std;
const int N=2000002,inf=2147483647;
#define lc ch[0]
#define rc ch[1]
int sz[N],fa[N],cnt[N],a[N],ans,mid,l,r,ll,rr,k,rt[N],tot,val[N],ch[2][N],n,m,i,opt;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
int x=0,fl=1;char ch=gc();
for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
return x*fl;
}
inline void wri(int a){if(a<0)a=-a,putchar('-');if(a>=10)wri(a/10);putchar(a%10|48);}
inline void wln(int a){wri(a);puts("");}
//---------------------------------------------------------平衡树
void upd(int x){sz[x]=sz[lc[x]]+sz[rc[x]]+cnt[x];}
void rot(int x){
int y=fa[x],z=fa[y];bool f=x==rc[y];
if (z) ch[y==rc[z]][z]=x;
fa[x]=z,fa[y]=x,fa[ch[!f][x]]=y,ch[f][y]=ch[!f][x],ch[!f][x]=y;
upd(y);
}
void splay(int pos,int x){
while (fa[x]){
int y=fa[x],z=fa[y];
if (z) rot((y==rc[z])^(x==rc[y])?x:y);
rot(x);
}
upd(x);
rt[pos]=x;
}
void ins(int pos,int x){
int t=rt[pos],ff=0;
while (t){
sz[t]++;
if (x==val[t]){
cnt[t]++;
return;
}
ff=t,t=ch[x>val[t]][t];
}
t=++tot;
ch[x>val[ff]][ff]=t;
fa[t]=ff,val[t]=x,lc[t]=rc[t]=0,sz[t]=cnt[t]=1;
splay(pos,t);
}
int find(int pos,int x){
int t=rt[pos];
do{
if (x==val[t]) break;
t=ch[x>val[t]][t];
}while (1);
splay(pos,t);
return t;
}
int rank(int pos,int x){
int t=rt[pos],ret=0;
while (t){
if (x==val[t]) return ret+sz[lc[t]];
if (x>val[t]){
ret+=sz[lc[t]]+cnt[t];
t=rc[t];
}else t=lc[t];
}
return ret;
}
//int Max(int x){return rc[x]?Max(rc[x]):x;}
int Max(int t){while (rc[t]) t=rc[t];return t;}
void del(int pos,int x){
x=find(pos,x);
int ls=lc[x],rs=rc[x];
if (--cnt[x]) return;
if (!ls && !rs){//不能直接return,先清空一下
int &k=rt[pos];
k=fa[k]=lc[k]=rc[k]=sz[k]=cnt[k]=val[k]=0;
return;
}
if (!ls) rt[pos]=rc[x],fa[rt[pos]]=0;
else if (!rs) rt[pos]=lc[x],fa[rt[pos]]=0;
else{
int lson=Max(ls);swap(ls,lson);
fa[lson]=0,splay(pos,ls),rc[ls]=rs,fa[rs]=ls,upd(ls);
}
}
/*int PRE(int t,int x){ if (!t) return 0; if (x<=val[t]) return PRE(lc[t],x); int tmp=PRE(rc[t],x); return tmp?tmp:t; } int pre(int pos,int x){return val[PRE(rt[pos],x)];}*/
int pre(int pos,int x){
int t=rt[pos];int ans=-inf;
while (t)
if (x>val[t]) ans=max(ans,val[t]),t=rc[t];
else t=lc[t];
return ans;
}
int nxt(int pos,int x){
int t=rt[pos];int ans=inf;
while (t)
if (x<val[t]) ans=min(ans,val[t]),t=lc[t];
else t=rc[t];
return ans;
}
//---------------------------------------------------------线段树
#define mid ((l+r)>>1)//如果没加,这个mid就变二分里的mid了
void insert(int t,int l,int r,int x,int v){
ins(t,v);//和下面的修改一样,我刚开始是在l==r的时候插入的
if (l==r) return;
if (x<=mid) insert(t<<1,l,mid,x,v);
else insert(t<<1|1,mid+1,r,x,v);
//函数开始的ins()作用跟update()差不多
}
void change(int t,int l,int r,int x,int v){
del(t,a[x]),ins(t,v);//刚开始写的是del(t,v)
if (l==r) return;
if (x<=mid) change(t<<1,l,mid,x,v);
else change(t<<1|1,mid+1,r,x,v);
}
int query(int t,int l,int r,int x,int y,int v){
if (x<=l && r<=y) return rank(t,v);
// if (x<=l && r<=y) return sz[lc[fi***)]];----会有不存在v的情况,find()会死循环
int ans=0;
if (x<=mid) ans+=query(t<<1,l,mid,x,y,v);
if (mid<y) ans+=query(t<<1|1,mid+1,r,x,y,v);
return ans;
}
int Prev(int t,int l,int r,int x,int y,int v){
if (x<=l && r<=y) return pre(t,v);
int ans=-inf;
if (x<=mid) ans=max(ans,Prev(t<<1,l,mid,x,y,v));
if (mid<y) ans=max(ans,Prev(t<<1|1,mid+1,r,x,y,v));
return ans;
}
int Succ(int t,int l,int r,int x,int y,int v){
if (x<=l && r<=y) return nxt(t,v);
int ans=inf;
if (x<=mid) ans=min(ans,Succ(t<<1,l,mid,x,y,v));
if (mid<y) ans=min(ans,Succ(t<<1|1,mid+1,r,x,y,v));
return ans;
}
#undef mid
int main(){
n=rd(),m=rd();
for (i=1;i<=n;i++) a[i]=rd(),insert(1,1,n,i,a[i]);
for (;m--;){
opt=rd(),l=rd();
if (opt!=3) r=rd();
k=rd();
if (opt==1) wln(query(1,1,n,l,r,k)+1);
if (opt==2){
ll=0,rr=1e8;
while (ll<=rr){
mid=ll+rr>>1;
if (query(1,1,n,l,r,mid)+1<=k) ans=mid,ll=mid+1;
else rr=mid-1;
/*if (query(1,1,n,l,r,mid)+1<k) ll=mid+1;------比如查询k=1时query()+1一定>=k,会导致不断向左,输出0 else ans=mid,rr=mid-1; 其实两者本质差别是query()+1==k的时候应该向左还是向右, 如果是小于号的话,rr不断向左,query()也变小,导致答案和标程差很多*/
}
wln(ans);
}
if (opt==3) change(1,1,n,l,k),a[l]=k;//a[l]=k不能忘
if (opt==4) wln(Prev(1,1,n,l,r,k));
if (opt==5) wln(Succ(1,1,n,l,r,k));
}
}
京公网安备 11010502036488号