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

输入输出样例

输入样例#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

首先看到数据范围应该要想到大概的时间复杂度O(nlogn),然后题目涉及了很多的修改查询操作,可以看出要用数据结构来维护。题目要求查询第k小的元素,所以我们用平衡树来处理这个问题。因为在splay的操作中需要以一个值来作为树中维护的值(或是在插入时就先确定好数中节点的关系,不再修改)。既然题目要求的是修改查询书架上的第几本书,并对这样的关系进行修改。我们知道,splay的中序遍历结果就是该序列。所以,我们可以用一个优先级来表示一个节点所在位置(优先级越小就越靠前)并且用splay来维护这个优先级,这样题目中的操作就变成了这样:

  1. \(Top\):将一个元素放到树中的最左边,也就是将该节点的优先级调到最小,删除后重新插入。
  2. \(Bottom\):将一个元素放到树的最右边,将该节点的优先级调到最大,删除候重新插入。
  3. \(Insert\):将一个元素与它的前驱/后继交换优先级,两个都删除然后重新插入。
  4. \(Ask\):查询一个元素的排名。
  5. \(Query\):查询第k小的元素。

为什么每个元素在修改的时候不能直接更改优先级呢?因为我们要维持splay平衡树的性质,如果直接修改优先级而不改变它的位置的话,那么中序遍历的结果就不是按照优先级从小到大的排列了,下次在遍历整颗树的时候就会有可能找不到一个元素应该在的位置。所以要先删除再重新插入。

然后是在操作过程中要记录每个编号的优先级,因为splay中只能按照一个值来维护,所以一个节点的编号只能作为被查找到的位置的一个值。然后剩下的就是splay的基本操作了。然后在splay操作过程中记得按照每个点的优先级来遍历,交换时注意将编号所对应的优先级也交换。

#include<bits/stdc++.h>
#define debug output(root), cout << endl
using namespace std;
const int N=800000+5;
const int inf=2147483647; int n, m, mn, mx, cnt = 0, id[N], root = 0, r[N];
char f[10]; struct node{
int rk, fa, ch[2], val, size;
}t[N]; bool get(int x){ return t[t[x].fa].ch[1] == x; } void up(int x){ t[x].size = t[t[x].ch[0]].size+t[t[x].ch[1]].size+1; } void rotate(int x){
int fa = t[x].fa , gfa = t[fa].fa;
int d1 = get(x) , d2 = get(fa);
t[fa].ch[d1]=t[x].ch[d1^1]; t[t[x].ch[d1^1]].fa=fa;
t[x].ch[d1^1] = fa; t[fa].fa = x;
t[gfa].ch[d2] = x; t[x].fa = gfa;
up(fa); up(x);
} void splay(int x,int goal){
while(t[x].fa != goal){
int fa = t[x].fa , gfa = t[fa].fa;
int d1 = get(x) , d2 = get(fa);
if(gfa != goal){
if(d1 == d2) rotate(fa);
else rotate(x);
}
rotate(x);
}
if(goal == 0) root = x;
} void insert(int rank,int val){
int node = root , fa = 0;
while(node && t[node].rk != rank)
fa = node , node = t[node].ch[t[node].rk<rank];
node = ++cnt;
if(fa) t[fa].ch[t[fa].rk<rank] = node;
t[node].rk = rank;
t[node].val = val;
t[node].fa = fa;
t[node].size = 1;
splay(node , 0);
} int find(int rank){
int node = root;
while(t[node].rk != rank)
node = t[node].ch[t[node].rk<rank];
return node;
} int pre(int rank,int kind){
splay(find(rank) , 0);
int node = root;
if(t[node].rk<rank && kind == 0) return node;
if(t[node].rk>rank && kind == 1) return node;
node = t[node].ch[kind];
while(t[node].ch[kind^1])
node = t[node].ch[kind^1];
return node;
} void delet(int rank){
int last = pre(rank,0) , next = pre(rank,1);
splay(last , 0); splay(next , last);
t[next].ch[0] = 0;
} int kth(int k){
int node = root;
while(1){
int son = t[node].ch[0];
if(k <= t[son].size) node = son;
else if(k == t[son].size+1) return t[node].val;
else k-=t[son].size+1 , node=t[node].ch[1];
}
} int get_rank(int rank){ splay(find(rank) , 0); return t[t[root].ch[0]].size + 1; } void Top(int x,int kind){
splay(find(id[x]) , 0);
int val = t[root].val;
if(kind == 0){
delet(id[x]);
id[x] = --mn; insert(id[x] , val);
}
if(kind == 1){
delet(id[x]);
id[x] = ++mx; insert(id[x] , val);
}
} void Insert(int x,int pos){
if(pos == 0) return;
int rank1 = get_rank(id[x]) , rank2 = rank1+pos;
int val1 = x , val2 = kth(rank2);
delet(id[val1]); delet(id[val2]);
swap(id[val1] , id[val2]);
insert(id[val1] , val1) , insert(id[val2] , val2);
} int Ask(int x){ splay(find(id[x]) , 0); return t[t[root].ch[0]].size-1; } int Query(int x){ return kth(x+1); } int main(){
insert(-inf,555); insert(inf,666);
int x, y; cin >> n >> m;
mn = 1 , mx = n;
for(int i=1;i<=n;i++)
cin >> x , insert(i,x) , id[x]=i;
for(int i=1;i<=m;i++){
scanf("%s%d",f,&x);
if(f[0] == 'T') Top(x,0);
if(f[0] == 'B') Top(x,1);
if(f[0] == 'I') cin >> y , Insert(x,y);
if(f[0] == 'A') printf("%d\n",Ask(x));
if(f[0] == 'Q') printf("%d\n",Query(x));
}
}

