正文

bzoj1861:[zjoi2006]book书架（splay）

sigongzi  sigongzi  2022-08-21  738

关键词：

1861: [Zjoi2006]Book 书架

Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 1453 Solved: 822
[Submit][Status][Discuss]

Description

小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本书上面就只可能有X-1、X或X+1本书。当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小T会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。久而久之，小T的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：(1)编号为X的书在书柜的什么位置；(2)从上到下第i本书的编号是多少。

Input

第一行有两个数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本书的编号。

Output

对于每一条Ask或Query语句你应该输出一行，一个数，代表询问的答案。

Sample Input

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

Sample Output

2
9
9
7
5
3

HINT

数据范围

100%的数据，n,m < = 80000

Source

Day2

————————————————————————

splay维护序列的裸题

只需要维护一个子树大小size

1.top 将一个点删除，插入到根节点最左儿子

2.bottom 将一个点删除，插入到根节点最右儿子

3.insert +1 -1 （记录s前一个点为prev，后一个点为next）

-1 prev提根，s插在prev和它的左儿子之间

+1 next提根，s插在next和它的右儿子之间

4.ask s提根，左儿子的size

5.query 递归查找即可

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 #include <set>
  7 #include <vector>
  8 #include <string.h>
  9 #define siji(i,x,y) for(int i=(x);i<=(y);++i)
 10 #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
 11 #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
 12 #define sigongzi(j,x,y) for(int j=(x);j>(y);--j)
 13 #define inf 0x1f1f1f1f
 14 #define ivorysi
 15 #define mo 97797977
 16 #define hash 974711
 17 #define base 47
 18 #define MAXN 100005
 19 #define fi first
 20 #define se second
 21 #define pii pair<int,int>
 22 using namespace std;
 23 typedef long long ll;
 24 struct node {
 25     int size,son[2],fa;    
 26     void clear() {
 27         size=son[0]=son[1]=fa=0;
 28     }
 29 }tree[MAXN];
 30 int root;
 31 //维护size
 32 void update(int x,int c) {
 33     int k=tree[x].size;
 34     int o=tree[x].fa;
 35     tree[x].size=tree[o].size;
 36     tree[o].size=tree[o].size-k+tree[tree[x].son[c]].size;
 37 }
 38 void rotate(int x,int c) {
 39     update(x,c);
 40     int o=tree[x].fa;
 41     if(tree[o].fa!=0) {
 42         int t= o==tree[tree[o].fa].son[0] ? 0 : 1;
 43         tree[tree[o].fa].son[t]=x;
 44     }
 45     tree[o].son[c^1]=tree[x].son[c];
 46     if(tree[o].son[c^1])tree[tree[o].son[c^1]].fa=o;
 47     tree[x].son[c]=o;
 48     tree[x].fa=tree[o].fa;
 49     tree[o].fa=x;
 50     
 51 }
 52 void splay(int x,int y) {
 53     while(tree[x].fa!=y) {
 54         int k1= x==tree[tree[x].fa].son[0] ? 1 : 0;
 55         int k2= tree[x].fa == tree[tree[tree[x].fa].fa].son[0] ? 1 : 0;
 56         if(tree[tree[x].fa].fa!=y && k2==k1) {
 57             rotate(tree[x].fa,k1);
 58             rotate(x,k1);
 59         }
 60         else {
 61             rotate(x,k1);
 62         }
 63     }
 64     if(y==0) root=x;
 65     else {
 66 
 67     }
 68 }
 69 int find(int x,int c) {
 70     splay(x,0);
 71     int t=tree[x].son[c];
 72     while(tree[t].son[c^1]!=0) {
 73         t=tree[t].son[c^1];
 74     }
 75     return t;
 76 }
 77 void delete_x(int prev,int next) {
 78     if(prev!=0 && next!=0) {
 79         splay(prev,0);
 80         splay(next,prev);
 81         tree[tree[root].son[1]].son[0]=0;
 82         --tree[tree[root].son[1]].size;
 83     }
 84     else if(prev!=0) {
 85         splay(prev,0);
 86         tree[root].son[1]=0;
 87     }
 88     else {
 89         splay(next,0);
 90         tree[root].son[0]=0;
 91     }
 92     --tree[root].size;
 93 }
 94 //0是top 1是bottom
 95 void in_hurry(int x,int c) {
 96     int pr=find(x,0),ne=find(x,1);
 97     delete_x(pr,ne);
 98     int t=root;
 99     ++tree[t].size;
100     tree[x].son[c^1]=tree[t].son[c];
101     tree[tree[t].son[c]].fa=x;
102     tree[x].size=tree[tree[t].son[c]].size+1;
103     tree[x].fa=t;
104     tree[t].son[c]=x;
105 }
106 int ask(int x) {
107     splay(x,0);
108     return tree[tree[x].son[0]].size;
109 }
110 void insert(int x,int c) {
111     if(c==0) return;
112     if(ask(x)==0 && c==-1) return;
113     int pr=find(x,0),ne=find(x,1);
114     delete_x(pr,ne);
115     int t= c==-1 ? pr : ne;
116     splay(t,0);
117     c= c==-1 ? 0 : 1;
118     ++tree[t].size;
119     tree[x].clear();
120     tree[x].son[c]=tree[t].son[c];
121     tree[tree[t].son[c]].fa=x;
122     tree[x].size=tree[tree[t].son[c]].size+1;
123     tree[t].son[c]=x;
124     tree[x].fa=t;
125     splay(x,0);
126 }
127 
128 void query(int x,int s) {
129     int temp=tree[tree[x].son[0]].size+1;
130     if(s==temp) {splay(x,0);return;}
131     int t=s<temp ? 0 : 1;
132     s = s>=temp ? s-temp : s; 
133     query(tree[x].son[t],s);
134 }
135 int n,m;
136 void init() {
137     scanf("%d%d",&n,&m);
138     int a=0,b;
139     siji(i,1,n) {
140         scanf("%d",&b);
141         tree[b].fa=a;
142         if(a!=0) { 
143             tree[a].son[1]=b;
144         }
145         else {root=b;}
146         tree[b].size=n-i+1;
147         a=b;
148     }
149 
150 }
151 void solve() {
152     init();
153     char ord[15];
154     int s,t;
155     siji(i,1,m) {
156         scanf("%s",ord);
157         if(ord[0]==‘T‘ || ord[0]==‘B‘ ) {
158             t=ord[0]==‘T‘ ? 0 : 1;
159             scanf("%d",&s);
160             in_hurry(s,t);
161         }
162         else if(ord[0]==‘I‘) {
163             scanf("%d%d",&s,&t);
164             insert(s,t);
165         }
166         else if(ord[0]==‘A‘){
167             scanf("%d",&s);
168             printf("%d
",ask(s));
169         }
170         else if(ord[0]==‘Q‘) {
171             scanf("%d",&s);
172             query(root,s);
173             printf("%d
",root);
174         }
175     }
176 }
177 int main(int argc, char const *argv[])
178 {
179 #ifdef ivorysi
180     freopen("f1.in","r",stdin);
181 #endif
182     solve();
183 }

[bzoj1861][zjoi2006]book书架

[BZOJ1861][Zjoi2006]Book书架试题描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一... 查看详情

bzoj1861[zjoi2006]book书架

1#include<bits/stdc++.h>2usingnamespacestd;3constintN=8e4+5;4constintinf=1e9;5intfa[N],c[N][2],size[N],pos[N],a[N],v[N],n,m,rt;6voidupdate(intx)7{8size[x]=size[c[x][0]]+size[c[x][1]]+1;9}10voidr 查看详情

bzoj1861:[zjoi2006]book书架

这题想写三次了。结果前两次太困╯﹏╰没写成，大数据结构题就是烦人啊。没什么值得注意的，就按题意一步步来吧。（写了map表示对应树上位置，担心编号大爆掉，不加好像也没啥关系）#include<cstdio>#include<iostream>#i... 查看详情

bzoj1861[zjoi2006]book书架——splay

【题目分析】模板题目。首尾两个虚拟结点，十分方便操作。【代码】#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<map>#include<set>#include<queue& 查看详情

bzoj1861:[zjoi2006]book书架splay

1861:[Zjoi2006]Book书架Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。... 查看详情

bzoj1861:[zjoi2006]book书架

Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引... 查看详情

bzoj1861:[zjoi2006]book书架

[题解]bzoj1861book书架-splay

1861:[Zjoi2006]Book书架TimeLimit: 4Sec MemoryLimit: 64MBSubmit: 1396 Solved: 803[Submit][Status][Discuss]Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到查看详情

bzoj1861：[zjoi2006]书架——题解

http://www.lydsy.com/JudgeOnline/problem.php?id=1861（题面复制于洛谷）题目描述小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一... 查看详情

[bzoj1861][zjoi2006]书架

BZOJLuoguDescription小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太... 查看详情

[zjoi2006]book书架

pre.cjk{font-family:"DroidSansFallback",monospace}p{margin-bottom:0.25cm;line-height:120%}a:link{}1861:[Zjoi2006]Book书架TimeLimit:4Sec MemoryLimit:64MBSubmit:1581 Solved:884[Submi 查看详情

bzoj1861:[zjoi2006]book书架（平衡树）(代码片段)

原题链接题目描述：小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些... 查看详情

1861.[zjoi2006]书架平衡树-splay(代码片段)

[zjoi2006]书架(代码片段)

[题目链接] https://www.lydsy.com/JudgeOnline/problem.php?id=1861[算法] 平衡树时间复杂度：O(MlogN)[代码] &n 查看详情

[zjoi2006]book书架(代码片段)

DescriptionSally有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。Sally在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸... 查看详情

「luogu2596」[zjoi2006]书架(代码片段)

用平衡树维护每本书的位置1#include<bits/stdc++.h>2usingnamespacestd;3constintN=80010;4intn,m,maxpos,minpos,book[N<<2],bookpos[N];5introot,fa[N<<2],ch[N<<2][2],siz[N<<2],pos[N<<2 查看详情

bzoj1861书架splay版

单点插入删除以及求前缀#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintM=100055,inf=1000000000;intread(){intans=0,f=1,c=getchar();while(c<‘0‘||c>‘9‘){if(c==‘- 查看详情

bzoj1861书架(代码片段)

题目链接思路用一个平衡树维护点的编号和权值。这里的权值是自己赋上去的。操作1，就把x从平衡树中删掉，然后将其权值变为最小值，重新插入。操作2，与操作1类似，只要将其权值变为最大值再重新插入就行了。操作3，其... 查看详情