![洛谷 P2596 [ZJOI2006]书架 解题报告](/0.jpg)
P2596 [ZJOI2006]书架
题目描述
小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本书的编号。
输出格式：
对于每一条Ask或Query语句你应该输出一行，一个数，代表询问的答案。
说明
100%的数据，n,m <= 80000
这是我做的第一道非板子的平衡树题目，写+调大概花了2个小时，稍稍有点困，先以时间压到1个小时为目标了。
很显然，这颗平衡树是一颗区间树，用来平衡的域是书的相对位置大小，我们用树的大小信息来查询某个点在书架的相对位置，而不去直接存储这个相对位置以比较，这应该是区间树的一个重要特点。
用\(pos[i]\)维护编号为\(i\)的书对应哪个节点。
对于操作：
放在最上面/下面就先删掉然后加点
添加的话只有两个情况，就先把要添加的节点伸展到根，然后和它的前驱/后继交换即可
两个询问互为逆操作，有关排名的
#include
#include
#define ls t[now].ch[0]
#define rs t[now].ch[1]
#define f t[now].par
#define s t[now].ch[typ]
using namespace std;
const int N=160010;
struct Splay
{
int ch[2],par,siz,num;
}t[N];
int root,tot=0,n,m,x,a[N],pos[N];//编号为i的书对应的当前点的编号
string S;
int identity(int now)
{
return t[f].ch[1]==now;
}
void connect(int fa,int now,int typ)
{
f=fa;
t[fa].ch[typ]=now;
}
void updata(int now)
{
t[now].siz=t[ls].siz+t[rs].siz+1;
}
void rotate(int now)
{
int p=f,typ=identity(now);
connect(p,t[now].ch[typ^1],typ);
connect(t[p].par,now,identity(p));
connect(now,p,typ^1);
updata(p),updata(now);
}
void splay(int now,int to)
{
to=t[to].par;
for(int typ;f!=to;rotate(now))
if(t[f].par!=to)
rotate(identity(now)==identity(f)?f:now);
if(!to) root=now;
}
int New(int dat)
{
t[++tot].num=dat;t[tot].siz=1;return tot;
}
void free(int now)
{
t[now].num=0;t[now].siz=0;t[now].par=0;ls=0;rs=0;
if(tot==now) tot--;
}
void find(int x)//当前排名为x的书的编号
{
int now=root;
while(t[ls].siz+1!=x)
now=t[now].ch[t[ls].siz+1 splay(now,root); printf("%d\n",t[now].num); } int get_max(int now,int typ) { if(typ) t[now].siz++; return rs?get_max(rs,typ):now; } int get_min(int now,int typ) { if(typ) t[now].siz++; return ls?get_min(ls,typ):now; } void extrack(int now)//删除编号为now的点 { splay(now,root); if(!ls){root=rs;connect(0,root,1);free(now);return;} int rt=get_max(ls,0); splay(rt,ls); connect(rt,rs,1); connect(0,rt,1); updata(rt); root=rt; free(now); } void rank(int now) { splay(now,root); printf("%d\n",t[ls].siz); } void top(int now,int num)//节点编号和书的编号 { extrack(now); int fa=get_min(root,1); connect(fa,now=New(num),0); pos[num]=now; updata(now); } void bottom(int now,int num) { extrack(now); int fa=get_max(root,1); connect(fa,now=New(num),1); pos[num]=now; updata(now); } void exchange(int to,int now) { swap(pos[t[to].num],pos[t[now].num]); swap(t[to].num,t[now].num); } void insert(int now,int T) { if(!T) return; splay(now,root); if(T==1) exchange(get_min(rs,0),now); else exchange(get_max(ls,0),now); } int build(int l,int r,int fa) { if(l>r) return 0; int now=l+r>>1; t[now].par=fa; t[now].num=a[now]; updata(now); if(l==r) return now; ls=build(l,now-1,now); rs=build(now+1,r,now); updata(now); return now; } /*void write(int now) { if(!now) return; write(ls); printf("%d ",t[now].num); write(rs); }*/ int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",a+i); pos[a[i]]=i; } connect(0,root=build(1,n,0),1); tot=n; for(int i=1;i<=m;i++) { cin>>S; scanf("%d",&x); if(S=="Top") top(pos[x],x); else if(S=="Bottom") bottom(pos[x],x); else if(S=="Insert") { int T;scanf("%d",&T); insert(pos[x],T); } else if(S=="Ask") rank(pos[x]); else find(x); //write(root); //printf("%d\n"); } return 0; } 2018.6.14