BZOJ 1861 Book 书架（splay插入和删除等操作）

1861: [Zjoi2006]Book 书架

Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 1841 Solved: 1049
[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

3
HINT

数据范围

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

题目链接：BZOJ 1861
splay的插入和删除、找第 $k$ 大操作，由于 $h z w e r$ 大佬的奇怪的建树和记录点姿势和感觉不太懂，就还是用原来的建树方式了（还是熟悉的配方），由于 $p o s$ 数组记录的是编号对应在树上的下标，因此我的代码在建树时才更新 $p o s$ 数组而不是预先设定好。其余的操作都是参考大佬的博客，这里的 $d e l$ 操作有两种，一种是找到要删除节点的前驱和后继然后将前驱点旋转到根，后继点旋转到根的右儿子，然后将后继点的左儿子删除掉即可；第二种是我尝试用之前学的删除的方法，只将要删除的点旋转到根，然后合并以左儿子和右儿子为根的两颗子树，其中涉及到的点用一个数组记录下来，然后按深度从大到小依次 $p u s h u p$ 上去，没想到这样也可以而且速度居然比前面一种快了 $300 m s$ +，好神奇……。
最后由于我们插入了两个虚拟节点当做边界点，因此计算排名的时候注意 $+ 1$ 或 $- 1$
第二种的del操作：

void del(int k)
{
    int x = Find_kth(rt, k);
    splay(x, rt);
    top = 0;//用top指针和st数组记录需要pushup的点
    if (T[x].ch[0] * T[x].ch[1] == 0)
    {
        rt = T[x].ch[0] + T[x].ch[1];
        st[top++] = rt;
    }
    else
    {
        int k = T[x].ch[1];
        st[top++] = k;
        while (T[k].ch[0])
        {
            k = T[k].ch[0];
            st[top++] = k;
        }
        T[k].ch[0] = T[x].ch[0];
        T[T[x].ch[0]].f = k;
        rt = T[x].ch[1];
    }
    for (int i = top - 1; i >= 0; --i)
        pushup(st[i]);
    T[rt].f = 0;
}

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 80010;
struct node
{
    int ch[2], sz, f, id;
} T[N];
int rt, sz, ID[N], pos[N], n, m;

void init()
{
    rt = sz = 0;
}
inline void newnode(int k, int f, int id)
{
    T[k].ch[0] = T[k].ch[1] = 0;
    T[k].f = f;
    T[k].id = id;
    T[k].sz = 1;
}
inline int getson(int x)
{
    return T[T[x].f].ch[1] == x;
}
inline void pushup(int x)
{
    T[x].sz = T[T[x].ch[0]].sz + T[T[x].ch[1]].sz + 1;
}
void rotate(int x, int &k)
{
    int f = T[x].f, ff = T[f].f, l = getson(x), r = l ^ 1;
    if (f == k)
        k = x;
    else
        T[ff].ch[getson(f)] = x;
    T[x].f = ff;
    T[f].ch[l] = T[x].ch[r];
    if (T[x].ch[r])
        T[T[x].ch[r]].f = f;
    T[x].ch[r] = f;
    T[f].f = x;
    pushup(f);
    pushup(x);
}
inline void splay(int x, int &k)
{
    while (x != k)
    {
        int f = T[x].f;
        if (f != k)
        {
            if (getson(x)^getson(f))
                rotate(x, k);
            else
                rotate(f, k);
        }
        rotate(x, k);
    }
}
void build(int &k, int l, int r, int f)
{
    int mid = MID(l, r);
    newnode(k = ++sz, f, ID[mid]);
    pos[T[k].id] = k;
    if (l < mid)
        build(T[k].ch[0], l, mid - 1, k);
    if (mid < r)
        build(T[k].ch[1], mid + 1, r, k);
    pushup(k);
}
int Find_kth(int x, int k)
{
    int w = T[T[x].ch[0]].sz + 1;
    if (k == w)
        return x;
    if (k < w)
        return Find_kth(T[x].ch[0], k);
    return Find_kth(T[x].ch[1], k - w);
}
void del(int k)
{
    int x = Find_kth(rt, k - 1), y = Find_kth(rt, k + 1);
    splay(x, rt);
    splay(y, T[rt].ch[1]);
    int z = T[y].ch[0];
    T[y].ch[0] = 0;
    T[z].f = 0;
    pushup(y);
    pushup(x);
}
void Move(int id, int val)
{
    int x, y, z = pos[id];
    splay(z, rt);
    int ran = T[T[z].ch[0]].sz + 1;//原来的排名
    del(ran);
    if (val == INF)
        x = Find_kth(rt, n), y = Find_kth(rt, n + 1);
    else if (val == -INF)
        x = Find_kth(rt, 1), y = Find_kth(rt, 2);
    else
        x = Find_kth(rt, ran + val - 1), y = Find_kth(rt, ran + val);
    splay(x, rt);
    splay(y, T[rt].ch[1]);
    newnode(z, y, id);
    T[y].ch[0] = z;
    pushup(y);
    pushup(x);
}
int main(void)
{
    int i, id;
    char ops[4];
    while (~scanf("%d%d", &n, &m))
    {
        init();
        for (i = 2; i <= n + 1; ++i)
            scanf("%d", &ID[i]);
        build(rt, 1, n + 2, 0);
        while (m--)
        {
            scanf("%s", ops);
            if (ops[0] == 'T')
            {
                scanf("%d", &id);
                Move(id, -INF);
            }
            else if (ops[0] == 'B')
            {
                scanf("%d", &id);
                Move(id, INF);
            }
            else if (ops[0] == 'I')
            {
                int S, T;
                scanf("%d%d", &S, &T);
                Move(S, T);
            }
            else if (ops[0] == 'A')
            {
                scanf("%d", &id);
                splay(pos[id], rt);
                printf("%d\n", T[T[rt].ch[0]].sz - 1);
            }
            else if (ops[0] == 'Q')
            {
                int S;
                scanf("%d", &S);
                printf("%d\n", T[Find_kth(rt, S + 1)].id);
            }
        }
    }
    return 0;
}