P3380 【模板】二逼平衡树（树套树）题解
萌新怒码4k ，搞出来一份不开O2就会T的代码。
只会 fhq-treap ，所以就来了一发 线段树套 fhq-treap。
也就调了一个小时
一些注意点
- 调用 fhq-treap 时 root 要传址。
- 寻找排名为 k 的数的时候二分的 check 要 queryrk(k+1) ，因为 queryrk() 找的是小于 k 的数，而 check 的要求是小于等于 k 的数。
Code
#include<bits/stdc++.h>
#define N 100005
#define orz puts("orzwyy332623");//tiaoshi
#define ls(p) p<<1
#define rs(p) p<<1|1
using namespace std;
int read(){
int x=0,w=1;
char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*w;
}
const int inf = 2147483647;
int n,m,cnt;
int a[N];
struct node{
struct Tree{int l,r,key,val,siz;}tree[N*20];
int insert(int x){
tree[++cnt].val=x;tree[cnt].siz=1;tree[cnt].key=rand();
return cnt;
}
void push_up(int p){tree[p].siz=tree[tree[p].l].siz+tree[tree[p].r].siz+1;}
int merge(int x,int y){
if(!x||!y) return x+y;
if(tree[x].key<tree[y].key){
tree[x].r=merge(tree[x].r,y);
push_up(x); return x;
}
else{
tree[y].l=merge(x,tree[y].l);
push_up(y); return y;
}
}
void split(int p,int k,int &x,int &y){
if(!p){x=y=0;return ;}
if(tree[p].val<=k)x=p,split(tree[p].r,k,tree[p].r,y);
else y=p,split(tree[p].l,k,x,tree[p].l);
push_up(p);
}
int kth(int p,int k){
if(tree[tree[p].l].siz>=k) return kth(tree[p].l,k);
else if(tree[tree[p].l].siz+1==k) return p;
else return kth(tree[p].r,k-tree[tree[p].l].siz-1);
}
void add(int &root,int x){
int a,b;
split(root,x,a,b);
root=merge(a,merge(insert(x),b));
}
void update(int &root,int k,int w){
int a,b,c;
split(root,k-1,a,b); split(b,k,b,c);
b=merge(tree[b].l,tree[b].r);a=merge(a,merge(b,c));
split(a,w,a,b);
root=merge(a,merge(insert(w),b));
}
int queryrk(int &root,int k){
int a,b;
split(root,k-1,a,b);
int x=tree[a].siz;
root=merge(a,b);
return x;
}
int querypre(int &root,int k){
int a,b;
split(root,k-1,a,b);
int x=tree[a].siz,y;
if(x) y=tree[kth(a,tree[a].siz)].val;
root=merge(a,b);
if(x==0) return -inf;
return y;
}
int querysuf(int &root,int k){
int a,b;
split(root,k,a,b);
int x=tree[b].siz,y;
if(x) y=tree[kth(b,1)].val;
root=merge(a,b);
if(x==0) return inf;
return y;
}
}fhq;
struct Segment{
int root[N<<4];
void build(int p,int l,int r){
for(int i=l;i<=r;++i) fhq.add(root[p],a[i]);
if(l==r) return ;
int mid=(l+r)>>1;
build(ls(p),l,mid);build(rs(p),mid+1,r);
}
void update(int p,int l,int r,int k,int w){
fhq.update(root[p],a[k],w);
if(l==r) return ;
int mid=(l+r)>>1;
if(mid>=k) update(ls(p),l,mid,k,w);
else update(rs(p),mid+1,r,k,w);
}
int queryrk(int p,int l,int r,int k,int L,int R){
int mid=(l+r)>>1;
if(l>R||r<L) return 0;
if(L<=l&&r<=R) return fhq.queryrk(root[p],k);
else return queryrk(ls(p),l,mid,k,L,R)+queryrk(rs(p),mid+1,r,k,L,R);
}
int queryrk1(int L,int R,int k){
int l=0,r=1e8,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(queryrk(1,1,n,mid+1,L,R)>=k)ans=mid ,r=mid-1;
else l=mid+1;
}
return ans;
}
int querypre(int p,int l,int r,int k,int L,int R){
int mid=(l+r)>>1;
if(l>R||r<L) return -inf;
if(L<=l&&r<=R) return fhq.querypre(root[p],k);
else return max(querypre(ls(p),l,mid,k,L,R),querypre(rs(p),mid+1,r,k,L,R));
}
int querysuf(int p,int l,int r,int k,int L,int R){
int mid=(l+r)>>1;
if(l>R||r<L) return inf;
if(L<=l&&r<=R) return fhq.querysuf(root[p],k);
else return min(querysuf(ls(p),l,mid,k,L,R),querysuf(rs(p),mid+1,r,k,L,R));
}
}seg;
signed main(){
n=read();m=read();
for(int i=1;i<=n;++i) a[i]=read();
seg.build(1,1,n);
for(int i=1;i<=m;++i){
int opt=read();
if(opt==1) {
int l=read(),r=read(),k=read();
printf("%d\n",seg.queryrk(1,1,n,k,l,r)+1);
}
else if(opt==2){
int l=read(),r=read(),k=read();
printf("%d\n",seg.queryrk1(l,r,k));
}
else if(opt==3){
int pos=read(),k=read();
seg.update(1,1,n,pos,k);
a[pos]=k;
}
else if(opt==4){
int l=read(),r=read(),k=read();
printf("%d\n",seg.querypre(1,1,n,k,l,r));
}
else {
int l=read(),r=read(),k=read();
printf("%d\n",seg.querysuf(1,1,n,k,l,r));
}
}
return 0;
}