BZOJ_1861_[Zjoi2006]Book 书架

BZOJ_1861_[Zjoi2006]Book 书架_splay

题意：

小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本书上面就只可能有X-1、X或X+1本书。当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小T会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。久而久之，小T的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：(1)编号为X的书在书柜的什么位置；(2)从上到下第i本书的编号是多少。

第一行有两个数n，m，分别表示书的个数以及命令的条数；第二行为n个正整数：第i个数表示初始时从上至下第i个位置放置的书的编号；第三行到m+2行，每行一条命令。命令有5种形式： 1． Top S——表示把编号为S的书房在最上面。 2． Bottom S——表示把编号为S的书房在最下面。 3． Insert S T——T∈{-1，0，1}，若编号为S的书上面有X本书，则这条命令表示把这本书放回去后它的上面有X+T本书； 4． Ask S——询问编号为S的书的上面目前有多少本书。 5． Query S——询问从上面数起的第S本书的编号。

分析：

top：splay到根上，把左子树丢到后继那里

bottom：splay到根上，把右子树丢到前驱那里

insert：splay到根上，交换根和前驱/后继的信息即可

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define ls ch[p][0]

#define rs ch[p][1]

#define get(x) (ch[f[x]][1]==x)

#define N 80050

int ch[N][2],f[N],siz[N],a[N],w[N],val[N],rt,n,m;

char opt[10];

void pushup(int p){ if(p)siz[p]=siz[ls]+siz[rs]+1; }

void rotate(int x)

{

	int y=f[x],z=f[y],k=get(x);

	ch[y][k]=ch[x][!k];f[ch[y][k]]=y;

	ch[x][!k]=y;f[y]=x;f[x]=z;

	if(z) ch[z][ch[z][1]==y]=x;

	pushup(y);pushup(x);if(rt==y)rt=x;

}

void splay(int x,int y)

{

	for(int fa;(fa=f[x])!=y;rotate(x))

		if(f[fa]!=y)

			rotate((get(x)==get(fa)) ? fa : x);

}

int pre()

{

	int p=ch[rt][0];

	while(rs)p=rs;

	return p;

}

int nxt()

{

	int p=ch[rt][1];

	while(ls)p=ls;

	return p;

}

int find(int x)

{

	int p=rt;

	while(1)

	{

		if(x<=siz[ls])p=ls;

		else{

			x-=siz[ls]+1;

			if(!x)return p;

			p=rs;

		}

	}

}

void build(int fa,int l,int r,bool flg)

{

	if(l>r)return ;

	int mid=l+r>>1;

	ch[fa][flg]=mid;

	f[mid]=fa;

	val[mid]=a[mid];

	w[a[mid]]=mid;

	siz[mid]=1;

	build(mid,l,mid-1,0);

	build(mid,mid+1,r,1);

	pushup(mid);

}

void print(){

	int p;

	for(int i=1;i<=n;i++)p=find(i),printf("p=%d, val[p]=%d\n",p,val[p]);

}

void top(int p)

{

	splay(p,0);

	if(!ls)return ;

	if(!rs){

		rs=ls;ls=0;return ;

	}

	int nx=nxt();

	ch[nx][0]=ls;

	f[ls]=nx;

	ch[p][0]=0;

	pushup(ch[nx][0]);

	splay(ch[nx][0],0);

	//print();

}

void bottom(int p)

{

	splay(p,0);

	if(!rs)return ;

	if(!ls){

		ls=rs;rs=0;return ;

	}

	int pr=pre();

	ch[pr][1]=rs;

	f[rs]=pr;

	ch[p][1]=0;

	pushup(ch[pr][1]);

	splay(ch[pr][1],0);

	//print();

}

void up(int p)

{

	splay(p,0);

	int pr=pre();

	swap(val[p],val[pr]);

	swap(w[val[p]],w[val[pr]]);

	/*int prlson=ch[pr][0];

	f[ls]=f[rs]=pr;

	ch[pr][0]=ls;

	ch[pr][1]=rs;

	rs=0;ls=prlson;

	f[p]=f[pr];

	f[pr]=0;

	ch[0][0]=pr;

	ch[f[p]][1]=p;

	pushup(p);

	splay(p,0);*/

}

void down(int p)

{

	splay(p,0);

	int nx=nxt();

	swap(val[p],val[nx]);

	swap(w[val[p]],w[val[nx]]);

	/*nt nxrson=ch[nx][1];

	f[ls]=f[rs]=nx;

	ch[nx][0]=ls;

	ch[nx][1]=rs;

	ls=0;rs=nxrson;

	f[p]=f[nx];

	f[nx]=0;

	ch[0][0]=nx;

	ch[f[p]][0]=p;

	pushup(p);

	splay(p,0);*/

}

void ask(int p)

{

	splay(p,0);

	printf("%d\n",siz[ls]);

}

int main()

{

	scanf("%d%d",&n,&m);

	int i,x,y;

	for(i=1;i<=n;i++) scanf("%d",&a[i]);

	build(0,1,n,0);

	rt=n+1>>1;

	//print();

	for(i=1;i<=m;i++) {

		scanf("%s%d",opt,&x);

		if(opt[0]=='T') top(w[x]);

		else if(opt[0]=='B') bottom(w[x]);

		else if(opt[0]=='I'){

			scanf("%d",&y);

			if(y==1)down(w[x]);

			if(y==-1)up(w[x]);

		}else if(opt[0]=='A') ask(w[x]);

		else printf("%d\n",val[find(x)]);

	}

}

巴特西

BZOJ_1861_[Zjoi2006]Book 书架_splay

最新文章

热门文章