线段树套平衡树( $ n(log^2n+log^3n) $ )
cpp
mt19937_64 rng(114514);
struct FHQ{
int ls,rs,key,sz,val;
} fhq[N];
int idx,T1,T2,T3;
int newNode(int val){
fhq[++idx]={0,0,(int)rng(),1,val};
return idx;
}
void pushup(int u){
fhq[u].sz=fhq[fhq[u].ls].sz+fhq[fhq[u].rs].sz+1;
}
void split(int u,int val,int &x,int &y){
if(!u){
x=y=0;
return;
}
if(fhq[u].val>val){
y=u;
split(fhq[u].ls,val,x,fhq[u].ls);
}
else{
x=u;
split(fhq[u].rs,val,fhq[u].rs,y);
}
pushup(u);
}
int merge(int x,int y){
if(!x||!y)return x+y;
if(fhq[x].key>fhq[y].key){
fhq[x].rs=merge(fhq[x].rs,y);
pushup(x);
return x;
}
fhq[y].ls=merge(x,fhq[y].ls);
pushup(y);
return y;
}
void insert(int &root,int val){
split(root,val,T1,T2);
root=merge(merge(T1,newNode(val)),T2);
}
void del(int &root,int val){
split(root,val,T1,T2);
split(T1,val-1,T1,T3);
T3=merge(fhq[T3].ls,fhq[T3].rs);
root=merge(merge(T1,T3),T2);
}
int find_rank(int &root,int val){
split(root,val-1,T1,T2);
int res=fhq[T1].sz;
root=merge(T1,T2);
return res;
}
int find_prev(int u,int val){
if(u==0)return -INF;
if(fhq[u].val<val){
int res=find_prev(fhq[u].rs,val);
return res==-INF?fhq[u].val:res;
}
return find_prev(fhq[u].ls,val);
}
int find_next(int u,int val){
if(u==0)return INF;
if(fhq[u].val>val){
int res=find_next(fhq[u].ls,val);
return res==INF?fhq[u].val:res;
}
return find_next(fhq[u].rs,val);
}
struct Node{
int l,r,root;
};
struct SegmentTree{
vector<Node> t;
vector<int> a;
SegmentTree(int n,vector<int> a):a(a){
t=vector<Node> (n<<2);
}
void build(int p,int l,int r){
t[p]={l,r,0};
for(int i=l;i<=r;i++)insert(t[p].root,a[i]);
if(l==r)return;
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
int query_rank(int p,int l,int r,int x){
if(l<=t[p].l&&r>=t[p].r){
return find_rank(t[p].root,x);
}
int mid=t[p].l+t[p].r>>1;
int res=0;
if(l<=mid)res+=query_rank(p<<1,l,r,x);
if(r>mid)res+=query_rank(p<<1|1,l,r,x);
return res;
}
int query_kth(int l,int r,int k){
int L=0,R=1e9;
while(L<R){
int mid=L+R+1>>1;
if(query_rank(1,l,r,mid)+1<=k)L=mid;
else R=mid-1;
}
return L;
}
void modify(int p,int x,int y){
del(t[p].root,a[x]);
insert(t[p].root,y);
if(t[p].l==t[p].r){
a[x]=y;
return;
}
int mid=t[p].l+t[p].r>>1;
if(x<=mid)modify(p<<1,x,y);
else modify(p<<1|1,x,y);
}
int prev(int p,int l,int r,int x){
if(l<=t[p].l&&r>=t[p].r)return find_prev(t[p].root,x);
int res=-INF;
int mid=t[p].l+t[p].r>>1;
if(l<=mid)res=max(res,prev(p<<1,l,r,x));
if(r>mid)res=max(res,prev(p<<1|1,l,r,x));
return res;
}
int next(int p,int l,int r,int x){
if(l<=t[p].l&&r>=t[p].r)return find_next(t[p].root,x);
int res=INF;
int mid=t[p].l+t[p].r>>1;
if(l<=mid)res=min(res,next(p<<1,l,r,x));
if(r>mid)res=min(res,next(p<<1|1,l,r,x));
return res;
}
};