hdu 4441 Queue Sequence (splay + 線段樹)

題目大意：

給出一個空的序列，通過插入，刪除，查詢操作維護。

插入：找到這個序列中還沒出現的最小的正數 i 。將他插入到給定的位置，然後還要插入一個 -i ，將-i 插入到使得正負數的順序一樣的最右邊。

刪除：刪除 i 和 -i的位置

查詢：查詢i 和 -i之間的和

思路分析：

首先我們面臨的問題就是要找到最小的正數，要用一個線段樹維護。

然後插入操作：

首先+i 方便處理，然後記下他在splay中的編號。那麼-i的位置我們是要自己去解決的。

在splay上記錄這個區間的正負數情況。那麼我們先求出插入的正數前面有多個正數。假設有n個。那麼我們就再插入 -i到第n+1個負數前面。

刪除和查詢都是splay 的基本操作 沒什麼可以說的了。

#include 
#include 
#include 
#include 
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#define maxn 200005
#define inf 0x3f3f3f3f
#define keyTree (ch[ch[root][1]][0])

using namespace std;
typedef long long LL;

int S[maxn],que[maxn],ch[maxn][2],pre[maxn],siz[maxn];
int root,top1,top2;
int val[maxn],a[maxn];
int pos1[maxn],pos2[maxn];
LL sum[maxn];
int z[maxn],f[maxn],m;

void Treaval(int x)
{
    if(x)
    {
        Treaval(ch[x][0]);
        printf("結點%2d:左兒子 %2d 右兒子 %2d 父結點 %2d size = %2d ,val = %2d , sum = %2lld z = %d f=%d\n",x,ch[x][0],ch[x][1],pre[x],siz[x],val[x],sum[x],z[x],f[x]);
        Treaval(ch[x][1]);
    }
}
void debug()
{
    printf("root=%d\n",root);
    Treaval(root);
}

void New(int &x,int PRE,int v)
{
    x=++top1;

    ch[x][0]=ch[x][1]=0;
    siz[x]=1;
    pre[x]=PRE;

    val[x]=v;
    sum[x]=v;
    z[x]=v>0;
    f[x]=v<0;
}
void pushup(int x)
{
    siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+(LL)val[x];
    z[x]=z[ch[x][0]]+z[ch[x][1]]+(val[x]>0);
    f[x]=f[ch[x][0]]+f[ch[x][1]]+(val[x]<0);
}

void Rotate(int x,int kind)
{
    int y=pre[x];

    ch[y][!kind]=ch[x][kind];
    pre[ch[x][kind]]=y;
    if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;
    pre[x]=pre[y];
    ch[x][kind]=y;
    pre[y]=x;
    pushup(y);
}
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];
            int kind=ch[pre[y]][0]==y;
            if(ch[y][kind]==x){
                Rotate(x,!kind);
                Rotate(x,kind);
            }
            else {
                Rotate(y,kind);
                Rotate(x,kind);
            }
        }
    }
    pushup(x);
    if(goal==0)root=x;
}

void RotateTo(int k,int goal)
{
    int r=root;
    while(siz[ch[r][0]]+1!=k)
    {
        if(k<=siz[ch[r][0]])
        {
            r=ch[r][0];
        }
        else
        {
            k-=siz[ch[r][0]]+1;
            r=ch[r][1];
        }
    }
    Splay(r,goal);
}

void init()
{
    root=top1=top2=0;
    ch[0][0]=ch[0][1]=siz[0]=pre[0]=0;

    New(root,0,0);
    New(ch[root][1],root,0);

    siz[root]=2;
    pushup(ch[root][1]);
    pushup(root);
}

int tre[maxn<<2];
void push_up(int num)
{
    tre[num]=min(tre[num<<1],tre[num<<1|1]);
}
void build(int num,int s,int e)
{
    if(s==e)
    {
        tre[num]=s;
        return;
    }
    int mid=(s+e)>>1;
    build(lson);
    build(rson);
    push_up(num);
}

void update(int num,int s,int e,int pos,int val)
{
    if(s==e)
    {
        tre[num]=val?inf:s;
        return;
    }
    int mid=(s+e)>>1;
    if(pos<=mid)update(lson,pos,val);
    else update(rson,pos,val);
    push_up(num);
}
int Splay_insert(int pos,int v)
{
    RotateTo(pos,0);
    RotateTo(pos+1,root);

    New(keyTree,ch[root][1],v);
    pushup(ch[root][1]);
    pushup(root);
    return keyTree;
}
int kth(int x,int n)
{
    int ls=ch[x][0],rs=ch[x][1];
    if(f[ls]==n && val[x]<0){Splay(x,0);return siz[ch[root][0]];}
    else if(f[ls]>n)return kth(ls,n);
    else return kth(rs,n-f[ls]-(val[x]<0));
}

void remove(int x)
{
    Splay(pos1[x],0);
    int P=siz[ch[root][0]];
    RotateTo(P,0);
    RotateTo(P+2,root);
    keyTree=0;
    pushup(ch[root][1]);
    pushup(root);

    Splay(pos2[x],0);
    P=siz[ch[root][0]];
    RotateTo(P,0);
    RotateTo(P+2,root);
    keyTree=0;
    pushup(ch[root][1]);
    pushup(root);
}
void insert(int pos)
{
    int num=tre[1];

    pos1[num]=Splay_insert(pos+1,num);

    Splay(pos1[num],0);

    int n=z[ch[root][0]];

    if(f[root]<=n)
    {
        int t=siz[root]-2+1;
        pos2[num]=Splay_insert(t,-num);
    }
    else
    {
        int t=kth(root,n);
        pos2[num]=Splay_insert(t,-num);
    }
    update(1,1,m,num,1);
}

int main()
{
    int cas=1;

    while(scanf("%d",&m)!=EOF)
    {
        printf("Case #%d:\n",cas++);
        init();
        build(1,1,m);

        for(int sss=1;sss<=m;sss++)
        {
           // cout<