2015
07-16

# 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

by—cxlove

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

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

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

#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]
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;
}