P3380 【模板】树套树
这里采取的是线段树套平衡树（FHQ）
考虑树套树可以解决类似于在两维区间限制类似操作的问题
把线段树上每个节点维护一颗平衡树，维护的方法也非常简单，发现只要知道root，就能够访问平衡树，非常简单
考虑每个节点会被添加log次，所以平衡树要 nlogn 个节点，线段树普通 4n 个节点
考虑二操作，就二分一下排名的数，查排名，\(log^3\)
修改操作，把所有包含修改节点的平衡树进行修改
注意！！！！！！！（血淋淋的教训，我调了好几个小时）
平衡树添加节点一定要按照顺序合并，即先按照排名分裂，在依次合并，保证满足二叉树性质，这个在添加节点和修改节点时都要满足
查排名是查有多少个小于x的数，因为我们答案最终是要累加起来，别忘了最后+1
修改节点时一定要把修改出来的节点，所有的变量都初始化！！！
#include<bits/stdc++.h>
#define ls(x) dt[x].ls
#define rs(x) dt[x].rs
#define pri(x) dt[x].pri
#define key(x) dt[x].key
#define siz(x) dt[x].siz
using namespace std;
const int N=5e4+5,M=1e8;
int cnt,n,m;
int a[N];
struct node{int root,key;
}tr[N*4];
struct dot{int ls,rs,pri,key,siz;
}dt[N*20];
struct FHQ{int newnode(int x){dt[++cnt]={0,0,rand(),x,1};return cnt;}void update(int u){siz(u)=siz(ls(u))+siz(rs(u))+1;}void split(int u,int x,int &L,int &R){if(u==0){L=R=0;return;}if(key(u)<=x){L=u;split(rs(u),x,rs(u),R);}else{R=u;split(ls(u),x,L,ls(u));}update(u);}int merge(int L,int R){if(!L||!R) return L+R;if(pri(L)<pri(R)){rs(L)=merge(rs(L),R);update(L);return L;}else{ls(R)=merge(L,ls(R));update(R);return R;}}void insert(int &root,int l,int r){//RE表明没写返回值for(int i=l;i<=r;i++){int L,R;split(root,a[i],L,R);root=merge(L,merge(newnode(a[i]),R));}}int rank(int &root,int x){int L,R;split(root,x-1,L,R);int res=siz(L);//这里要判断是否已经全满了root=merge(L,R);return res;}int find(int u,int k){if(!u) return -1;if(siz(ls(u))+1==k) return key(u);else if(siz(ls(u))+1<k) return find(rs(u),k-siz(ls(u))-1);else return find(ls(u),k);}void change(int &root,int x,int k){int L,R,p=0;split(root,x-1,L,R);split(R,x,p,R);int g=p;p=merge(ls(p),rs(p));root=merge(L,merge(p,R));//插入一定是要有顺序的split(root,k,L,R);if(g){dt[g]={0,0,rand(),k,1};//一定要全部修改root=merge(L,merge(g,R));}}int pre(int &root,int x){int L,R;split(root,x-1,L,R);int res=find(L,siz(L));if(res==-1) res=-2147483647;root=merge(L,R);return res;}int suc(int &root,int x){int L,R;split(root,x,L,R);int res=find(R,1);if(res==-1) res=2147483647;root=merge(L,R);return res;}void print(int u){if(!u) return;print(ls(u));printf("%d ",key(u));print(rs(u));}
}FHQ;
struct tree{void build(int k,int l,int r){FHQ.insert(tr[k].root,l,r);if(l==r){tr[k].key=a[l];return;}int mid=(l+r)>>1;build(k*2,l,mid);build(k*2+1,mid+1,r);}void change(int k,int l,int r,int x,int g){FHQ.change(tr[k].root,a[x],g);if(l==r){return;}int mid=(l+r)>>1;if(x<=mid) change(k*2,l,mid,x,g);else change(k*2+1,mid+1,r,x,g);}void she(int &res,int op){if(op==1) res=0;if(op==2) res=-2147483647;if(op==3) res=2147483647;}void update(int &res,int op,int num){if(op==1) res+=num;if(op==2) res=max(res,num);if(op==3) res=min(res,num);}int figue(int k,int g,int op){if(op==1) return FHQ.rank(tr[k].root,g);if(op==2) return FHQ.pre(tr[k].root,g);if(op==3) return FHQ.suc(tr[k].root,g);}int query(int k,int l,int r,int x,int y,int g,int op){if(x<=l&&r<=y){return figue(k,g,op);}int mid=(l+r)>>1,res;she(res,op);if(x<=mid) update(res,op,query(k*2,l,mid,x,y,g,op));if(y>mid) update(res,op,query(k*2+1,mid+1,r,x,y,g,op));return res;}int middle(int x,int y,int k){int l=0,r=M;while(l<r){int mid=(l+r+1)>>1;if(query(1,1,n,x,y,mid,1)+1<=k) l=mid;else r=mid-1;}return l;}
}tree;
int main(){srand(time(NULL));scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}tree.build(1,1,n);for(int i=1;i<=m;i++){int op,l,r,k;scanf("%d%d%d",&op,&l,&r);if(op==1){scanf("%d",&k);printf("%d\n",tree.query(1,1,n,l,r,k,1)+1);}if(op==2){scanf("%d",&k);printf("%d\n",tree.middle(l,r,k));}if(op==3){tree.change(1,1,n,l,r);a[l]=r;}if(op==4){scanf("%d",&k);printf("%d\n",tree.query(1,1,n,l,r,k,2));}if(op==5){scanf("%d",&k);printf("%d\n",tree.query(1,1,n,l,r,k,3));}}return 0;
}
