20161111

BZOJ3224 普通平衡树|treap

//BZOJ 3224//by Cydiater//2016.11.11#include <iostream>#include <cstring>#include <string>#include <algorithm>#include <queue>#include <map>#include <ctime>#include <cmath>#include <cstdlib>#include <cstdio>#include <iomanip>#include <bitset>#include <set>using namespace std;#define ll long long#define up(i,j,n)		for(int i=j;i<=n;i++)#define down(i,j,n)		for(int i=j;i>=n;i--)#define cmax(a,b)		a=max(a,b)#define cmin(a,b)		a=min(a,b)const int MAXN=1e5+5;const int oo=0x3f3f3f3f;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int N,root=0,opt,tol=0;struct tree{	int leftt,rightt,rnd,v,siz,cnt;}t[MAXN];namespace solution{	inline void updata(int k){t[k].siz=t[t[k].leftt].siz+t[t[k].rightt].siz+t[k].cnt;}	void lefturn(int &k){		int tmp=t[k].rightt;t[k].rightt=t[tmp].leftt;t[tmp].leftt=k;		t[tmp].siz=t[k].siz;updata(k);k=tmp;	}	void righturn(int &k){		int tmp=t[k].leftt;t[k].leftt=t[tmp].rightt;t[tmp].rightt=k;		t[tmp].siz=t[k].siz;updata(k);k=tmp;	}	void insert(int &k,int num){		if(k==0){			k=++tol;t[tol].leftt=t[tol].rightt=0;			t[tol].rnd=rand();t[tol].v=num;t[tol].siz=t[tol].cnt=1;			return;		}		t[k].siz++;		if(num==t[k].v)t[k].cnt++;		else if(num>t[k].v){			insert(t[k].rightt,num);			if(t[t[k].rightt].rnd<t[k].rnd)lefturn(k);		}else{			insert(t[k].leftt,num);			if(t[t[k].leftt].rnd<t[k].rnd)righturn(k);		}	}	void del(int &k,int num){		if(k==0)	return;		if(t[k].v==num){			if(t[k].cnt>1){t[k].cnt--;t[k].siz--;return;}			if(t[k].leftt*t[k].rightt==0)k=t[k].leftt+t[k].rightt;			else if(t[t[k].rightt].rnd>t[t[k].leftt].rnd){				lefturn(k);del(k,num);			}else{				righturn(k);del(k,num);			}		}else if(num>t[k].v){			t[k].siz--;			del(t[k].rightt,num);		}else{			t[k].siz--;			del(t[k].leftt,num);		}	}	int getrank(int k,int num){		if(t[k].v==num)		return 1+t[t[k].leftt].siz;		else if(num>t[k].v)	return t[t[k].leftt].siz+t[k].cnt+getrank(t[k].rightt,num);		else 				return getrank(t[k].leftt,num);	}	int getnum(int k,int rnk){		if(rnk>t[t[k].leftt].siz+t[k].cnt)	return getnum(t[k].rightt,rnk-(t[t[k].leftt].siz+t[k].cnt));		else if(rnk>t[t[k].leftt].siz)		return t[k].v;		else 								return getnum(t[k].leftt,rnk);	}	int pre(int k,int num){		if(k==0)			return -1;						if(t[k].v>=num)		return pre(t[k].leftt,num);		else 				return max(pre(t[k].rightt,num),t[k].v);	}	int nxt(int k,int num){		if(k==0)			return oo;		if(t[k].v<=num)		return nxt(t[k].rightt,num);		else 				return min(nxt(t[k].leftt,num),t[k].v);	}	void slove(){		root=0;N=read();		while(N--){			opt=read();int num=read();			if(opt==1)insert(root,num);			if(opt==2)del(root,num);			if(opt==3)printf("%d\n",getrank(root,num));			if(opt==4)printf("%d\n",getnum(root,num));			if(opt==5)printf("%d\n",pre(root,num));			if(opt==6)printf("%d\n",nxt(root,num));		}	}}int main(){	//freopen("input.in","r",stdin);	//freopen("out.out","w",stdout);	using namespace solution;	slove();	return 0;}

模板复习计划