BZOJ-1861: [Zjoi2006]Book 书架

[文章目录]

Description

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

100%的数据,n,m < = 80000

理论上数组版的splay会简单很多,但是“自己选择的路,跪着也要走完”。

开一个指针数组就好了。。。

另外普及一下指针的内存占用是4个字节,但是new一个指针相当于开一个结构体。哈哈哈,一遍A2333。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 81000
int n,m,a[N];
char st[50];
struct node
{
 node *fa,*c[2];
 int val,size;
 node(int x);
 void push_up();
}*null =new node(0),*root,*tree[N];

node :: node(int x)
{
 fa=c[0]=c[1]=null;
 val=x;size=null?1:0;
}
void node :: push_up()
{
 size=c[0]->size+c[1]->size+1;
}
node* build(int l,int r)
{
 if(l>r) return null;
 int mid=l+r>>1;
 node *re=tree[a[mid]];//不再new,所以内存只多了一个指针
 re->c[0]=build(l,mid-1);re->c[1]=build(mid+1,r);
 re->c[0]->fa=re;re->c[1]->fa=re;
 re->push_up();
 return re;
}
void initialize()
{
 root=new node(0);
 root->c[1]=new node(0);
 root->c[1]->fa=root;
 root->c[1]->c[0]=build(1,n);
 root->c[1]->c[0]->fa=root->c[1];
 root->c[1]->push_up();root->push_up();
}
void rotate(node *x)
{
 node *y=x->fa;int l=(x!=y->c[0]),r=l^1;
 y->c[l]=x->c[r];x->c[r]->fa=y;
 x->c[r]=y;x->fa=y->fa;
 if(y==y->fa->c[l]) y->fa->c[l]=x;
 else y->fa->c[r]=x;
 y->fa=x;y->push_up();x->push_up();
 if(root==y) root=x;
}
void splay(node *x,node *tar)
{
 while(1)
 {
 node *y=x->fa,*z=y->fa;
 if(y==tar) break;
 if(z==tar){rotate(x);break;}
 if((x==y->c[0])^(y==z->c[0])==0) rotate(y);
 else rotate(x);
 rotate(x);
 }
}
void find(node *x,int y,node *z)
{
 while(1)
 {
 int tmp=x->c[0]->size;
 if(y<=tmp) x=x->c[0];
 else
 {
 y-=tmp+1;
 if(!y) break;
 x=x->c[1];
 }
 }
 splay(x,z);
}
int get_rank(node *x)
{
 int re=x->c[0]->size;
 for(;x!=root;x=x->fa)
 if(x==x->fa->c[1]) re+=x->fa->c[0]->size+1;
 return re;
}
void Delete(int x) 
{ 
 find(root,x,null); 
 find(root,x+2,root); 
 root->c[1]->c[0]=null;
 root->c[1]->push_up();
 root->push_up();
} 
void Insert(node *x,int y)
{
 find(root,y,null);
 find(root,y+1,root);
 root->c[1]->c[0]=x;
 x->fa=root->c[1];
 root->c[1]->push_up();root->push_up();
}
void Top()
{
 int s;scanf("%d",&s);
 int tmp=get_rank(tree[s]);
 Delete(tmp);
 Insert(tree[s],1);
}
void Bottom()//
{
 int s;scanf("%d",&s);
 int tmp=get_rank(tree[s]);
 Delete(tmp);
 Insert(tree[s],n);//
}
void In()
{
 int x,y;
 scanf("%d%d",&x,&y);if(y==0) return ;
 int tmp=get_rank(tree[x]);
 Delete(tmp);
 Insert(tree[x],tmp+y);
}
void Ask()
{
 int s; scanf("%d",&s);
 printf("%d\n",get_rank(tree[s])-1);
}
void Query()
{
 int s;scanf("%d",&s);
 find(root,s+1,null);
 printf("%d\n",root->val);
}
int main()
{
 scanf("%d%d",&n,&m);
 for(int i=1;i<=n;i++)
 {
 scanf("%d",&a[i]);
 tree[a[i]]=new node(a[i]);//
 }
 initialize();
 while(m--)
 {
 scanf("%s",st);
 switch(st[0])
 {
 case 'T':Top();break;
 case 'B':Bottom();break;
 case 'I':In();break;
 case 'A':Ask();break;
 case 'Q':Query();break;
 }
 }
 return 0;
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注