P2596 [ZJOI2006]书架

admin · 发表于 2020-4-7 19:15:37

https://www.luogu.com.cn/problem/P2596

题目描述
小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语句你应该输出一行，一个数，代表询问的答案。

输入输出样例
输入 #1复制
10 10
1 3 2 7 5 8 10 4 9 6
Query 3
Top 5
Ask 6
Bottom 3
Ask 3
Top 6
Insert 4 -1
Query 5
Query 2
Ask 2
输出 #1复制
2
9
9
7
5
3
说明/提示
100%的数据，n,m <= 80000

admin · 发表于 2020-4-13 20:43:25

加上两种查询，因为一般的修改都相对较麻烦，查询会比较简单，这两个都很容易：
Ask S——询问编号为S的书的上面目前有多少本书。把S对应的下标q[S]，旋转到根后，输出它的左子树的sz
Query S——询问从上面数起的第S本书的编号。类似二分，设根的左子树的sz为l，右子树的sz为r的话，若l+1==s根为所求，s小的话去左边，s大的话去右边

int Ask(int S)
{
Splay(S,root);
int l=a[root].s[0];
return a[l].sz;
}
int Query(int rt, int S)
{
int l=a[a[rt].s[0]].sz;
if(l+1==S) return a[rt].val;
if(l+1>S) return Query(a[rt].s[0], S);
if(l+1<S) return Query(a[rt].s[1], S-(l+1));
}

复制代码

继续用上面的数据，每个轮询的查，没有发现问题，
看看我是如何相互验证的。

for (int i=1; i<=n; i++)
{
int x=Ask(q[i]); ///看看i是上面有几本书
cout<<x<<' ';
int y=Query(root,x+1);
cout<<y<<' '<<a[y].val<<endl;
}

复制代码

admin · 发表于 2020-4-7 19:19:53

读完题目的意思，显然可以使用BST来做。但是我喜欢先做一个粗暴的，试试树状数组记录前面如何？

admin · 发表于 2020-4-13 19:28:02

这是一个很基本很简单的SPLAY模板题，我以前见到过但是没有实际的写过，比他难得的多的都见过。周日晚上，我准备来写一个，同时记录下这个编程的过程：

admin · 发表于 2020-4-13 19:31:26

有很多种方法可以做这个题，数据规模不大，8W，这里我选择使用SPLAY。秀一把。
1、周日晚上上完网课后9-00，准备开始做题，很久没有做这种思路不复杂，细节有很多要注意的地方的题目，估算了一下，可能需要2-3小时。
2、读懂了测试数据，准备步步为营来做

admin · 发表于 2020-4-13 19:44:37

1、读懂题目之后做了一组1-20的二十个数的数据，准备把它每个数都查询一次，翻转一次，插入交换一次，求下位置，准备验算，因为这中题目联调会非常头疼，有必要在写的时候保证每个函数的正确性，否则一旦出错，调试将是可怕的。
2、因为是SPLAY，所以前面的ArrayPr，BSTPr()等函数还是写着，毕竟还不敢保证一写就能对。
3、初始状态不用SPLAY插入方式来做，因为旋转过多可能不好，采用类似线段树的递归建树模式。建成后打印时候打印输出，

#include<bits/stdc++.h>
using namespace std;
const int N=80100;
struct node
{
int val,fa,s[2],sz; ///s0s1左右儿子
} a[N];
int p[N],n,m, tot, root;
void ArrayPr() /// 调试监视使用
{
cout<<endl<<" i ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
cout<<endl<<"val ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
cout<<endl<<" s0 ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
cout<<endl<<" s1 ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
cout<<endl<<" sz ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
cout<<endl<<" fa ";
for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
cout<<endl;
}
void BSTPr(int rt) ///中序输出以rt为根的BST
{
if (a[rt].s[0]>0) BSTPr(a[rt].s[0]);
cout<<a[rt].val<<' ';
if (a[rt].s[1]>0) BSTPr(a[rt].s[1]);
}
int Build(int l,int r) ///前n个数直接建个满二叉树
{
if (l>r) return 0;
if (l==r)
{
a[l].val=p[l];
a[l].sz=1;
return l;
}
int m=(l+r)/2;
a[m].val=p[m];
int L=a[m].s[0]=Build(l,m-1);
int R=a[m].s[1]=Build(m+1,r);
a[L].fa=a[R].fa=m;
a[m].sz=a[L].sz+a[R].sz+1;
return m;
}
int main()
{
cin>>n;
for (int i=1; i<=n; i++)cin>>p[i];
tot=n;
root=Build(1,n);
///初始建树完毕
ArrayPr();
BSTPr(root);
return 0;
}
/*
20
1 3 2 7 5 8 10 4 9 6
11 13 12 17 15 18 14 19 16 20
*/

复制代码

admin · 发表于 2020-4-13 19:51:12