无旋treap做法

最近同学在学treap,想用treap来写这题,于是我也去写了一下.

无旋treap可以维护一棵树的中序遍历结果.但是不支持通过编号来找节点.于是在无旋treap的基础上,我维护了每个节点的父亲,这样就可以求出一个节点是中序遍历中的第几个.

那么对于一个节点,每次将它向树根跳,如果它是右儿子,那么就将它父亲的左子树的值以及父亲的大小计入结果.

那么问题就只有如何记录父亲了.显然会改变父亲的只有\(split\)和\(merge\)操作,那么我只需要在这两个函数中修改就可以了.在\(split\)的时候再传两个参数记录父亲,\(merge\)在修改儿子的时候同时将父亲一起修改.

其他的都是无旋treap的基本操作了.

  • \(Top\): 提取该节点,放在树的最前面合并.
  • \(Bottom\): 提取节点,放在树的最后面合并.
  • \(Insert\): 将它与前驱/后继从整棵树中分离出来,交换顺序合并.
  • \(Ask\): 直接通过编号找到节点是中序遍历结果第几个.
  • \(Query\): 先找到节点是中序遍历第几个,然后split前k个,在分离出的第一颗子树中找最右边的节点.

代码凑合着看一下吧.

#include<bits/stdc++.h>
#define debug out(root), cout << endl
using namespace std;
const int N=80000+5; int n, m, id[N], a[N], root, r1, r2, r3, r4, cnt = 0;
//id记录某一个书的编号映射到树中的节点编号 struct treap{
int ch[2], fa, size, rd, val;
}t[N]; int gi(){
int ans = 0, f = 1; char i = getchar();
while(i<'0' || i>'9'){ if(i == '-') f = -1; i = getchar(); }
while(i>='0' && i<='9') ans = ans*10+i-'0', i = getchar();
return ans * f;
} int newnode(int val){
t[++cnt].val = val; t[cnt].rd = rand(), t[cnt].size = 1;
id[val] = cnt; return cnt;
} void up(int x){ t[x].size = t[t[x].ch[0]].size+t[t[x].ch[1]].size+1; } void split(int x, int k, int &a, int &b, int faa = 0, int fab = 0){
if(x == 0){ a = b = 0; return; }
if(k <= t[t[x].ch[0]].size) t[x].fa = fab, b = x, split(t[x].ch[0], k, a, t[x].ch[0], faa, x);
else t[x].fa = faa, a = x, split(t[x].ch[1], k-t[t[x].ch[0]].size-1, t[x].ch[1], b, x, fab); up(x);
} int merge(int x, int y){
if(x == 0 || y == 0) return x+y;
if(t[x].rd < t[y].rd){
t[x].ch[1] = merge(t[x].ch[1], y);
t[t[x].ch[1]].fa = x; up(x); return x;
}
else {
t[y].ch[0] = merge(x, t[y].ch[0]);
t[t[y].ch[0]].fa = y; up(y); return y;
}
} void insert(int pos, int val){
split(root, pos, r1, r2);
root = merge(r1, merge(newnode(val), r2));
} bool get(int x){ return t[t[x].fa].ch[1] == x; } int find(int cnt){//cnt是节点编号
int node = cnt, res = t[t[cnt].ch[0]].size+1;
while(node != root && cnt){
if(get(cnt)) res += t[t[t[cnt].fa].ch[0]].size+1;
cnt = t[cnt].fa;
//这里可以画图理解一下,因为如果该节点是左儿子的话,向上走是中序遍历在增大的
//如果是右儿子向上跳的话,父亲的左子树的所有节点的中序遍历的结果都小于我在查的节点,所以要计入答案.
}
return res;
} int main(){
char opt[10]; int x, y, k; n = gi(), m = gi(); srand(19260817);
for(int i=1;i<=n;i++) a[i] = gi(), insert(i-1, a[i]);
for(int i=1;i<=m;i++){
scanf("%s", opt); x = gi(); if(opt[0] == 'T'){
k = find(id[x]);//通过节点编号找到书本编号为x的节点是第k个
split(root, k, r1, r3);
split(r1, k-1, r1, r2);
root = merge(r2, merge(r1, r3));
} if(opt[0] == 'B'){
k = find(id[x]);
split(root, k, r1, r3, 0);
split(r1, k-1, r1, r2, 0);
root = merge(r1, merge(r3, r2));
} if(opt[0] == 'I'){
y = gi(); k = find(id[x]);
if(y){
if(y > 0){//与前驱/后继交换后插入
split(root, k+1, r3, r4);
split(r3, k, r2, r3);
split(r2, k-1, r1, r2);
root = merge(r1, merge(r3, merge(r2, r4)));
}
else {
split(root, k, r3, r4);
split(r3, k-1, r2, r3);
split(r2, k-2, r1, r2);
root = merge(r1, merge(r3, merge(r2, r4)));
}
}
} if(opt[0] == 'A'){
k = find(id[x]);
printf("%d\n", k-1);
} if(opt[0] == 'Q'){
split(root, x, r1, r2);
int node = r1;
while(t[node].ch[1]) node = t[node].ch[1];
printf("%d\n", t[node].val);
root = merge(r1, r2);
}
}
return 0;
}
上一篇:洛谷 P2677 超级书架 2 题解


下一篇:洛谷P2677 超级书架 2