hdu4441 Queue Sequence

hdu4441 Queue Sequence

​​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:

insert pFirst 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’.remove iRemove +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’.query iOutput 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

Source 2012 Asia Tianjin Regional Contest 模拟队列操作 开设两个数组ta[],tb[]分别记录正数和负数在splay中的下标 每次操作的时候看一下p位置前面有多少个正数记为sz 然后 首先正数就查在p这个位置 负数怎么办找到p后面有sz个负数 插在它的前面即可 然后其他就都是正常的splay操作了 维护区间和 注意long long 相当于在splay中维护了这个区间有多少个正数有多少个负数

#include#include#include#include#include#define N 220000#define ll long long#define inf 0x3f3f3f3fusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=getchar(); return x*f;}int sizen[N],sizep[N],ta[N],tb[N],size[N],fa[N],n,root,c[N][2],v[N],num;ll sum[N];inline void update(int x){ size[x]=size[c[x][0]]+size[c[x][1]]+1; sizen[x]=sizen[c[x][0]]+sizen[c[x][1]]+(v[x]<0); sizep[x]=sizep[c[x][0]]+sizep[c[x][1]]+(v[x]>0); sum[x]=sum[c[x][0]]+sum[c[x][1]]+v[x];}inline void rotate(int x,int &tar){ int y=fa[x],z=fa[y]; if (y==tar) tar=x;else c[z][c[z][1]==y]=x; int l=c[y][1]==x,r=l^1; fa[c[x][r]]=y;fa[y]=x;fa[x]=z; c[y][l]=c[x][r];c[x][r]=y;update(y);update(x);}inline void splay(int x,int &tar){ while(x!=tar){ int y=fa[x],z=fa[y]; if(y!=tar){ if (c[y][0]==x^c[z][0]==y) rotate(x,tar);else rotate(y,tar); }rotate(x,tar); }}inline int find(int x,int sz){ int l=c[x][0],r=c[x][1]; if (size[l]+1==sz) return x; if (sz<=size[l]) return find(l,sz);else return find(r,sz-size[l]-1);}inline void insert1(int &x,int vv,int f){ if (!x){x=++num;fa[x]=f;v[x]=vv;size[x]=sizep[x]=1;update(x);splay(x,root);return;} insert1(c[x][1],vv,x);}inline void insert2(int &x,int p,int vv,int f){ if (!x){x=++num;fa[x]=f;v[x]=vv;size[x]=sizen[x]=1;update(x);splay(x,root);return;} int &l=c[x][0],&r=c[x][1]; if (p<=sizen[l]+(v[x]<0)) insert2(l,p,vv,x);else insert2(r,p-(sizen[l]+(v[x]<0)),vv,x);} inline void del(int x){ splay(x,root);int pre=c[root][0],succ=c[root][1]; while(c[pre][1]) pre=c[pre][1];while(c[succ][0]) succ=c[succ][0]; splay(succ,root);splay(pre,c[root][0]);c[pre][1]=0;update(pre);update(root);}inline void init(){ num=2;memset(size,0,sizeof(size));memset(sizen,0,sizeof(sizen)); memset(fa,0,sizeof(fa));memset(c,0,sizeof(c));memset(sizep,0,sizeof(sizep)); size[1]=2;v[1]=-inf;fa[2]=1;root=1;c[1][0]=2;v[2]=inf;update(2);update(1);}int main(){ freopen("hdu4441.in","r",stdin); int test=0; while(~scanf("%d",&n)){printf("Case #%d:\n",++test); root=0;priority_queue,greater >q; for (int i=1;i<=n;++i) q.push(i);init(); for (int t=1;t<=n;++t){ char op[10];scanf("%s",op); if (op[0]=='i'){ int p=read(),x=q-();q.pop(); int xx=find(root,p+2);splay(xx,root);splay(2,c[xx][0]);int sz=sizep[c[2][1]]; insert1(c[root][0],x,root);ta[x]=num;insert2(root,sz+1,-x,root);tb[x]=num;//print(root);puts(""); } if (op[0]=='r'){ int x=read();q.push(x);del(ta[x]);del(tb[x]); } if (op[0]=='q'){ int x=read();splay(tb[x],root);splay(ta[x],c[root][0]);printf("%lld\n",sum[c[ta[x]][1]]); } } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。