「ZJOI2006」书架 - Splay

题目链接：传送门

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

Solution

又是一道平衡树的题 然而一道模板题我调了一天。。。 代码能力太弱了。。。

Code

#include <bits/stdc++.h>

using namespace std;
const int Maxn = 80000 + 100;

int N, M, cnt, root;
struct node
{
    int ch[2], size, fa, val, val2;
}Tree[Maxn];

int Pos[Maxn];
inline void Insert(int x, int f)
{
    Tree[++cnt].val = x;
    Pos[x] = cnt;
    Tree[cnt].fa = f;
    Tree[cnt].size = 1;
    return ;
}

inline int judge_dir (int x)
{
    return Tree[Tree[x].fa].ch[1] == x;
}

inline void Connect(int x, int f, int dir)
{
    Tree[x].fa = f;
    Tree[f].ch[dir] = x;
    return ;
}

inline void Push_up(int x)
{
    Tree[x].size = Tree[Tree[x].ch[0]].size + Tree[Tree[x].ch[1]].size + 1;
    Pos[Tree[Tree[x].ch[0]].val] = Tree[x].ch[0];
    Pos[Tree[x].val] = x;
    Pos[Tree[Tree[x].ch[1]].val] = Tree[x].ch[1];
    return ;
}

inline void rotate(int x)
{
    int dirx = judge_dir(x), f = Tree[x].fa, anc = Tree[f].fa, dirf = judge_dir(f);
    Connect(Tree[x].ch[dirx ^ 1], f, dirx);
    Connect(x, anc, dirf);
    Connect(f, x, dirx ^ 1);
    Push_up(f);
    Push_up(x);
}

inline void Splay(int x, int y)
{
    while (Tree[x].fa != y)
    {
        int dirx = judge_dir(x), f = Tree[x].fa, dirf = judge_dir(f);
        if (Tree[f].fa == y) rotate(x);
        else if (dirx == dirf) rotate(f), rotate(x);
        else rotate(x), rotate(x);
    }
    Pos[Tree[x].val] = x;
    if (!y) root = x;
}

inline void Create(int x)
{
    if (!root)
    {
        root = 1;
        Tree[root].val2 = 1;
        Insert(x, 0);
        return ;
    }
    /*
    ++cnt;
    Tree[cnt - 1].ch[1] = cnt;
    Tree[cnt].val = x;
    Tree[cnt].fa = cnt - 1;
    Splay(cnt, 0);
    */
    int now = root;
    while (1)
    {
        Tree[now].size ++;
        int dir = x > Tree[now].val2;
        if (!Tree[now].ch[dir])
        {
            Insert(x, now);
            Tree[now].ch[dir] = cnt;
            Tree[now].val2 = cnt;
            Splay(cnt, 0);
            return ;
        }
        now = Tree[now].ch[dir];
    }
}

char s[10];

inline int Find(int x)
{
    return Pos[x];
}

inline void Put_top(int x)
{
    x = Find(x);
//  cout<<"*"<<x<<endl;
    Splay(x, 0);
    if (!Tree[x].ch[0]) return ;
    if (!Tree[x].ch[1])
    {
        Tree[x].ch[1] = Tree[x].ch[0];
        Tree[x].ch[0] = 0;
        Push_up(x);
        return ;
    }
    int now = Tree[x].ch[1];
    while (Tree[now].ch[0]) now = Tree[now].ch[0];
    Splay(now, x);
    Connect(Tree[x].ch[0], now, 0);
    Tree[x].ch[0] = 0;
    Push_up(now);
    Push_up(x);
}

inline void Put_bottom(int x)
{
    x = Find(x);
//  cout<<"#"<<x<<endl;
    Splay(x, 0);
    if (!Tree[x].ch[1]) return ;
    if (!Tree[x].ch[0])
    {
        Tree[x].ch[0] = Tree[x].ch[1];
        Tree[x].ch[1] = 0;
        Push_up(x);
        return ;
    }
    int now = Tree[x].ch[0];
    while (Tree[now].ch[1]) now = Tree[now].ch[1];
    Splay(now, x);
    Connect(Tree[x].ch[1], now, 1);
    Tree[x].ch[1] = 0;
    Push_up(now);
    Push_up(x);
}

inline void Change(int x, int y)
{
    if (!y) return ;
    x = Find(x);
    Splay(x, 0);
    int dir = (y == 1);
    if (!Tree[x].ch[dir]) return ;
    int now = Tree[root].ch[dir];
//  cout<<Tree[root].ch[0]<<" "<<Tree[root].ch[1]<<endl;
//  cout<<Tree[10].ch[0]<<" "<<Tree[10].ch[1]<<endl;
    while (Tree[now].ch[dir ^ 1]) now = Tree[now].ch[dir ^ 1];
//  cout<<Tree[now].val;cout<<endl;
//  cout<<Tree[x].val<<" "<<Tree[now].val<<endl;
    swap(Tree[x].val, Tree[now].val);
    Pos[Tree[x].val] = x;
    Pos[Tree[now].val] = now;
//  cout<<Tree[2].val<<endl;
}

inline int Rank(int x)
{
    x = Find(x);
    Splay(x, 0);
    return Tree[Tree[x].ch[0]].size;
}

inline int Rerank(int x)
{
    int now = root;
    while (1)
    {
        int Sum = Tree[Tree[now].ch[0]].size + 1;
        if (Sum == x) return Tree[now].val;
        if (x <= (Sum - 1)) now = Tree[now].ch[0];
        else x -= (Tree[Tree[now].ch[0]].size + 1), now = Tree[now].ch[1];
    }
}

inline void Print(int x)
{
    if (Tree[x].ch[0]) Print(Tree[x].ch[0]);
    cout<<Tree[x].val<<" ";
    if (Tree[x].ch[1]) Print(Tree[x].ch[1]);
}
int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    scanf("%d%d", &N, &M);
    int x, y;
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d", &x);
        Create(x);
    }
    while (M--)
    {
        scanf("%s", s);
        scanf("%d", &x);
        if (s[0] == 'T') Put_top(x);
        if (s[0] == 'B') Put_bottom(x);
        if (s[0] == 'I') scanf("%d", &y), Change(x, y);
        if (s[0] == 'A') cout<<Rank(x)<<endl;
        if (s[0] == 'Q') cout<<Rerank(x)<<endl;
    }
    return 0;
}