P3380 【模板】二逼平衡树（树套树）

1.93k，70行树状数组套权值线段树代码不来康康嘛~

#include<bits/stdc++.h>
#define IL inline
using namespace std;
const int N=5e4+3,Maxn=1e8+1,inf=2147483647;
int n,m,a[N],c1[N],c2[N],c3[N],rt[N],cnt[N<<9],ls[N<<9],rs[N<<9],num;
IL int in(){
	char c;int f=1;
	while((c=getchar())<'0'||c>'9')
	  if(c=='-') f=-1;
	int x=c-'0';
	while((c=getchar())>='0'&&c<='9')
	  x=x*10+c-'0';
	return x*f;
}
IL int low(int x){return x&-x;}
IL void golft(int *c){for(int i=1;i<=c[0];++i) c[i]=ls[c[i]];}
IL void gorig(int *c){for(int i=1;i<=c[0];++i) c[i]=rs[c[i]];}
IL int get_val(int *c){int res=0;for(int i=1;i<=c[0];++i) res+=cnt[ls[c[i]]];return res;}
IL void get(int x,int *c){c[0]=0;for(;x;x-=low(x)) c[++c[0]]=rt[x];}
void update(int &u,int l,int r,int v,int op){
	if(!u) u=++num;cnt[u]+=op;
	if(l==r) return;
	int mid=l+r>>1;
	if(v<=mid) update(ls[u],l,mid,v,op);
	else update(rs[u],mid+1,r,v,op);
}
IL void init(int x,int v){for(;x<=n;x+=low(x)) update(rt[x],0,Maxn,v,1);}
IL void change(int x,int v){for(int i=x;i<=n;i+=low(i)) update(rt[i],0,Maxn,a[x],-1);init(x,v),a[x]=v;} 
int rank(int L,int R,int v){
	int l=0,r=Maxn,res=0;get(L-1,c1),get(R,c2);
	while(l<r){
		int mid=l+r>>1;
		if(v<=mid) golft(c1),golft(c2),r=mid;
		else res+=get_val(c2)-get_val(c1),gorig(c1),gorig(c2),l=mid+1;
	}
	return res;
}
int kth(int L,int R,int k){
	int l=0,r=Maxn;get(L-1,c1),get(R,c2);
	while(l<r){
		int mid=l+r>>1,res=get_val(c2)-get_val(c1);
		if(res>=k) r=mid,golft(c1),golft(c2);
		else l=mid+1,k-=res,gorig(c1),gorig(c2);
	}
  return l;
}
int main()
{
	int l,r,k,op;
	n=in(),m=in();
	for(int i=1;i<=n;++i) init(i,a[i]=in());
	while(m--){
		op=in(),l=in(),r=in();
		if(op!=3) k=in();
		if(op==1) printf("%d
",rank(l,r,k)+1);
		else if(op==2) printf("%d
",kth(l,r,k));
		else if(op==3) change(l,r);
		else if(op==4){
			int res=rank(l,r,k);
			if(!res) printf("%d
",-inf);
			else printf("%d
",kth(l,r,res));
		}
		else{
			int res=rank(l,r,k+1);
			if(res==r-l+1) printf("%d
",inf);
			else printf("%d
",kth(l,r,res+1));
		}
	}
	return 0;
}