传送门
直接大力线段树套平衡树
线段树维护区间，平衡树维护权值
对于询问区间内排名为 $K$ 的值，二分答案然后判断
其余操作都很好搞了
复杂度 $O(nlog^3_n)$ ，然后就是丧心病狂的代码和卡常时间了QAQ
我这个傻逼的代码要开 $O2$ 才过得去QAQ
如果一开始建树时不要一个个插入而是直接归并建树会快很多，像这样：
inline int build_s(int l,int r) { if(l>r) return 0; int x=++tot,mid=(l+r)>>1; val[tot]=a[mid]; size[x]=1; fa[lc=build_s(l,mid-1)]=x; fa[rc=build_s(mid+1,r)]=x; up(x); return x; } inline void build_t(int rt,int l,int r) { if(l==r) return (void)(root[rt]=build_s(l,r)); int mid=(l+r)>>1,i=l,j=mid+1,p=l; build_t(rt<<1,l,mid); build_t(rt<<1|1,mid+1,r); while(i<=mid&&j<=r) { if(a[i]<=a[j]) b[p++]=a[i++]; else b[p++]=a[j++]; } while(i<=mid) b[p++]=a[i++]; while(j<=r) b[p++]=a[j++]; for(_R int i=l;i<=r;i++) a[i]=b[i]; root[rt]=build_s(l,r); }
然而懒得写了，其他细节操作看代码吧
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<queue> using namespace std; typedef long long ll; inline 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<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=5e6+7,INF=2147483647; int n,m,cnt; int c[N][2],fa[N],sz[N],val[N]; struct SPLAY { int rt,res; inline void pushup(int x) { sz[x]=sz[c[x][0]]+sz[c[x][1]]+1; } inline void rotate(int x,int &k) { int y=fa[x],z=fa[y],d=(c[y][1]==x); y==k ? k=x : c[z][c[z][1]==y]=x; fa[x]=z; fa[y]=x; fa[c[x][d^1]]=y; c[y][d]=c[x][d^1]; c[x][d^1]=y; pushup(y); pushup(x); } inline void splay(int x,int &k) { while(x!=k) { int y=fa[x],z=fa[y]; if(y!=k) (c[y][0]==x ^ c[z][0]==y) ? rotate(x,k) : rotate(y,k); rotate(x,k); } } inline int Q_rank(int k) { int x=rt,res=0,f=0; while(x) { f=x; if(val[x]>=k) x=c[x][0]; else res+=sz[c[x][0]]+1,x=c[x][1]; } if(f) splay(f,rt); return res; } inline int Q_kth(int x,int k) { while(233) { if(sz[c[x][0]]+1==k) return x; if(sz[c[x][0]]>=k) { x=c[x][0]; continue; } k-=sz[c[x][0]]+1; x=c[x][1]; } } inline void ins(int k) { int x=rt,f=0; while(x) f=x,x=c[x][k>val[x]]; x=++cnt; val[x]=k; sz[x]=1; fa[x]=f; if(f) c[f][k>val[f]]=x; if(rt) splay(x,rt); else rt=x; } inline void del(int k) { int x=rt; while(val[x]!=k) x=c[x][k>val[x]]; splay(x,rt); if(c[x][0]&&c[x][1]) { int y=Q_kth(rt,sz[c[x][0]]); splay(y,c[x][0]); x=rt; c[y][1]=c[x][1]; fa[c[x][1]]=y; rt=y; fa[rt]=0; pushup(y); } else if(c[x][0]) rt=c[x][0],fa[rt]=0; else if(c[x][1]) rt=c[x][1],fa[rt]=0; else rt=0; } void pre(int x,int k) { if(!x) return; if(val[x]>res&&val[x]<k) res=val[x]; pre(c[x][k>val[x]],k); } void nex(int x,int k) { if(!x) return; if(val[x]<res&&val[x]>k) res=val[x]; nex(c[x][k>=val[x]],k); } inline int Pre(int k) { res=-INF; pre(rt,k); return res; } inline int Nex(int k) { res=INF; nex(rt,k); return res; } }S[N<<2]; int A[N]; int pos,v,ql,qr,res; void INS(int o,int l,int r) { S[o].ins(v); if(l==r) return; int mid=l+r>>1; if(pos<=mid) INS(o<<1,l,mid); else INS(o<<1|1,mid+1,r); } void Q1(int o,int l,int r) { if(l>=ql&&r<=qr) { res+=S[o].Q_rank(v); return; } int mid=l+r>>1; if(ql<=mid) Q1(o<<1,l,mid); if(qr>mid) Q1(o<<1|1,mid+1,r); } void Change(int o,int l,int r) { S[o].del(A[pos]); S[o].ins(v); if(l==r) return; int mid=l+r>>1; if(pos<=mid) Change(o<<1,l,mid); else Change(o<<1|1,mid+1,r); } void Q4(int o,int l,int r) { if(l>=ql&&r<=qr) { res=max(res,S[o].Pre(v)); return; } int mid=l+r>>1; if(ql<=mid) Q4(o<<1,l,mid); if(qr>mid) Q4(o<<1|1,mid+1,r); } void Q5(int o,int l,int r) { if(l>=ql&&r<=qr) { res=min(res,S[o].Nex(v)); return; } int mid=l+r>>1; if(ql<=mid) Q5(o<<1,l,mid); if(qr>mid) Q5(o<<1|1,mid+1,r); } inline int clac(int p) { res=0,v=p; Q1(1,1,n); return res; } int main() { n=read(),m=read(); int opt; for(pos=1;pos<=n;pos++) v=A[pos]=read(),INS(1,1,n); while(m--) { opt=read(); if(opt==3) { pos=read(),v=read(); Change(1,1,n); A[pos]=v; continue; } if(opt==2) { ql=read(),qr=read(); int w=read(),l=0,r=1e8,ans=0; while(l<=r) { int mid=l+r>>1; if(clac(mid)<w) ans=mid,l=mid+1; else r=mid-1; } printf("%d ",ans); continue; } ql=read(),qr=read(),v=read(); switch(opt) { case 1: { res=0; Q1(1,1,n); printf("%d ",res+1); break; } case 4: { res=-INF; Q4(1,1,n); printf("%d ",res); break; } case 5: { res=INF; Q5(1,1,n); printf("%d ",res); break; } } } return 0; }