hdu 4441 Queue Sequence (splay + 线段树)

题目大意：

给出一个空的序列，通过插入，删除，查询操作维护。

插入：找到这个序列中还没出现的最小的正数 i 。将他插入到给定的位置，然后还要插入一个  -i  ，将-i 插入到使得正负数的顺序一样的最右边。

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

查询：查询i 和 -i之间的和

思路分析：

首先我们面临的问题就是要找到最小的正数，要用一个线段树维护。

然后插入操作：

首先+i 方便处理，然后记下他在splay中的编号。那么-i的位置我们是要自己去解决的。

在splay上记录这个区间的正负数情况。那么我们先求出插入的正数前面有多个正数。假设有n个。那么我们就再插入 -i到第n+1个负数前面。

删除和查询都是splay 的基本操作  没什么可以说的了。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#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<<siz[root]<<endl;
            char str[100];
            int tag;
            scanf("%s%d",str,&tag);
            if(str[0]==‘i‘)
            {
                insert(tag);
            }
            else if(str[0]==‘r‘)
            {
                remove(tag);
                update(1,1,m,tag,0);
            }
            else
            {
                Splay(pos1[tag],0);
                Splay(pos2[tag],root);
                printf("%I64d\n",sum[keyTree]);
            }
            //debug();
        }
    }
    return 0;
}

hdu 4441 Queue Sequence (splay + 线段树),布布扣,bubuko.com

hdu 4441 Queue Sequence (splay + 线段树)

原文：http://blog.csdn.net/u010709592/article/details/21482517