P2596 [ZJOI2006]书架 && Splay 区间操作(三)

时间:2021-06-13 07:14:27

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语句你应该输出一行,一个数,代表询问的答案。


我们在\(Splay\)区间操作(二)中提到过,有些操作若是完全基于基本操作,要进行需要大量的基本操作(\(Splay\))。

比如本题中的置顶操作:刚开始的想法是,把置顶的节点删除,在重新在序列首插入一个新的节点和原来的节点一样,这样需要上篇博客提到的 \(Remove\) 和 \(insert\)

操作,这样一波下来需要$Splay$5次!,造成常数过大。

事实上,我们可以依据要求操作的一些特性,合理的\(Splay\),达到相同的目的

其实,我们时常会移动一整颗树来达到目的,但是这样的话若是存在哨兵节点,会对我们的结果造成影响,(谢谢花)增加哨兵节点是完成某些特殊操作时需要的辅助节点(需要\(L - 1\) 和 \(R + 1\)),是为了保持树的结构。对于这题,我们其实没有必要加上哨兵节点(然而上一题就有必要)

\(Top\) 置顶

通过简略的推理 弱智都知道 ,当一个节点置顶时,当他为\(root\)时,其左子树为空,我们利用这一点,将某一元素置顶时,先把操作节点\(Splay\)到根,在把根的左子树全部移至操作节点的后继,较为巧妙的完成了置顶(加上最后的更新的\(Splay\)一共才两次,效率较高)

值得注意的是,因为没了哨兵节点,我们需要特判当前节点是否处在首端或末端 否则有玄学错误

void Top(){//左子树合并到后继
x = RD();
splay(pos[x], 0);
if(!ch[root][0])return ;
if(!ch[root][1]){ch[root][1] = ch[root][0], ch[root][0] = 0;return ;}
x = find(root, size[ch[root][0]] + 2);//后继
fa[ch[root][0]] = x;
ch[x][0] = ch[root][0];
ch[root][0] = 0;
splay(x, 0);
}

\(Bot\) 置底

同置顶,将操作节点\(Splay\)到根然后移花接木即可

void Bot(){//右子树合并到前驱
x = RD();
splay(pos[x], 0);
if(!ch[root][1])return ;
if(!ch[root][0]){ch[root][0] = ch[root][1],ch[root][1] = 0;return ;}
x = find(root, size[ch[root][0]]);//前驱
fa[ch[root][1]] = x;
ch[x][1] = ch[root][1];
ch[root][1] = 0;
splay(x, 0);
}

\(Ins\) 交换

观察可知,交换两点对树的结构没有影响,所以我们直接交换两点的数据(即代表的书编号和书映射在Splay树上的编号)即可

虽然交换两点不会改变树的结构,我们还是需要\(Splay\)操作节点到根来获取节点的\(rank\)

void Ins(){
x = pos[RD()];int d = RD();
if(!d)return ;
splay(x, 0);y = d == 1 ? find(root, size[ch[root][0]] + 2) : find(root, size[ch[root][0]]);
int cx = val[x], cy = val[y];
swap(val[x], val[y]);
swap(pos[cx], pos[cy]);
}

\(Ask\ \&\ Que\)

依据编号查询\(rank\)和依据\(rank\)查询编号

前者把操作节点\(Splay\)到根,左子树大小即为答案

后者直接上\(find\)函数查找即可

void Ask(){
x = RD();
splay(pos[x], 0);
printf("%d\n", size[ch[root][0]]);
}
void Que(){
x = RD();
printf("%d\n", val[find(root, x)]);
}

Code

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<climits>
typedef long long LL;
using namespace std;
int RD(){
int out = 0,flag = 1;char c = getchar();
while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}
while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}
return flag * out;
}
const int maxn = 100019,INF = 1e9;
int ch[maxn][2];
int val[maxn];
int size[maxn],pos[maxn];//pos用来表示某个值的位置
int fa[maxn];
int root, tot;
int New(int F, int v){
fa[++tot] = F;ch[tot][0] = ch[tot][1] = 0;
val[tot] = v;pos[v] = tot;
size[tot] = 1;
return tot;
}
void pushup(int id){size[id] = size[ch[id][0]] + size[ch[id][1]] + 1;}
bool lor(int id){return ch[fa[id]][0] == id ? 0 : 1;}
void spin(int id){
int F = fa[id],d = lor(id);
fa[id] = fa[F];
if(fa[F])ch[fa[F]][lor(F)] = id;
fa[F] = id;
ch[F][d] = ch[id][d ^ 1];
if(ch[F][d])fa[ch[F][d]] = F;
ch[id][d ^ 1] = F;
pushup(F), pushup(id);
}
void splay(int id, int goal){
while(fa[id] != goal){
int F = fa[id];
if(fa[F] == goal)spin(id);
else if(lor(id) ^ lor(F))spin(id), spin(id);
else spin(F), spin(id);
}
if(!goal)root = id;
}
int find(int id, int rank){//寻找rank - 1
if(size[ch[id][0]] >= rank)return find(ch[id][0], rank);
else if(size[ch[id][0]] + 1 == rank)return id;
else return find(ch[id][1], rank - size[ch[id][0]] - 1);
}
void insert(int v){
ch[root][1] = New(root, v);
splay(pos[v], 0);
}
int num, nr;
int x, y;
void Top(){//左子树合并到后继
x = RD();
splay(pos[x], 0);
if(!ch[root][0])return ;
if(!ch[root][1]){ch[root][1] = ch[root][0], ch[root][0] = 0;return ;}
x = find(root, size[ch[root][0]] + 2);//后继
fa[ch[root][0]] = x;
ch[x][0] = ch[root][0];
ch[root][0] = 0;
splay(x, 0);
}
void Bot(){//右子树合并到前驱
x = RD();
splay(pos[x], 0);
if(!ch[root][1])return ;
if(!ch[root][0]){ch[root][0] = ch[root][1],ch[root][1] = 0;return ;}
x = find(root, size[ch[root][0]]);//前驱
fa[ch[root][1]] = x;
ch[x][1] = ch[root][1];
ch[root][1] = 0;
splay(x, 0);
}
void Ins(){
x = pos[RD()];int d = RD();
if(!d)return ;
splay(x, 0);y = d == 1 ? find(root, size[ch[root][0]] + 2) : find(root, size[ch[root][0]]);
int cx = val[x], cy = val[y];
swap(val[x], val[y]);
swap(pos[cx], pos[cy]);
}
void Ask(){
x = RD();
splay(pos[x], 0);
printf("%d\n", size[ch[root][0]]);
}
void Que(){
x = RD();
printf("%d\n", val[find(root, x)]);
}
int main(){
num = RD(); nr = RD();
root = New(0, RD());
for(int i = 2;i <= num;i++)insert(RD());
char cmd[maxn];
for(int i = 1;i <= nr;i++){
cin>>cmd;
if(cmd[0] == 'T')Top();
else if(cmd[0] == 'B')Bot();
else if(cmd[0] == 'I')Ins();
else if(cmd[0] == 'A')Ask();
else Que();
}
return 0;
}