华师一附中OI组

标题: P2596 [ZJOI2006]书架 [打印本页]
作者: admin    时间: 2020-4-7 19:15
标题: P2596 [ZJOI2006]书架
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-7 19:19
读完题目的意思，显然可以使用BST来做。但是我喜欢先做一个粗暴的，试试树状数组记录前面如何？
作者: admin    时间: 2020-4-13 19:28
这是一个很基本很简单的SPLAY模板题，我以前见到过但是没有实际的写过，比他难得的多的都见过。周日晚上，我准备来写一个，同时记录下这个编程的过程：
作者: admin    时间: 2020-4-13 19:31
有很多种方法可以做这个题，数据规模不大，8W，这里我选择使用SPLAY。秀一把。
1、周日晚上上完网课后9-00，准备开始做题，很久没有做这种思路不复杂，细节有很多要注意的地方的题目，估算了一下，可能需要2-3小时。
2、读懂了测试数据，准备步步为营来做
作者: admin    时间: 2020-4-13 19:44
1、读懂题目之后做了一组1-20的二十个数的数据，准备把它每个数都查询一次，翻转一次，插入交换一次，求下位置，准备验算，因为这中题目联调会非常头疼，有必要在写的时候保证每个函数的正确性，否则一旦出错，调试将是可怕的。
2、因为是SPLAY，所以前面的ArrayPr，BSTPr()等函数还是写着，毕竟还不敢保证一写就能对。
3、初始状态不用SPLAY插入方式来做，因为旋转过多可能不好，采用类似线段树的递归建树模式。建成后打印时候打印输出，


  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=80100;
  4. struct node
  5. {
  6.         int val,fa,s[2],sz;  ///s0s1左右儿子
  7. } a[N];
  8. int p[N],n,m, tot, root;
  9. void ArrayPr()   /// 调试监视使用
  10. {
  11.         cout<<endl<<"  i ";
  12.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
  13.         cout<<endl<<"val ";
  14.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
  15.         cout<<endl<<" s0 ";
  16.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
  17.         cout<<endl<<" s1 ";
  18.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
  19.         cout<<endl<<" sz ";
  20.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
  21.         cout<<endl<<" fa ";
  22.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
  23.         cout<<endl;
  24. }
  25. void BSTPr(int rt)   ///中序输出以rt为根的BST
  26. {
  27.         if (a[rt].s[0]>0)  BSTPr(a[rt].s[0]);
  28.         cout<<a[rt].val<<' ';
  29.         if (a[rt].s[1]>0)  BSTPr(a[rt].s[1]);
  30. }
  31. int Build(int l,int r) ///前n个数直接建个满二叉树
  32. {
  33.         if (l>r) return 0;
  34.         if (l==r)
  35.                 {
  36.                         a[l].val=p[l];
  37.                         a[l].sz=1;
  38.                         return l;
  39.                 }
  40.         int m=(l+r)/2;
  41.         a[m].val=p[m];
  42.         int L=a[m].s[0]=Build(l,m-1);
  43.         int R=a[m].s[1]=Build(m+1,r);
  44.         a[L].fa=a[R].fa=m;
  45.         a[m].sz=a[L].sz+a[R].sz+1;
  46.         return m;
  47. }
  48. int main()
  49. {
  50.         cin>>n;
  51.         for (int i=1; i<=n; i++)cin>>p[i];
  52.         tot=n;
  53.         root=Build(1,n);


  56.         ///初始建树完毕
  57.         ArrayPr();
  58.         BSTPr(root);
  59.         
  60.         return 0;
  61. }
  62. /*
  63. 20
  64. 1 3 2 7 5 8 10 4 9 6
  65. 11 13 12 17 15 18 14 19 16 20
  66. */
