首页 > ACM题库 > HDU-杭电 > HDU 4441- Queue Sequence-线段树-[解题报告]HOJ
2015
07-16

HDU 4441- Queue Sequence-线段树-[解题报告]HOJ

Queue Sequence

问题描述 :

There’s a queue obeying the first in first out rule. Each time you can either push a number into the queue (+i), or pop a number out from the queue (-i). After a series of operation, you get a sequence (e.g. +1 -1 +2 +4 -2 -4). We call this sequence a queue sequence.

Now you are given a queue sequence and asked to perform several operations:

1. insert p
First you should find the smallest positive number (e.g. i) that does not appear in the current queue sequence, then you are asked to insert the +i at position p (position starts from 0). For -i, insert it into the right most position that result in a valid queue sequence (i.e. when encountered with element -x, the front of the queue should be exactly x).
For example, (+1 -1 +3 +4 -3 -4) would become (+1 +2 -1 +3 +4 -2 -3 -4) after operation ‘insert 1′.
2. remove i
Remove +i and -i from the sequence.
For example, (+1 +2 -1 +3 +4 -2 -3 -4) would become (+1 +2 -1 +4 -2 -4) after operation ‘remove 3′.
3. query i
Output the sum of elements between +i and -i. For example, the result of query 1, query 2, query 4 in sequence (+1 +2 -1 +4 -2 -4) is 2, 3(obtained by -1 + 4), -2 correspond.

输入:

There are less than 25 test cases. Each case begins with a number indicating the number of operations n (1 ≤ n ≤ 100000). The following n lines with be ‘insert p’, ‘remove i’ or ‘query i’(0 ≤ p ≤ length (current sequence), 1 ≤ i, i is granted to be in the sequence).
In each case, the sequence is empty initially.
The input is terminated by EOF.

输出:

There are less than 25 test cases. Each case begins with a number indicating the number of operations n (1 ≤ n ≤ 100000). The following n lines with be ‘insert p’, ‘remove i’ or ‘query i’(0 ≤ p ≤ length (current sequence), 1 ≤ i, i is granted to be in the sequence).
In each case, the sequence is empty initially.
The input is terminated by EOF.

样例输入:

10
insert 0
insert 1
query 1
query 2
insert 2
query 2
remove 1
remove 2
insert 2
query 3
6
insert 0
insert 0
remove 2
query 1
insert 1
query 2

样例输出:

Case #1:
2
-1
2
0
Case #2:
0
-1

转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents   
by—cxlove 

题目:每次有三种操作

insert pos  表示在pos插入一个数,这个数是最小的正数没有在序列中出现的。而且还要在某个位置插入他的相反数

remove num 表示把num以及-num去掉

query num 把num与-num之间的数求和输出

http://acm.hdu.edu.cn/showproblem.php?pid=4441 

首先说一下insert操作

对于需要插入的那个数,维护一个线段树表示区间最值就OK了,随意搞吧。

那么对于插入的正数,位置已经告诉了,就简单了,对于那个负数,要求的位置是最右边的满足条件的。

其实题目要求的就是正数的顺序和负数的是一样的。

那么如果当前数字i前面有n个正数,那么表示-i前面也有n个负数,而且又需要是最右边的

就是第 n+1个负数的左边,如果没有n+1个负数,那就看插到最后(所以代码中有一个判断)

那么怎么找第n+1个负数呢,只需要维护一个值,表示负数的个数就行了,我还维护了正数有多少个,其实没啥用,TAT

然后是remove操作,只要记录num以及-num在Splay中的编号就可以了。

那么 就可以很轻松的通过编号找到结点,删除

我存的是编号,那么在删除的时候,先旋转至根,找到他的左边有多少个数,这样得到他的位置,就好处理了

最后是query操作,由于 我们存了编号

那么通过Splay很快能找到中间的区间,维护一个区间和就OK了

这种数据结构题,代码量很大,给现场短时候1A的队伍跪烂啊,需要非常注意细节。

