题解 P2596 【[ZJOI2006]书架】

· · 题解

我的做法好像又是比较清奇

这显然是个文艺平衡树的题

看看每个操作我们要干什么

1． Top S——表示把编号为S的书放在最上面。

先找到书 S 的位置 pos，翻转区间 [1,pos]，再翻转区间 [2 ,pos]

2． Bottom S——表示把编号为S的书放在最下面。

先找到书 S 的位置 pos，翻转区间 [pos ,n]，再翻转区间 [pos + 1 ,n]

3． Insert S T——T∈{-1，0，1}，若编号为S的书上面有X本书，则这条命令表示把这本书放回去后它的上面有X+T本书；

先找到书 S 的位置 pos，翻转区间 [pos ,pos + T]

4． Ask S——询问编号为S的书的上面目前有多少本书。

询问 S 的 rank（把 S 转到根，问左子树大小）

5． Query S——询问从上面数起的第S本书的编号。

询问第 S 位的 key

由于我的splay需要插入 INF 和 -INF 以便于求PRE和NXT的时候不会RE，所以某些地方需要 +1 -1的

#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<iostream>

//#define debug

#define rg register
#define il inline
#define MX (100000 + 4)
#define INF (0x7f7f7f7f)

void swap(int &x ,int &y){
    int t = x;
    x = y ,y = t;  
}
namespace SPLAY{
    #define lch(x) ch[x][0]
    #define rch(x) ch[x][1]
    int root ,sz;
    int ch[MX][2] ,fa[MX] ,mark[MX] ,size[MX] ,key[MX] ,pos[MX];
    int get(int x){return x == ch[fa[x]][1];}
    void pushup(int x){
        if(!x)  return;
        size[x] = 1;
        if(lch(x))  size[x] += size[lch(x)];
        if(rch(x))  size[x] += size[rch(x)];
    }
    void reverse(int x){
        if(!x)  return ; 
        swap(lch(x) ,rch(x));
        mark[x] ^= 1;
    }
    void pushdown(int x){
        if(!x)  return;
        if(mark[x]){
            if(lch(x))  reverse(lch(x));
            if(rch(x))  reverse(rch(x));
            mark[x] = false;
        }
    }
    void rotate(int x){
        int f = fa[x] ,gf = fa[f] ,which = get(x) ,w = ch[x][!which];
        if(gf)  ch[gf][ch[gf][1] == f] = x;
        ch[x][!which] = f ,ch[f][which] = w;
        if(w)   fa[w] = f;
        fa[f] = x ,fa[x] = gf;
        pushup(f) ,pushup(x);
    }
    int stack[MX] ,dep;
    void splay(int x ,int goal = 0){    //////
        int f = x;
        stack[++dep] = f;
        while(f)    stack[++dep] = f = fa[f];
        while(dep)  pushdown(stack[dep--]);
        for( ; (f = fa[x]) != goal ; rotate(x)){
            if(fa[f] != goal)   rotate(get(x) == get(f) ? f : x);
        }if(!goal)  root = x;
    }
    void insert(int x){
        int now = root;
        while(rch(now)) now = rch(now);
        fa[++sz] = now; 
        if(now) ch[now][1] = sz;

        key[sz] = x;
        size[sz] = 1;
        mark[sz] = ch[sz][0] = ch[sz][1] = 0;
        pushup(now);
        splay(sz);
    }
    int rank(int val){
        splay(pos[val]);
        return size[lch(pos[val])] + 1;
    }
    int Kth(int rank){
        int x = root;
        while(true){
            pushdown(x);
            if(lch(x) && rank <= size[lch(x)])  x = lch(x);
            else{
                int tmp = (lch(x) ? size[lch(x)] : 0) + 1;
                if(rank <= tmp) return x;
                rank -= tmp;
                x = rch(x);
            }
        }
    }
    void reverse(int l ,int r){
        splay(l - 1); 
        if(l >= r)  return;
        int PRE = Kth(l - 1) ,NXT = Kth(r + 1);
        splay(PRE); 
        splay(NXT ,PRE);
        reverse(ch[NXT][0]);
    }
}using namespace SPLAY;

int main(){
    int n ,m;
    scanf("%d%d" ,&n ,&m);
    insert(-INF);
    for(rg int i = 1 ,tmp ; i <= n ; ++i){
        scanf("%d" ,&tmp);
        pos[tmp] = i + 1;
        insert(tmp);
    }
    insert(INF);
    #ifdef debug
    test();puts("");
    #endif 
    char op[33];
    for(rg int i = 1 ,s ,t ; i <= m ; ++i){
        scanf("%s%d" ,op ,&s);
        switch(op[0]){
            case 'T':{
                int l = rank(s);
                if(l != 2){
                    reverse(2 ,l);
                    reverse(3 ,l);
                }
                break;
            }
            case 'B':{
                int l = rank(s);
                if(l != n + 1){
                    reverse(l ,n + 1);
                    reverse(l ,n);
                }
                break;
            }
            case 'I':{
                int delta ,P = rank(s);
                scanf("%d" ,&delta);
                switch(delta){
                    case 0:{break;}
                    case 1:{
                        reverse(P ,P + 1);
                        break;
                    }
                    case -1:{
                        reverse(P - 1 ,P);
                        break;
                    }
                }
                break;
            }
            case 'A':{
                printf("%d \n" ,rank(s) - 2);
                break;
            }
            case 'Q':{
                printf("%d \n" ,key[Kth(s + 1)]);
                break;
            } 
        }
    }return 0;
}