复制代码
作者: admin    时间: 2020-4-13 19:51
4、现在加入SPLAY部分，我的检查是把每个数字都查询一下，把他转到根，要是每个步骤都没错，估计旋转部分问题不大。

  1. void pushup(int rt)  
  2. {
  3.         int l=a[rt].s[0], r=a[rt].s[1];
  4.         a[rt].sz=a[l].sz+a[r].sz+1;
  5. }
  6. int Son(int x)
  7. {
  8.         int y=a[x].fa;
  9.         return  a[y].s[1]==x;
  10. }
  11. void R(int x)
  12. {
  13.         int y=a[x].fa;
  14.         int z=a[y].fa;
  15.         int k=Son(x);
  16.         int v=a[x].s[k^1];
  17.         a[y].s[k]=v,a[v].fa=y;
  18.         a[z].s[Son(y)]=x,a[x].fa=z;
  19.         a[x].s[k^1]=y,a[y].fa=x;
  20.         pushup(y),pushup(x);
  21. }
  22. void Splay(int x,int rt=root)
  23. {
  24.         rt=a[rt].fa;
  25.         int y,z;
  26.         while(a[x].fa!=rt)
  27.                 {
  28.                         y=a[x].fa,z=a[y].fa;
  29.                         if(z!=rt)
  30.                                 if(Son(x)==Son(y))R(y);
  31.                                 else R(x);
  32.                         R(x);
  33.                 }
  34.         if(rt==0)root=x;
  35. }
复制代码


主程序加上循环的测试段：
  1. for (int i=1; i<=n; i++)
  2.                 {
  3.                         cout<<endl<<i<<endl;
  4.                         Splay(i,root);
  5.                         ArrayPr();
  6.                         BSTPr(root);
  7.                 }
复制代码


测试了下，肉眼没有发现问题。最核心的部分完成了。
作者: admin    时间: 2020-4-13 20:02
现在开始按题目要求一个个的解决，先看第一个操作，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
写出了这段代码，然后测试，把那20个数从最大的开始，每个都往顶上挪一次，最后形成了一个递增的序列。

  2. void Top(int S)
  3. {
  4.         Splay(S,root);
  5.         int  x=root;
  6.         int l=a[x].s[0];
  7.         int r=a[x].s[1];///右儿子
  8.         if (r==0) a[x].s[1]=l;
  9.         else
  10.                 {
  11.                         int p=r;
  12.                         ///找最左节点
  13.                         while (a[p].s[0]>0) p=a[p].s[0];
  14.                         Splay(p,r);
  15.                         a[p].s[0]=l;
  16.                         a[l].fa=p;
  17.                         pushup(p);
  18.                 }
  19.         a[x].s[0]=0;
  20. }
复制代码


加上了q数组，主程序里测试这段代码：
  1.         for (int i=1; i<=n; i++)
  2.                 {
  3.                         int x=q[i];///编号i对应的splay中的数组下标
  4.                         Top(x);
  5.                         cout<<endl;
  6.                         BSTPr(root);
  7.                 }
复制代码



运行结果很美观：

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
稍加修改变成Bottom，继续测试一下 ，就不写了，但是我自己中间有一个l和r写错了，幸亏通过这种方法检查出来了。
作者: admin    时间: 2020-4-13 20:43
加上两种查询，因为一般的修改都相对较麻烦，查询会比较简单，这两个都很容易：
Ask S——询问编号为S的书的上面目前有多少本书。把S对应的下标q[S]，旋转到根后，输出它的左子树的sz
Query S——询问从上面数起的第S本书的编号。类似二分，设根的左子树的sz为l，右子树的sz为r的话，若l+1==s根为所求，s小的话去左边，s大的话去右边

  1. int Ask(int S)
  2. {
  3.         Splay(S,root);
  4.         int l=a[root].s[0];
  5.         return a[l].sz;
  6. }

  8. int Query(int rt, int S)
  9. {
  10.         int l=a[a[rt].s[0]].sz;  
  11.         if(l+1==S) return a[rt].val;
  12.         if(l+1>S) return Query(a[rt].s[0], S);
  13.         if(l+1<S) return Query(a[rt].s[1], S-(l+1));
  14. }
复制代码



继续用上面的数据，每个轮询的查，没有发现问题，
看看我是如何相互验证的。
  1.         for (int i=1; i<=n; i++)
  2.                 {
  3.                 int x=Ask(q[i]); ///看看i是上面有几本书
  4.                 cout<<x<<' ';
  5.                 int y=Query(root,x+1);
  6.                 cout<<y<<' '<<a[y].val<<endl;
  7.                  
  8.                 }
