1861: [Zjoi2006]Book 书架
Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 1396 Solved: 803
[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
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
9
9
7
5
3
HINT
数据范围
100%的数据，n,m < = 80000
Source
将用Splay按照下标来建树，另外用一个数组来记录编号为i的书在Splay中的位置（指针）。
Top、Bottom和Insert操作就把该节点删掉，然后重新取出来，然后插到对应的位置。
Ask操作把对应节点伸展到根，然后求左子树的大小。Query操作就求K小值就行了。
Code
/**
* bzoj
* Problem#1861
* Accepted
* Time:1280ms
* Memory:3464k
*/
#include<iostream>
#include<fstream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef bool boolean;
#define smin(a, b) (a) = min((a), (b))
#define smax(a, b) (a) = max((a), (b))
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-' && x != -);
if(x == -) return;
if(x == '-'){
x = getchar();
aFlag = -;
}
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
u *= aFlag;
} template<typename T>
class SplayNode{
public:
T data;
int s;
SplayNode* next[];
SplayNode* father;
SplayNode(T data, SplayNode* father):data(data), father(father), s(){
memset(next, , sizeof(next));
}
inline void maintain(){
this->s = ;
for(int i = ; i < ; i++)
if(next[i] != NULL)
s += next[i]->s;
}
int which(SplayNode* p){
return (next[] == p) ? () : ();
}
}; template<typename T>
class Splay{
protected:
inline static void rotate(SplayNode<T>*& node, int d){
SplayNode<T> *father = node->father;
SplayNode<T> *newRoot = node->next[d ^ ];
node->next[d ^ ] = newRoot->next[d];
node->father = newRoot;
newRoot->next[d] = node;
newRoot->father = father;
if(node->next[d ^ ] != NULL) node->next[d ^ ]->father = node;
if(father != NULL) father->next[father->which(node)] = newRoot;
node->maintain();
node->father->maintain();
} static SplayNode<T>* findKth(SplayNode<T>*& node, int k){
int ls = (node->next[] != NULL) ? (node->next[]->s) : ();
if(k == ls + ) return node;
if(k <= ls) return findKth(node->next[], k);
return findKth(node->next[], k - ls - );
} public:
SplayNode<T>* root; Splay():root(NULL){ } inline void splay(SplayNode<T>*& node, SplayNode<T>* father){
while(node->father != father){
SplayNode<T>* f = node->father;
int fd = f->which(node);
SplayNode<T>* ff = f->father;
if(ff == father){
rotate(f, fd ^ );
break;
}
int ffd = ff->which(f);
if(fd == ffd){
rotate(ff, ffd ^ );
rotate(f, fd ^ );
}else{
rotate(f, fd ^ );
rotate(ff, ffd ^ );
}
}
if(father == NULL)
root = node;
} inline SplayNode<T>* findKth(int k, SplayNode<T>* father){
if(root == NULL || k < || k > root->s) return NULL;
SplayNode<T>* res = findKth(root, k);
splay(res, father);
return res;
} inline void insert(T data, int index){
if(root == NULL){
root = new SplayNode<T>(data, NULL);
return;
}
SplayNode<T>* added;
if(index <= ){
findKth(, NULL);
added = root->next[] = new SplayNode<T>(data, root);
}else if(index >= root->s + ){
findKth(root->s, NULL);
added = root->next[] = new SplayNode<T>(data, root);
}else if(index == root->s){
findKth(index, NULL);
findKth(index - , root);
added = new SplayNode<T>(data, root);
added->next[] = root->next[];
root->next[]->father = added;
root->next[] = added;
}else{
findKth(index - , NULL);
findKth(index + , root);
SplayNode<T>* node = root->next[]->next[];
added = node->next[] = new SplayNode<T>(data, node);
}
splay(added, NULL);
} inline void remove(SplayNode<T>* node){
splay(node, NULL);
SplayNode<T>* maxi = node->next[];
if(maxi == NULL){
root = node->next[];
if(node->next[] != NULL) node->next[]->father = NULL;
delete node;
return;
}
while(maxi->next[] != NULL) maxi = maxi->next[];
splay(maxi, node);
maxi->next[] = node->next[];
if(node->next[] != NULL) node->next[]->father = maxi;
maxi->father = NULL;
delete node;
root = maxi;
maxi->maintain();
} }; int n, m;
Splay<int> s;
SplayNode<int>** books; inline void init(){
readInteger(n);
readInteger(m);
books = new SplayNode<int>*[(const int)(n + )];
for(int i = , a; i <= n; i++){
readInteger(a);
s.insert(a, i);
books[a] = s.root;
}
} inline void solve(){
char cmd[];
int a, b;
while(m--){
scanf("%s", cmd);
readInteger(a);
if(cmd[] == 'T'){
s.remove(books[a]);
s.insert(a, );
books[a] = s.root;
}else if(cmd[] == 'B'){
s.remove(books[a]);
s.insert(a, n);
books[a] = s.root;
}else if(cmd[] == 'I'){
readInteger(b);
if(b == ) continue;
s.splay(books[a], NULL);
int r = (s.root->next[] == NULL) ? () : (s.root->next[]->s);
s.remove(books[a]);
s.insert(a, r + + b);
books[a] = s.root;
}else if(cmd[] == 'A'){
s.splay(books[a], NULL);
int r = (s.root->next[] == NULL) ? () : (s.root->next[]->s);
printf("%d\n", r);
}else if(cmd[] == 'Q'){
SplayNode<int> *node = s.findKth(a, NULL);
printf("%d\n", node->data);
}
}
} int main(){
init();
solve();
return ;
}