4、现在加入SPLAY部分，我的检查是把每个数字都查询一下，把他转到根，要是每个步骤都没错，估计旋转部分问题不大。

void pushup(int rt)
{
int l=a[rt].s[0], r=a[rt].s[1];
a[rt].sz=a[l].sz+a[r].sz+1;
}
int Son(int x)
{
int y=a[x].fa;
return a[y].s[1]==x;
}
void R(int x)
{
int y=a[x].fa;
int z=a[y].fa;
int k=Son(x);
int v=a[x].s[k^1];
a[y].s[k]=v,a[v].fa=y;
a[z].s[Son(y)]=x,a[x].fa=z;
a[x].s[k^1]=y,a[y].fa=x;
pushup(y),pushup(x);
}
void Splay(int x,int rt=root)
{
rt=a[rt].fa;
int y,z;
while(a[x].fa!=rt)
{
y=a[x].fa,z=a[y].fa;
if(z!=rt)
if(Son(x)==Son(y))R(y);
else R(x);
R(x);
}
if(rt==0)root=x;
}

复制代码

主程序加上循环的测试段：

for (int i=1; i<=n; i++)
{
cout<<endl<<i<<endl;
Splay(i,root);
ArrayPr();
BSTPr(root);
}

复制代码

测试了下，肉眼没有发现问题。最核心的部分完成了。

admin · 发表于 2020-4-13 20:02:19

现在开始按题目要求一个个的解决，先看第一个操作，Top(S)，把编号为S的书放在最上面，出问题了，哪本书的编号是S呢，总不能在val域中去查询吧？看来需要一个另外的数组，记录编号为S的书的起始位置，当然，这里就没有必要用什么map之类了，因为是一一对应的满射。加上数组q，q[i]表示编号为i的书对应的SPLAY的节点下标。
Top和Bottom的过程就是SPLAY的合并过程。以Top为例：
1、找到编号为S的点对应的节点x，把它旋转到根；
2、若x没有左子树，说明他已经是第一个，不用再处理；
3、设l为root的左子树，r为root的右子树，
4、在l子树中找最大的那个 p=l;while(a[p].s[0]>0) p=a[p].s[0];
5、把p旋到l的位置，这么来l就没有右子树了。
6、把r接到l的右儿子处。

admin · 发表于 2020-4-13 20:05:27

写出了这段代码，然后测试，把那20个数从最大的开始，每个都往顶上挪一次，最后形成了一个递增的序列。

void Top(int S)
{
Splay(S,root);
int x=root;
int l=a[x].s[0];
int r=a[x].s[1];///右儿子
if (r==0) a[x].s[1]=l;
else
{
int p=r;
///找最左节点
while (a[p].s[0]>0) p=a[p].s[0];
Splay(p,r);
a[p].s[0]=l;
a[l].fa=p;
pushup(p);
}
a[x].s[0]=0;
}

复制代码

加上了q数组，主程序里测试这段代码：

for (int i=1; i<=n; i++)
{
int x=q[i];///编号i对应的splay中的数组下标
Top(x);
cout<<endl;
BSTPr(root);
}

复制代码

运行结果很美观：

1 3 2 7 5 8 10 4 9 6 11 13 12 17 15 18 14 19 16 20
2 1 3 7 5 8 10 4 9 6 11 13 12 17 15 18 14 19 16 20
3 2 1 7 5 8 10 4 9 6 11 13 12 17 15 18 14 19 16 20
4 3 2 1 7 5 8 10 9 6 11 13 12 17 15 18 14 19 16 20
5 4 3 2 1 7 8 10 9 6 11 13 12 17 15 18 14 19 16 20
6 5 4 3 2 1 7 8 10 9 11 13 12 17 15 18 14 19 16 20
7 6 5 4 3 2 1 8 10 9 11 13 12 17 15 18 14 19 16 20
8 7 6 5 4 3 2 1 10 9 11 13 12 17 15 18 14 19 16 20
9 8 7 6 5 4 3 2 1 10 11 13 12 17 15 18 14 19 16 20
10 9 8 7 6 5 4 3 2 1 11 13 12 17 15 18 14 19 16 20
11 10 9 8 7 6 5 4 3 2 1 13 12 17 15 18 14 19 16 20
12 11 10 9 8 7 6 5 4 3 2 1 13 17 15 18 14 19 16 20
13 12 11 10 9 8 7 6 5 4 3 2 1 17 15 18 14 19 16 20
14 13 12 11 10 9 8 7 6 5 4 3 2 1 17 15 18 19 16 20
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 17 18 19 16 20
16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 17 18 19 20
17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 18 19 20
18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 19 20
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 20
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

admin · 发表于 2020-4-13 20:13:45

稍加修改变成Bottom，继续测试一下，就不写了，但是我自己中间有一个l和r写错了，幸亏通过这种方法检查出来了。

		自动登录	找回密码
密码			立即注册