[TYVJ1730]二逼平衡树 - wumingshi - 435185

记录编号	435185	评测结果	AAAAAAAAAA
题目名称	[TYVJ1730]二逼平衡树	最终得分	100
用户昵称	wumingshi	是否通过	通过
代码语言	C++	运行时间	2.307 s
提交时间	2017-08-09 10:25:37	内存使用	47.04 MiB
显示代码纯文本
#include<cstdio>
#include<iostream>
using namespace std;
const int N=50005;
struct node
{
	int size,num,sum;
	node *ch[2],*fa;
	inline int getwh()
	{
		return fa->ch[0]==this?0:1;
	}
	inline void update()
	{
		size=ch[0]->size+ch[1]->size+sum;
	}
	inline void setch(int wh,node *child);
}pool[2000005],*null,*t[N<<2];
inline void node::setch(int wh,node *child)
{
	ch[wh]=child;
	if(child!=null) child->fa=this;
	update();
}
int a[N];
int n,m,opt,x,y,z,tot;
inline node *getnew(int value)
{
	node *now=pool+ ++tot;
	now->ch[0]=now->ch[1]=now->fa=null;
	now->num=value;
	now->size=now->sum=1;
	return now;
}
inline void rotate(node *&now)
{
	node *fa=now->fa,*grand=fa->fa;
	int wh=now->getwh();
	fa->setch(wh,now->ch[wh^1]);
	now->setch(wh^1,fa);
	now->fa=grand;
	if(grand!=null) grand->ch[grand->ch[0]==fa?0:1]=now;
}
inline void splay(node *now,node *tar,node *&root)
{
	for(;now->fa!=tar;rotate(now))
	  if(now->fa->fa!=tar) now->getwh()==now->fa->getwh()?rotate(now->fa):rotate(now);
	if(tar==null) root=now;
}
inline void insert(int value,node *&root)
{
	node *now=root,*last=null;
	while(now!=null)
	{
		last=now;
		if(now->num==value) return now->sum++,now->size++,splay(now,null,root);
		if(now->num>value) now=now->ch[0];
		else now=now->ch[1];
	}
	if(last==null)
	{
		root=getnew(value);
		return;
	}
	now=getnew(value);
	if(last->num>value) last->setch(0,now);
	else last->setch(1,now);
	splay(now,null,root);
}
inline node *find(int value,node *&root)
{
	node *now=root;
	while(now!=null)
	{
		if(now->num==value)
		{
			splay(now,null,root);
			return now;
		}
		if(now->num>value) now=now->ch[0];
		else now=now->ch[1];
	}
}
inline void del(int value,node *&root)
{
	node *now=find(value,root);
	if(now->sum>1)
	{
		now->sum--;
		now->size--;
		return;
	}
	if(now->ch[0]==null&&now->ch[1]==null)
	{
		root=null;
		return;
	}
	if(now->ch[0]==null)
	{
		root=now->ch[1];
		now->ch[1]->fa=null;
		return;
	}
	if(now->ch[1]==null)
	{
		root=now->ch[0];
		now->ch[0]->fa=null;
		return;
	}
	node *pre=now->ch[0];
	while(pre->ch[1]!=null) pre=pre->ch[1];
	splay(pre,now,root);
	pre->setch(1,now->ch[1]);
	pre->fa=null;
	root=pre;
}
inline int rank(int value,node *&root)
{
	int ranking=0;
	node *now=root;
	while(now!=null)
	{
		if(now->num==value)
		{
			ranking+=now->ch[0]->size;
			splay(now,null,root);
			return ranking;
		}
		if(now->num>value) now=now->ch[0];
		else ranking+=now->ch[0]->size+now->sum,now=now->ch[1];
	}
	return ranking;
}
inline void change(int value,int num,node *&root)
{
	del(value,root);
	insert(num,root);
}
inline int pre(int value,node *&root)
{
	node *now=root;
	int ans=-2147483647;
	while(now!=null)
	  if(now->num>=value) now=now->ch[0];
	  else ans=max(ans,now->num),now=now->ch[1];
	return ans;
}
inline int nxt(int value,node *&root)
{
	node *now=root;
	int ans=2147483647;
	while(now!=null)
	  if(now->num<=value) now=now->ch[1];
	  else ans=min(ans,now->num),now=now->ch[0];
	return ans;
}
inline void init(int l,int r,node *&root)
{
	root=null;
	for(int i=l;i<=r;i++)
	  insert(a[i],root);
}
inline void build(int l,int r,int now)
{
	init(l,r,t[now]);
	if(l==r) return;
	int mid=(l+r)>>1;
	build(l,mid,now<<1);
	build(mid+1,r,now<<1|1);
}
inline int askrank(int L,int R,int l,int r,int now,int num)
{
	if(L<=l&&r<=R) return rank(num,t[now]);
	int mid=(l+r)>>1,ans=0;
	if(L<=mid) ans=askrank(L,R,l,mid,now<<1,num);
	if(R>mid) ans+=askrank(L,R,mid+1,r,now<<1|1,num);
	return ans;
}
inline int askkth(int L,int R,int num)
{
	int l=0,r=1e8+1,mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(askrank(L,R,1,n,1,mid)>=num) r=mid;
		else l=mid+1;
	}
	return l-1;
}
inline void changenum(int p,int l,int r,int now,int num)
{
	change(a[p],num,t[now]);
	if(l==r) return;
	int mid=(l+r)>>1;
	if(p<=mid) return changenum(p,l,mid,now<<1,num);
	changenum(p,mid+1,r,now<<1|1,num);
}
inline int askpre(int L,int R,int l,int r,int now,int num)
{
	if(L<=l&&r<=R) return pre(num,t[now]);
	int mid=(l+r)>>1,ans=-2147483647;
	if(L<=mid) ans=askpre(L,R,l,mid,now<<1,num);
	if(R>mid) ans=max(ans,askpre(L,R,mid+1,r,now<<1|1,num));
	return ans;
}
inline int asknxt(int L,int R,int l,int r,int now,int num)
{
	if(L<=l&&r<=R) return nxt(num,t[now]);
	int mid=(l+r)>>1,ans=2147483647;
	if(L<=mid) ans=asknxt(L,R,l,mid,now<<1,num);
	if(R>mid) ans=min(ans,asknxt(L,R,mid+1,r,now<<1|1,num));
	return ans;
}
int main()
{
	freopen("psh.in","r",stdin);
	freopen("psh.out","w",stdout);
	null=pool;
	null->ch[0]=null->ch[1]=null->fa=null;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	  scanf("%d",&a[i]);
	build(1,n,1);
	while(m--)
	{
		scanf("%d",&opt);
		if(opt==1) scanf("%d%d%d",&x,&y,&z),printf("%d\n",askrank(x,y,1,n,1,z)+1);
		else if(opt==2) scanf("%d%d%d",&x,&y,&z),printf("%d\n",askkth(x,y,z));
		else if(opt==3) scanf("%d%d",&x,&y),changenum(x,1,n,1,y),a[x]=y;
		else if(opt==4) scanf("%d%d%d",&x,&y,&z),printf("%d\n",askpre(x,y,1,n,1,z));
		else scanf("%d%d%d",&x,&y,&z),printf("%d\n",asknxt(x,y,1,n,1,z));
	}
	return 0;
}