hdu 5929 Baic Data Structure法則シミュレーション

Mr.Frog learned a baic data structure recently,which is caled stack.The re some baic operations of stack:街PUSH x:put x on the top of the stack,x must be 0 or 1.POP:throw the element the the protement the Tance「Five points coexist with a circule「easury、hecompes up with some exciting operation s:や街REVERE:Just reverse the stack、the bottom element becompes the top element of the stack、and the element just aboote the bottom element becommes the element just below the top elemens...and so on.ややややややQUEry:Print the value which with such way:Take the element from top bottone,from.  atop−1,⋯,a 1 is corese ponding to the element of the Stark from top to the bottom,value=aop nad atop−1 nand…nand a 1.Note that the Stock will not change after QUnit the operation.Specemic,Spective,Specemic,theNAND is a baic binary operation:街0 nand 0=1列0 nand 1=1列1 nad 0=1街街
1 nand 1=0
Because Mr.Froog needs to some ting contributions now,you shou shou sh help him finish this data structure:print the answer to each QULY,or tell hit is invalid.
InputThe first line contains only one integer T(
T≦20)、which indicates the number of test cases.
For each test case,the first line contains only one integers N
2≦N≦200000)、indicating the number of operations.
In the follwing Nライン、the i-th line contains one of these operations below:
街PUSH x(x
must be 0 or 1)
ポップ
とREVERSE
チェックアウト
It is garanted that the current stack will not be empy while dong POP operation.
Output For each test case,first output one line「Case菗x:w,where x is the case number(starting from 1).The n several line follow,  i-th line contains an integer indicating the answer to the i-th QUERY operation.Specially,if the i-th QULY is invalid,jusprint"
Invalid.「(without quot tes).(Please see the sample for more details.)
Sample Input

2
8
PUSH 1
QUERY
PUSH 0
REVERSE
QUERY
POP
POP
QUERY
3
PUSH 0
REVERSE
QUERY

Sample Output

Case #1:
1
1
Invalid.
Case #2:
0

件名:
          アナログのデータ構造は元のstackよりも多くなりました.
           クエリ機能はスタックの一番上から、下に向かってnand演算を行います.
最後の要素が0なら、
最後の要素が0なら、answerは0です.
        スタックの底から一番近い0まで計算した後、answerは1で、残りの1のanswerを計算します.

#include
#include
#include
#include
#include
#include
using namespace std;
#define Size 200005
int dequee[Size*2],topp,bb,sizes;
struct bds
{
	int top,b;
	int flag,size;
	void inline init() { top=Size-1;b=Size;topp=top;bb=b;flag=1;size=0;sizes=0;} 
	void inline push(int x)
	{
	    if(flag) top++; else top--;
		if(!x) {
			if(flag) topp++,dequee[topp]=top;
			else bb--,dequee[bb]=top;
			sizes++;
		       } 
		size++;
	}
	int inline pop()
	{
		int x=0;
		if(flag) {if(dequee[topp]==top) x=1;top--;}
		if(!flag) { if(dequee[bb]==top) x=1;top++;}
		if(--size<0) return 1;
		if(x) {
			if(flag) topp--;
			else bb++; 
			sizes--;
		       }
		return 0;
	}
	int query()
	{
		int pos;
		if(size==0) return 3;
		if(size==1) return !sizes;
		if(sizes==0) return size&1;
		pos=dequee[(flag?bb:topp)];
		if(pos==b) return 1;
		if(flag&&postop) pos--;
		if(abs(b-pos)&1) return 1;
		return 0;
	}
	void inline reverse()
	{
		top=top+b;b=top-b;top=top-b;
		flag = !flag;
	}
};
int main()
{
	int t,q,kase=0,x;
	char qu[15];
	bds basic1;
	scanf("%d",&t);
	while(t--)
	{
		basic1.init();
		scanf("%d",&q);
		printf("Case #%d:
",++kase);
		while(q--)
		{
		  scanf("%s",qu);
		  if(qu[0]=='P')
		  {
		  	 if(qu[1]=='U') { scanf("%d",&x); basic1.push(x);}
			 else basic1.pop();
		  }
		  if(qu[0]=='R') basic1.reverse();
		  if(qu[0]=='Q') 
		  {
		  	 int ans=basic1.query();
		  	 if(ans==3) printf("Invalid.
");
		  	 else printf("%d
",ans);
		  } 
		}
	}
}