[文章目录]
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;
}