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;
}