Queue Sequence
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
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.
Input
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.
Output
Before each case, print a line "Case #d:" indicating the id of the test case.After each operation, output the sum of elements between +i and -i.
Sample Input
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
Sample Output
Case #1:
2
-1
2
0
Case #2:
0
-1
题目有三种操作:
- insert p,表示在p插入一个数,这个数是最小的正数没有在序列中出现的。而且还要在某个位置插入他的相反数
- delete num,将num和-num从序列中去掉
- query num,求num与-num区间的和
对于insert操作,我们可以用线段树或者树状数组维护mex值,然后进行insert操作,对于插入相反数时,那么如果当前数字i前面有n个正数,那么表示-i前面也有n个负数,而且又需要是最右边的就是第
n+1个负数的左边,如果没有n+1个负数,那就看插到最后。
对于delete操作,我们可以事先记录num和-num的位置,这就很容易删除了。
对于query我们对每个节点记录一个sum,表示其子树的sum和。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 |
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=2e5+10; int sze[maxn],rev[maxn],key[maxn],pre[maxn],ch[maxn][2],cnt[maxn][2]; long long sum[maxn]; int ans[maxn]; int root,tot; inline void newnode(int &x,int fa,int k) { x=++tot; sze[x]=1; rev[x]=ch[x][0]=ch[x][1]=0; pre[x]=fa; key[x]=k; cnt[x][0]=k>0; cnt[x][1]=k<0; sum[x]=k; } inline void Modify(int x) { if (!x) return; rev[x]^=1; } inline void push_down(int x) { if (x&&rev[x]) { swap(ch[x][0],ch[x][1]); Modify(ch[x][0]); Modify(ch[x][1]); Modify(x); } } inline void push_up(int x) { if (!x) return; sze[x]=sze[ch[x][0]]+sze[ch[x][1]]+1; cnt[x][0]=cnt[ch[x][0]][0]+cnt[ch[x][1]][0]+(key[x]>0); cnt[x][1]=cnt[ch[x][0]][1]+cnt[ch[x][1]][1]+(key[x]<0); sum[x]=(long long)sum[ch[x][0]]+sum[ch[x][1]]+key[x]; return; } void build(int &x,int L,int R,int fa) { if (L>R) return ; int M=(L+R)>>1; newnode(x,fa,M); build(ch[x][0],L,M-1,x); build(ch[x][1],M+1,R,x); push_up(x); } void Rotate(int x,int kind) { int y=pre[x]; //push_down(y); //push_down(x); ch[y][!kind]=ch[x][kind]; pre[ch[x][kind]]=y; ch[x][kind]=y; if(pre[y]) { ch[pre[y]][ch[pre[y]][1]==y]=x; } pre[x]=pre[y]; pre[y]=x; push_up(y); push_up(x); } //spaly x to the child of goal,if goal=0, splay x to the root; 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); } } } if (goal==0) root=x; } int Get_kth(int x,int k) { // push_down(x); int tz=sze[ch[x][0]]+1; if (tz==k) return x; if (tz>k) return Get_kth(ch[x][0],k); return Get_kth(ch[x][1],k-tz); } void init() { root=tot=sze[0]=rev[0]=pre[0]=ch[0][0]=ch[0][1]=0; sum[0]=cnt[0][0]=cnt[0][1]=0; newnode(root,0,0); newnode(ch[root][1],root,0); //build(ch[ch[root][1]][0],1,n,ch[root][1]); push_up(ch[root][1]); push_up(root); } inline void RotateTo(int k, int goal) { int x=root; while(k!=sze[ch[x][0]]+1){ if (k<=sze[ch[x][0]]){ x=ch[x][0]; }else{ k-=(sze[ch[x][0]]+1); x=ch[x][1]; } } Splay(x,goal); } inline int Find(int x,int k) { int l=ch[x][0],r=ch[x][1]; if(cnt[l][1]==k&&key[x]<0) { Splay(x,0); return sze[ch[root][0]]; } else if(cnt[l][1]>=k+1) return Find(l,k); else return Find(r,k-cnt[l][1]-(key[x]<0)); } inline int Insert(int x,int k) { RotateTo(x,0); RotateTo(x+1,root); newnode(ch[ch[root][1]][0],ch[root][1],k); push_up(ch[root][1]); push_up(root); int res=ch[ch[root][1]][0]; Splay(res,0); return res; } void Delete(int x) { Splay(x,0); int pos=sze[ch[root][0]]; RotateTo(pos,0); RotateTo(pos+2,root); ch[ch[root][1]][0]=0; push_up(ch[root][1]); push_up(root); } int L[maxn*4],R[maxn*4],minm[maxn*4]; void Push_up(int k) { int lson=k<<1; int rson=(k<<1)+1; minm[k]=min(minm[lson],minm[rson]); } void Build(int k,int l,int r) { L[k]=l; R[k]=r; if (l==r) { minm[k]=l; return ; } int mid=(l+r)/2; int lson=k<<1; int rson=(k<<1)+1; Build(lson,l,mid); Build(rson,mid+1,r); Push_up(k); } void Update(int k,int pos,int flag) { if (L[k]==pos&&pos==R[k]) { if (flag) minm[k]=0x3f3f3f3f; else minm[k]=L[k]; return ; } int mid=(L[k]+R[k])/2; int lson=k<<1; int rson=(k<<1)+1; if (pos<=mid) Update(lson,pos,flag); else Update(rson,pos,flag); Push_up(k); } int position[maxn][2]; int main() { int cas=1; int n; while(~scanf("%d",&n)) { printf("Case #%d:\n",cas++); init(); Build(1,1,n); for (int i=0;i<n;i++) { char op[10]; int p; scanf(" %s%d",op,&p); if (op[0]=='i') { int num=minm[1]; position[num][0]=Insert(p+1,num); int __=cnt[ch[root][0]][0]; if (cnt[root][1]<=__) { position[num][1]=Insert(sze[root]-2+1,-num); } else { position[num][1]=Insert(Find(root,__),-num); } Update(1,num,1); } else if (op[0]=='r') { Delete(position[p][0]); Delete(position[p][1]); Update(1,p,0); } else { Splay(position[p][0],0); Splay(position[p][1],root); printf("%I64d\n",sum[ch[ch[root][1]][0]]); } } } return 0; } |