复制代码
作者: admin    时间: 2020-4-13 20:57
剩下的这个插入我做了一个多小时，思路其实很简单，T==0的话不做任何操作，T==1的话把它和他的后继进行交换，T==-1的话和前驱进行交换。我在写的时候
  1. swap(a[x].val,a[q[S]].val);
  2. swap(q[a[x].val],q[S]);
复制代码

没有意识到错误，调了很长的时间。最后用了直观的方法，
  1.      cin>>S>>T;
  2.               int x;
  3.               if (T!=0)
  4.                     {
  5.                            if (T==-1)x=Pre(q[S]);
  6.                            if (T== 1)x=Suc(q[S]);
  7.                                     
  8.                            ///这两个交换我曾经搞糊涂了
  9.                            int v=a[x].val;
  10.                            swap(a[x].val,a[q[S]].val);
  11.                            swap(q[v],q[S]);
  12.                      }
复制代码


作者: admin    时间: 2020-4-13 21:01
最后奉上我的程序，前前后后3个多小时，丢人
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int inf=99999999;
  4. const int N=80100;
  5. struct node
  6. {
  7.         int val,fa,s[2],sz;  ///s0s1左右儿子
  8. } a[N];
  9. int p[N],q[N],n,m, tot, root;
  10. void ArrayPr()   /// 调试监视使用
  11. {
  12.         cout<<endl<<"  i ";
  13.         for (int i=1; i<=tot; i++) cout<<setw(3)<<i;
  14.         cout<<endl<<"val ";
  15.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].val;
  16.         cout<<endl<<" s0 ";
  17.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[0];
  18.         cout<<endl<<" s1 ";
  19.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].s[1];
  20.         cout<<endl<<" sz ";
  21.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].sz;
  22.         cout<<endl<<" fa ";
  23.         for (int i=1; i<=tot; i++) cout<<setw(3)<<a[i].fa;
  24.         cout<<endl;
  25. }
  26. void BSTPr(int rt)   
  27. {
  28.         if (a[rt].s[0]>0)  BSTPr(a[rt].s[0]);
  29.         cout<<a[rt].val<<' ';
  30.         if (a[rt].s[1]>0)  BSTPr(a[rt].s[1]);
  31. }
  32. void pushup(int rt)  
  33. {
  34.         int l=a[rt].s[0], r=a[rt].s[1];
  35.         a[rt].sz=a[l].sz+a[r].sz+1;
  36. }
  37. int Son(int x)
  38. {
  39.         int y=a[x].fa;
  40.         return  a[y].s[1]==x;
  41. }
  42. void R(int x)
  43. {
  44.         int y=a[x].fa;
  45.         int z=a[y].fa;
  46.         int k=Son(x);
  47.         int v=a[x].s[k^1];
  48.         a[y].s[k]=v,a[v].fa=y;
  49.         a[z].s[Son(y)]=x,a[x].fa=z;
  50.         a[x].s[k^1]=y,a[y].fa=x;
  51.         pushup(y),pushup(x);
  52. }
  53. void Splay(int x,int rt=root)
  54. {
  55.         rt=a[rt].fa;
  56.         int y,z;
  57.         while(a[x].fa!=rt)
  58.                 {
  59.                         y=a[x].fa,z=a[y].fa;
  60.                         if(z!=rt)
  61.                                 if(Son(x)==Son(y))R(y);
  62.                                 else R(x);
  63.                         R(x);
  64.                 }
  65.         if(rt==0)root=x;
  66. }

  68. int Ask(int S)
  69. {
  70.         Splay(S,root);
  71.         int l=a[root].s[0];
  72.         return a[l].sz;
  73. }

  75. int Query(int rt, int S) ///在RT子树中找第S小
  76. {
  77.         int l=a[a[rt].s[0]].sz;  /// RT的左儿子下的个数
  78.         if(l+1==S) return a[rt].val;
  79.         if(l+1>S) return Query(a[rt].s[0], S); ///左儿子里去找
  80.         if(l+1<S) return Query(a[rt].s[1], S-(l+1));
  81. }
  82. void Top(int S)
  83. {
  84.         Splay(S,root);
  85.         int  x=root;
  86.         int l=a[x].s[0];
  87.         int r=a[x].s[1];///右儿子
  88.         if (r==0) a[x].s[1]=l;
  89.         else
  90.                 {

  92.                         int p=r;
  93.                         ///找最左节点
  94.                         while (a[p].s[0]>0) p=a[p].s[0];
  95.                         Splay(p,r);
  96.                         a[p].s[0]=l;
  97.                         a[l].fa=p;
  98.                         pushup(p);
  99.                 }
  100.         a[x].s[0]=0;
  101. }
  102. void Bottom(int S)
  103. {
  104.         Splay(S,root);
  105.         int x=root;
  106.         int l=a[x].s[0];
  107.         int r=a[x].s[1];
  108.         if (l==0) a[x].s[0]=r;
  109.         else
  110.                 {
  111.                         int p=l;
  112.                         while (a[p].s[1]>0) p=a[p].s[1];
  113.                         Splay(p,r);

  115.                         a[p].s[1]=r;
  116.                         a[r].fa=p;
  117.                         pushup(p);
  118.                 }
  119.         a[x].s[1]=0;
  120. }

  122. int Pre(int S)
  123. {
  124.         Splay(S,root);
  125.         int l=a[S].s[0], ans=0;
  126.         if (l==0) return 0;
  127.         int p=l;
  128.         while(a[p].s[1]>0) p=a[p].s[1];
  129.         return p;
  130. }
  131. int Suc(int S)
  132. {
  133.                 Splay(S,root);
  134.         int r=a[S].s[1];
  135.         if (r==0) return 0;
  136.         int p=r;
  137.         while(a[p].s[0]>0) p=a[p].s[0];
  138.         return p;
  139. }
  140. int Build(int l,int r) ///前n个数直接建个满二叉树
  141. {
  142.         if (l>r) return 0;
  143.         if (l==r)
  144.                 {
  145.                         a[l].val=p[l];
  146.                         a[l].s[0]=a[l].s[1]=0;
  147.                         a[l].sz=1;
  148.                         return l;
  149.                 }
  150.         int m=(l+r)/2;
  151.         a[m].val=p[m];
  152.         int L=a[m].s[0]=Build(l,m-1);
  153.         int R=a[m].s[1]=Build(m+1,r);
  154.         a[L].fa=a[R].fa=m;
  155.         a[m].sz=a[L].sz+a[R].sz+1;
  156.         return m;
  157. }
  158. int main()
  159. {
  160.         cin>>n>>m;
  161.         for (int x,i=1; i<=n; i++)
  162.                 {
  163.                         cin>>x;
  164.                         p[i]=x;
  165.                         q[x]=i;
  166.                 }
  167.         tot=n;
  168.         root=Build(1,n);
  169.         for (int i=1; i<=n; i++)cout<<q[i]<<' ';
  170.         cout<<endl;

  172.         ///初始建树完毕
  173.         string opt;
  174.         int S,T;
  175.         while(m--)
  176.                 {
  177.                         cin>>opt;
  178.                         if(opt=="Top")
  179.                                 {
  180.                                         cin>>S;
  181.                                         Top(q[S]);
  182.                                 }
  183.                         if(opt=="Bottom")
  184.                                 {
  185.                                         cin>>S;
  186.                                         Bottom(q[S]);
  187.                                 }
  188.                         if(opt=="Insert")
  189.                                 {
  190.                                         cin>>S>>T;
  191.                                         int x;
  192.                                         if (T==-1)x=Pre(q[S]);
  193.                                         if (T== 1)x=Suc(q[S]);
  194.                                         ///这两个交换我曾经搞糊涂了
  195.                                         swap(q[a[x].val],q[S]);
  196.                                         swap(a[x].val,a[q[S]].val);
  197.                                 }
  198.                         if(opt=="Ask")
  199.                                 {
  200.                                         cin>>S;
  201.                                         cout<<Ask(q[S])<<endl;
  202.                                 }
  203.                         if(opt=="Query")
  204.                                 {
  205.                                         cin>>S;
  206.                                         cout<<Query(root,S)<<endl;
  207.                                 }
  208.                 }

  210.         return 0;
  211. }
  212. /*
  213. 10 10
  214. 1 3 2 7 5 8 10 4 9 6
  215. Query 3
  216. Top 5
  217. Ask 6
  218. Bottom 3
  219. Ask 3
  220. Top 6
  221. Insert 4 -1
  222. Query 5
  223. Query 2
  224. Ask 2
  225. */
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2