写代码的时候简单地加了点注释

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#define inf 1<<30
#define M 200005
#define N 200005
#define maxn 300005
#define eps 1e-10
#define zero(a) fabs(a)<eps
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson step<<1
#define rson step<<1|1
#define MOD 1000000009
#define sqr(a) ((a)*(a))
#define Key_value ch[ch[root][1]][0]
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
struct Splay_tree{
    LL sum[N];
    int size[N],pre[N],val[N],tot;
    int ch[N][2],tot1,root,s[N],tot2,cnt[N][2];    //cnt[0]表示的是正数个数,cnt[1]表示的是负数个数
    //debug部分copy from hh
    void Treaval(int x) {
        if(x) {
            Treaval(ch[x][0]);
            printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,val = %2c \n",x,ch[x][0],ch[x][1],pre[x],size[x],val[x]);
            Treaval(ch[x][1]);
        }
    }
    void debug() {printf("%d\n",root);Treaval(root);}
    //以上Debug
    inline void NewNode(int &r,int k,int father){
        r=++tot1;
        ch[r][0]=ch[r][1]=0;
        cnt[r][0]=k>0;
        cnt[r][1]=k<0;
        sum[r]=k;
        pre[r]=father;
        size[r]=1;
        val[r]=k;
    }
    inline void Push_Up(int x){
        if(x==0) return ;
        int l=ch[x][0],r=ch[x][1];
        size[x]=size[l]+size[r]+1;
        cnt[x][0]=cnt[l][0]+cnt[r][0]+(val[x]>0);
        cnt[x][1]=cnt[l][1]+cnt[r][1]+(val[x]<0);
        sum[x]=(LL)sum[l]+sum[r]+val[x];
    }
    inline void Init(){
        tot1=tot2=root=tot=0;
        ch[root][0]=ch[root][1]=pre[root]=size[root]=sum[0]=cnt[0][0]=cnt[0][1]=0;
        val[root]=0;
        NewNode(root,0,0);
        NewNode(ch[root][1],0,root);
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    inline 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;
        Push_Up(y);
    }
    inline void Splay(int r,int goal){
        while(pre[r]!=goal){
            if(pre[pre[r]]==goal)
                Rotate(r,ch[pre[r]][0]==r);
            else{
                int y=pre[r];
                int kind=(ch[pre[y]][0]==y);
                if(ch[y][kind]==r){
                    Rotate(r,!kind);
                    Rotate(r,kind);
                }
                else{
                    Rotate(y,kind);
                    Rotate(r,kind);
                }
            }
        }
        Push_Up(r);
        if(goal==0) root=r;
    }
    inline void RotateTo(int k, int goal) {
        int x=root;
        while(k!=size[ch[x][0]]+1){
            if (k<=size[ch[x][0]]){
                x=ch[x][0];
            }else{
                k-=(size[ch[x][0]]+1);
                x=ch[x][1];
            }
        }
        Splay(x,goal);
    }
    inline int Get_Kth(int r,int k){
        int t=size[ch[r][0]]+1;
        if(t==k) return r;
        if(t>k) return Get_Kth(ch[r][0],k);
        else return Get_Kth(ch[r][1],k-t);
    }
    inline int Insert(int pos,int k){
        tot++;
        RotateTo(pos,0);
        RotateTo(pos+1,root);
        NewNode(Key_value,k,ch[root][1]);
        Push_Up(ch[root][1]);
        Push_Up(root);
        return Key_value;
    }
    inline void Delete(int r){
        tot--;
        Splay(r,0);
        int pos=size[ch[r][0]];
        RotateTo(pos,0);
        RotateTo(pos+2,root);
        s[tot2++]=Key_value;
        Key_value=0;
        Push_Up(ch[root][1]);
        Push_Up(root);
    }
    //找第n+1个负数的位置
    inline int find(int x,int n){
        int l=ch[x][0],r=ch[x][1];
        if(cnt[l][1]==n&&val[x]<0) {Splay(x,0);return size[ch[root][0]];}
        else if(cnt[l][1]>=n+1) return find(l,n);
        else return find(r,n-cnt[l][1]-(val[x]<0));
    }
    inline void InOrder(int r){
        if(r==0)
            return;
        InOrder(ch[r][0]);
        printf("%d ",val[r]);
        InOrder(ch[r][1]);
    }
    inline void Print(){
        RotateTo(1,0);
        RotateTo(tot+2,root);
        InOrder(Key_value);
        printf("\n");
    }
}splay;
struct Segment_tree{
    int left,right,mmin;
}L[N*4];
int position[N][2];
void Push_Up(int step){
    L[step].mmin=min(L[lson].mmin,L[rson].mmin);
}
void Bulid(int step,int l,int r){
    L[step].left=l;
    L[step].right=r;
    if(l==r){
        L[step].mmin=l;
        return;
    }
    int m=(l+r)/2;
    Bulid(lson,l,m);
    Bulid(rson,m+1,r);
    Push_Up(step);
}
//flag为1表示是插入,flag为0表示是删除
void Update(int step,int pos,int flag){
    if(L[step].left==pos&&pos==L[step].right){
        if(flag) L[step].mmin=inf;
        else L[step].mmin=L[step].left;
        return ;
    }
    int m=(L[step].left+L[step].right)/2;
    if(pos<=m) Update(lson,pos,flag);
    else Update(rson,pos,flag);
    Push_Up(step);
}
void Insert(int pos){
    int num=L[1].mmin;
    position[num][0]=splay.Insert(pos+1,num);
    splay.Splay(position[num][0],0);
    int n=splay.cnt[splay.ch[splay.root][0]][0];  //表示在+i之前有多少个正数
    //将-i插入到第n+1个负数左边
    if(splay.cnt[splay.root][1]<=n){
        int m=splay.size[splay.root]-2+1;
        position[num][1]=splay.Insert(m,-num);
        Update(1,num,1);  //插入线段树
    }
    else{
        int m=splay.find(splay.root,n);   //表示第n+1个负数是第m个数
        position[num][1]=splay.Insert(m,-num);
        Update(1,num,1);  //插入线段树
    }
}
void Remove(int k){
    splay.Delete(position[k][0]);
    splay.Delete(position[k][1]);
    Update(1,k,0);   //从线段树中移除
}
LL Query(int k){
    splay.Splay(position[k][0],0);
    splay.Splay(position[k][1],splay.root);
    return splay.sum[splay.ch[splay.ch[splay.root][1]][0]];
}
int main(){
    int cas=0,q;
    while(scanf("%d",&q)!=EOF){
        printf("Case #%d:\n",++cas);
        splay.Init();
        Bulid(1,1,q);
        while(q--){
            char str[10];int k;
            scanf("%s%d",str,&k);
            if(str[0]=='i') Insert(k);
            else if(str[0]=='r') Remove(k);
            else printf("%I64d\n",Query(k));
           // splay.Print();
        }
    }
    return 0;
}



版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/8122288