区间线段树套treap，空间复杂度$O(nlogn)$，时间复杂度除了查询区间k大是$O(log^3n)$以外都是$O(log^2n)$的。
(据说线段树套线段树、树状数组套线段树也能过？)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+,inf=0x3f3f3f3f;
#define lson (u<<1)
#define rson (u<<1|1)
#define mid ((l+r)>>1)
int n,m,a[N],rt[N<<],ch[N*][],val[N*],siz[N*],rd[N*],tot;
void pu(int u) {siz[u]=siz[ch[u][]]+siz[ch[u][]]+;}
int newnode(int x) {int u=++tot; val[u]=x,siz[u]=,ch[u][]=ch[u][]=,rd[u]=rand(); return u;}
void rot(int& u,int f) {
int v=ch[u][f];
ch[u][f]=ch[v][f^],ch[v][f^]=u;
pu(u),pu(v),u=v;
}
void ins(int& u,int x) {
if(!u) {u=newnode(x); return;}
int f=x>val[u];
ins(ch[u][f],x);
if(rd[ch[u][f]]>rd[u])rot(u,f);
if(u)pu(u);
}
void del(int& u,int x) {
if(!u)return;
if(val[u]==x) {
if(!ch[u][]||!ch[u][])u=ch[u][]|ch[u][];
else {
int f=rd[ch[u][]]>rd[ch[u][]];
rot(u,f),del(ch[u][f^],x);
}
} else del(ch[u][x>val[u]],x);
if(u)pu(u);
}
int rnk(int u,int x) {
int ret=;
for(; u; u=ch[u][x>val[u]])if(x>val[u])ret+=siz[ch[u][]]+;
return ret+;
}
int kth(int u,int k) {
while(k!=siz[ch[u][]]+) {
if(k<siz[ch[u][]]+)u=ch[u][];
else k-=siz[ch[u][]]+,u=ch[u][];
}
return val[u];
}
int lb(int u,int x) {
int ret=;
for(; u; u=ch[u][x>val[u]])if(val[u]<x)ret=val[u];
return ret;
}
int ub(int u,int x) {
int ret=;
for(; u; u=ch[u][x>=val[u]])if(val[u]>x)ret=val[u];
return ret;
}
void upd(int p,int x,int u=,int l=,int r=n) {
del(rt[u],a[p]),ins(rt[u],x);
if(l==r)return;
p<=mid?upd(p,x,lson,l,mid):upd(p,x,rson,mid+,r);
}
void build(int u=,int l=,int r=n) {
for(int i=l; i<=r; ++i)ins(rt[u],a[i]);
if(l==r)return;
build(lson,l,mid),build(rson,mid+,r);
}
int qry1(int L,int R,int x,int u=,int l=,int r=n) {
if(l>=L&&r<=R) {return rnk(rt[u],x)-;}
if(l>R||r<L)return ;
return qry1(L,R,x,lson,l,mid)+qry1(L,R,x,rson,mid+,r);
}
int qry2(int L,int R,int k) {
int l=,r=inf;
while(l<r)qry1(L,R,mid+)>=k?r=mid:l=mid+;
return l;
}
int qry4(int L,int R,int x,int u=,int l=,int r=n) {
if(l>=L&&r<=R) {int t=lb(rt[u],x); return t?t:~inf;}
if(l>R||r<L)return ~inf;
return max(qry4(L,R,x,lson,l,mid),qry4(L,R,x,rson,mid+,r));
}
int qry5(int L,int R,int x,int u=,int l=,int r=n) {
if(l>=L&&r<=R) {int t=ub(rt[u],x); return t?t:inf;}
if(l>R||r<L)return inf;
return min(qry5(L,R,x,lson,l,mid),qry5(L,R,x,rson,mid+,r));
}
int main() {
srand(time());
scanf("%d%d",&n,&m);
for(int i=; i<=n; ++i)scanf("%d",&a[i]);
build();
while(m--) {
int f,l,r,x;
scanf("%d",&f);
if(f==)scanf("%d%d%d",&l,&r,&x),printf("%d\n",qry1(l,r,x)+);
else if(f==)scanf("%d%d%d",&l,&r,&x),printf("%d\n",qry2(l,r,x));
else if(f==)scanf("%d%d",&l,&x),upd(l,x),a[l]=x;
else if(f==)scanf("%d%d%d",&l,&r,&x),printf("%d\n",qry4(l,r,x));
else if(f==)scanf("%d%d%d",&l,&r,&x),printf("%d\n",qry5(l,r,x));
}
return ;
}