二逼平衡树

link

原题就叫这名字，虽然我并没有看出来它二逼在哪里。

就是一个线段树套平衡树的模板，挺好理解也挺好写，除了手抖收获了一片RE之外一切都挺顺利的，开了\(O_2\)随便过【逃】。

#include
#include
#include
//#define zczc
using namespace std;
const int N=50010;
const int maxn=2147483647;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}
inline int min(int s1,int s2){
	return s11)return t[wh].num--,t[wh].sum--,wh;
			if(!lc&&!rc)return 0;
			wh=t[lc].p>t[rc].p?zig(wh):zag(wh);
		}
		if(val=val)return getmax(lc,val);
		else return max(t[wh].data,getmax(rc,val));
	}
	void dfs(int wh){
		if(!wh)return;
		printf("%d %d %d %d %d&%d\n",wh,t[wh].data,t[wh].num,t[wh].sum,lc,rc);
		dfs(lc);dfs(rc);
	}
	#undef lc
	#undef rc
}

//线段树部分
namespace b{
	#define lc (wh<<1)
	#define rc (wh<<1|1)
	#define mid (t[wh].l+t[wh].r>>1)
	struct node{
		int l,r,mi,ma,root;
	}t[N<<2];
	int ss[N],bef;bool dell;
	inline void pushup(int wh){
		t[wh].mi=min(t[lc].mi,t[rc].mi);
		t[wh].ma=max(t[lc].ma,t[rc].ma);
	}
	inline void build(int wh,int l,int r){
		t[wh].l=l,t[wh].r=r,t[wh].root=0;if(l==r)return;
		build(lc,l,mid);build(rc,mid+1,r);
	}
	inline void insert(int wh,int pl,int val){
		//if(wh==1)printf("working %d\n",val);
		//printf("%d %d %d %d %d\n",wh,t[wh].l,t[wh].r,pl,val);
		t[wh].root=a::insert(t[wh].root,val);
		if(t[wh].l==t[wh].r)bef=ss[t[wh].l],ss[t[wh].l]=val;//,printf("end%d\n",wh)
		else insert(pl<=mid?lc:rc,pl,val);
		
		if(dell)t[wh].root=a::del(t[wh].root,bef);
	}
	inline int rank(int wh,int wl,int wr,int val){
		if(wl<=t[wh].l&&t[wh].r<=wr)return a::rank(t[wh].root,val);
		int an=0;if(wl<=mid)an+=rank(lc,wl,wr,val);
		if(wr>mid)an+=rank(rc,wl,wr,val);return an;
	}
	inline int get(int wl,int wr,int rk){
		int l=-1,r=maxn,midd;
		while(l>1)mid)an=min(an,getmin(rc,wl,wr,val));return an;
	}
	inline int getmax(int wh,int wl,int wr,int val){
		if(wl<=t[wh].l&&t[wh].r<=wr)return a::getmax(t[wh].root,val);
		int an=-maxn;if(wl<=mid)an=max(an,getmax(lc,wl,wr,val));
		if(wr>mid)an=max(an,getmax(rc,wl,wr,val));return an;
	}
	#undef lc
	#undef rc
	#undef mid
} 

signed main(){
	
	#ifdef zczc
	freopen("in.txt","r",stdin);
	#endif
	
	srand(time(0));int m,n,op,s1,s2,s3;read(m);read(n);b::build(1,1,m);
	for(int i=1;i<=m;i++){read(s1);b::ss[i]=s1;b::insert(1,i,s1);}
	//a::dfs(b::t[1].root);
	b::dell=true;
	//printf("%d\n",b::rank(1,1,4,3));
	
	for(int i=1;i<=n;i++){
		//if(i%100==0)printf("now:%d\n",i);
		read(op);
		switch(op){
			case 1:
				read(s1);read(s2);read(s3);
				printf("%d\n",b::rank(1,s1,s2,s3)+1);break;
			case 2:
				read(s1);read(s2);read(s3);
				printf("%d\n",b::get(s1,s2,s3));break;
			case 3:
				read(s1);read(s2);b::insert(1,s1,s2);break;
			case 4:
				read(s1);read(s2);read(s3);
				printf("%d\n",b::getmax(1,s1,s2,s3));break;
			case 5:
				read(s1);read(s2);read(s3);
				printf("%d\n",b::getmin(1,s1,s2,s3));break;
		}
	}
	//*/
	
	return 0;
}