BZOJ 1861 ZJOI 2006 Book 書架 Splay

BZOJ 1861 ZJOI 2006 Book 書架 Splay

題目大意：有一個書架，現在需要經常改變這些書的位置，每次詢問一本書在哪或者第幾本書是什麼。

思路：赤裸裸的Splay，只是有些小事需要注意。因為他有的時候問你一個書在哪，這個事情不能只在Splay中就能解決，我們需要輔助他解決。注意到操作中沒有加入書的操作，也就是書的總數並不會變化，而且Splay的過程中只是指針的變動，所以不會有點發生變化，所以在一開始建樹的時候維護一個數組，表示這本書在Splay中的節點，這樣我們就能快速的找到任意一本書的節點。詢問一本書的排名的時候，我們需要先找到這個節點，然後不斷向根靠近，在這過程中進行統計有多少個節點在這個節點前面就行了。自己YY出來的思路，不過感覺這種操作不是Splay原生的操作，應該還有更優雅的解決方法吧。。具體見代碼。

CODE：

#include 
#include 
#include 
#include 
#define MAX 80010
using namespace std;

struct SplayTree{
    int val,size;
    SplayTree *son[2],*father;
    
    bool Check() {
        return father->son[1] == this;
    }
    void Combine(SplayTree *a,bool dir) {
        a->father = this;
        son[dir] = a;
    }
}*pos[MAX],none,*nil = &none,*root;

int points,asks;
int src[MAX];

char s[10];

SplayTree *NewNode(int _)
{
    SplayTree *re = new SplayTree();
    re->son[0] = re->son[1] = nil;
    re->val = _;
    re->size = 1;
    return re;
}

inline void PushUp(SplayTree *a)
{
    a->size = a->son[0]->size + a->son[1]->size + 1;
}

SplayTree *BuildTree(int l,int r)
{
    if(l > r)   return nil;
    int mid = (l + r) >> 1;
    SplayTree *re = NewNode(src[mid]);
    pos[src[mid]] = re;
    re->Combine(BuildTree(l,mid - 1),false);
    re->Combine(BuildTree(mid + 1,r),true);
    PushUp(re);
    return re;
}

inline void Rotate(SplayTree *&a,bool dir)
{
    SplayTree *f = a->father;
    f->son[!dir] = a->son[dir];
    f->son[!dir]->father = f;
    a->son[dir] = f;
    f->father->son[f->Check()] = a;
    a->father = f->father;
    f->father = a;
    PushUp(f);
    if(root == f)	root = a;
}

inline void Splay(SplayTree *a,SplayTree *aim)
{
    while(a->father != aim) {
        if(a->father->father == aim)
            Rotate(a,!a->Check());
        else if(!a->father->Check()) {
            if(!a->Check())
                Rotate(a->father,true),Rotate(a,true);
            else	Rotate(a,false),Rotate(a,true);
        }
        else {
            if(a->Check())
                Rotate(a->father,false),Rotate(a,false);
            else	Rotate(a,true),Rotate(a,false);
        }
    }
    PushUp(a);
}

SplayTree *Find_(SplayTree *a,int k)
{
    if(k <= a->son[0]->size)	return Find_(a->son[0],k);
    k -= a->son[0]->size;
    if(k == 1)	return a;
    return Find_(a->son[1],k - 1);
}

int Find(SplayTree *a,int k)
{
    if(k <= a->son[0]->size)	return Find(a->son[0],k);
    k -= a->son[0]->size;
    if(k == 1)	return a->val;
    return Find(a->son[1],k - 1);
}

inline int Rank(SplayTree *a)
{
    int re = a->son[0]->size;
    while(a != root) {
        if(a->Check())
            re += a->father->son[0]->size + 1;
        a = a->father;
    }
    return re + 1;
}

inline void Insert(int rank,int aim)
{
    Splay(Find_(root,rank - 1),nil);
    Splay(Find_(root,rank + 1),root);
    SplayTree *temp = root->son[1]->son[0];
    root->son[1]->son[0] = nil;
    PushUp(root->son[1]);
    PushUp(root);
    Splay(Find_(root,aim - 1),nil);
    Splay(Find_(root,aim),root);
    root->son[1]->Combine(temp,false);
    PushUp(root->son[1]);
    PushUp(root);
}

int main()
{
    cin >> points >> asks;
    for(int i = 1; i <= points; ++i)
        scanf("%d",&src[i]);
    root = BuildTree(0,points + 1);
    root->father = nil;
    nil->son[1] = root;
    nil->son[0] = nil;
    for(int x,y,i = 1; i <= asks; ++i) {
        scanf("%s",s);
        if(s[0] == 'Q') {
            scanf("%d",&x);
            printf("%d\n",Find(root,x + 1));
        }
        if(s[0] == 'A') {
            scanf("%d",&x);
            printf("%d\n",Rank(pos[x]) - 2);
        }
        if(s[0] == 'T') {
            scanf("%d",&x);
            int rank = Rank(pos[x]);
            Insert(rank,2);
        }
        if(s[0] == 'B') {
            scanf("%d",&x);
            int rank = Rank(pos[x]);
            Insert(rank,points + 1);
        }
        if(s[0] == 'I') {
            scanf("%d%d",&x,&y);
            if(!y)	continue;
            int rank = Rank(pos[x]),temp;
            if(y == 1)	temp = rank + 1;
            else	temp = rank - 1;
            Insert(rank,temp);
        }
    }
    return 0;
}