【HDU 4441】 Queue Sequence(Splay)

這道題也是一道splay的基礎操作的集合題，主要包含有三種操作：

insert p ：在p位置插入目前未出現的最小的數，如目前出現了1 2 3 6，那再插入4

且正數和負數同時插入，而負數插入的位置要求：該負數左邊負數的個數和該數的相反數的左邊的正數的個數一樣多且最為靠右

則若2左邊有4個正數，那麼-2就應該插入在滿足左邊有4個負數的最靠右的位置

而如何找到最小的數呢？用一個優先隊列維護一下應該不難想到

remove p:删除p以及-p。這個操作隻需要在插入的時候記錄一下p和-p的位址就好了

query p：計算從p到 -p的和為多少。隻需要将p旋為根，将-p旋為右子樹，那麼關鍵樹就是區間的和，維護一下子樹和應該OK的

下面是代碼：

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define keytree (ch[ ch[root][1] ][0])
typedef long long LL;
using namespace std;
const int SIZEN = 200005;
struct SplayTree{
    int ch[SIZEN][2];
    int pre[SIZEN];
    int sz[SIZEN];
    int top,top2,root,rest;
    priority_queue<int,vector<int>,greater<int> > q;

    inline void pushup(int x){
        sz[x] = sz[ ch[x][0] ] + sz[ ch[x][1] ] + 1;
        cnt[x] = cnt[ ch[x][0] ] + cnt[ ch[x][1] ] + (val[x] < 0);
        sum[x] = sum[ ch[x][0] ] + sum[ ch[x][1] ] + val[x];
    }
    inline void Rotate(int x,int f){
        int y = pre[x];
        ch[y][!f] = ch[x][f];
        pre[ ch[x][f] ] = y;
        pre[x] = pre[y];
        if(pre[y]) ch[ pre[y] ][ ch[ pre[y] ][1] == y ] = x;
        ch[x][f] = y;
        pre[y] = x;
        pushup(y);
    }
    inline void Splay(int x,int goal){
        while(pre[x] != goal){
            if(pre[ pre[x] ] == goal)
                Rotate(x,ch[ pre[x] ][0] == x);
            else{
                int y = pre[x],z = pre[y];
                int f = ch[z][0] == y;
                if(ch[y][f] == x){
                    Rotate(x,!f),Rotate(x,f);
                }
                else{
                    Rotate(y,f),Rotate(x,f);
                }
            }
        }
        pushup(x);
        if(goal == 0) root = x;
    }
    inline void Rotateto(int k,int goal){
        int x = root;
        while(sz[ ch[x][0] ] != k){
            if(sz[ ch[x][0] ] > k){
                x = ch[x][0];
            }
            else{
                k -= sz[ ch[x][0] ] + 1;
                x = ch[x][1];
            }
        }
        Splay(x,goal);
    }
    inline void init(){
        ch[0][0] = ch[0][1] = pre[0] = 0;
        sz[0] = val[0] = sum[0] = 0;
        cnt[0] = 0;
        while(!q.empty()) q.pop();
        top = top2 = root = rest = 0;

        root = Newnode(0);
        ch[root][1] = Newnode(0);
        sz[root] = 2;
        pre[ ch[root][1] ] = root;
        pre[root] = 0;
    }
    int Newnode(int c){
        int x = ++top;
        ch[x][0] = ch[x][1] = pre[0] = 0;
        val[x] = sum[x] = c;
        sz[x] = 1;
        cnt[x] = (c < 0);
        if(c > 0) loc[c] = x;
            else n_loc[-c] = x;
        return x;
    }
    int Find(int k,int x){
        if(cnt[ ch[x][0] ] + 1 == k && val[x] < 0) return x;
        if(cnt[ ch[x][0] ] >= k) return Find(k,ch[x][0]);
            else return Find(k - cnt[ ch[x][0] ] - (val[x] < 0),ch[x][1]);
    }
    inline int findmax(int x){
        while(ch[x][1]) x = ch[x][1];
        return x;
    }
    inline int findmin(int x){
        while(ch[x][0]) x = ch[x][0];
        return x;
    }
    inline void debug(){
        printf("root:%d\n",root);
        Travel(root);
    }
    void Travel(int x){
        if(ch[x][0]) Travel(ch[x][0]);
        printf("node:%d lson:%d rson:%d pre:%d sz:%d cnt:%d val:%d\n",x,ch[x][0],ch[x][1],pre[x],sz[x],cnt[x],val[x]);
        if(ch[x][1]) Travel(ch[x][1]);
    }
    void Insert(){
        int c,p;
        scanf(" %d",&p);
        if(!q.empty()) {c = q.top(),q.pop();}
            else c = ++top2;
        Rotateto(p,0);
        Rotateto(p + 1,root);
        keytree = Newnode(c);
        rest++;
        pre[keytree] = ch[root][1];
        pushup(ch[root][1]);
        pushup(root);
        Splay(keytree,0);
        int n_cnt = sz[ ch[root][0] ] - cnt[ ch[root][0] ];
        if(cnt[root]  < n_cnt){
            Rotateto(rest,0);
            Rotateto(rest + 1,root);
            keytree = Newnode(-c);
            pre[keytree] = ch[root][1];
            pushup(ch[root][1]);
            pushup(root);
        }
        else{
            int lloc = Find(n_cnt,root);
            Splay(lloc,0);
            int x = findmax(ch[root][0]);
            Splay(x,0);
            Splay(lloc,root);
            keytree = Newnode(-c);
            pre[keytree] = ch[root][1];
            pushup(ch[root][1]);
            pushup(root);
        }
        rest++;
    }
    inline void del(int x){
        Splay(x,0);
        if(!ch[root][0]){
            root = ch[root][1];
            pre[root] = 0;
            return;
        }
        int tmp = findmax(ch[root][0]);
        Splay(tmp,root);

        ch[ ch[root][0] ][1] = ch[root][1];
        pre[ ch[root][1] ] = ch[root][0];
        root = ch[root][0];
        pre[root] = 0;
        pushup(root);
    }
    inline void Del(){
        int c;
        scanf("%d",&c);
        del(loc[c]);
        del(n_loc[c]);
        q.push(c);
        rest -= 2;
    }
    inline void Query(){
        int c;
        scanf("%d",&c);
        Splay(loc[c],0);
        Splay(n_loc[c],root);
        printf("%I64d\n",sum[keytree]);
    }
    LL sum[SIZEN];
    int val[SIZEN],cnt[SIZEN];
    int n_loc[SIZEN],loc[SIZEN];
};
SplayTree spt;
void solve(int n){
    char op[10];
    spt.init();
    for(int i = 0 ; i < n ; i ++){
        scanf(" %s",op);
        if(op[0] == 'i') spt.Insert();
        else if(op[0] == 'r') spt.Del();
        else if(op[0] == 'q') spt.Query();
    }
}
int main()
{
    int n,txt = 1;
    while(scanf("%d",&n) != EOF){
        printf("Case #%d:\n",txt++);
        solve(n);
    }
}