題意：

定義一個可以反轉棧頂的棧，有push，pop操作，每次push只push 0,1這兩種元素，除此之外還有reverse操作，即把棧頂反轉為棧尾， 棧尾反轉為棧頂，另外有一個query操作，查詢的是從棧頂到棧尾的元素進行一種nand運算所得到的值，nand運算其實就是&&運算的非，具體規則如下：

? 0 nand 0 = 1 ? 0 nand 1 = 1 ? 1 nand 0 = 1 ? 1 nand 1 = 0

解題思路：

暴力的去查詢肯定要t，觀察這種運算的規律，任何數和0運算的結果都是1，所以對于查詢的結果，我們考慮最后一個0出現的位置，從棧頂到這個0元素運算得到的結果一定都是1，而0之后的元素就都是1了，1nand1為0,1nand1nand1為1，我們可以得到偶數個1nand運算后是0， 奇數個1nand運算后是1,所以整個棧元素的nand值只要在知道最后一個0所在的位置，我們就可以求出了結果了。

代碼：

#include <bits/stdc++.h>using namespace std;int a[410004];int nand[410004];int zero[410005];int main(){   int t;   int e=1;   cin>>t;   while(t--)   {    int n;    scanf("%d", &n);    int i, j;    //memset(nand, 0, sizeof(nand));    //memset(zero, 0, sizeof(zero));    int head, tail;    head=tail=200005;     int p=1;    int isfirst=1, x;    char oper[33];    PRintf("Case #%d:/n", e++);    int l, r;    l=r=200005;//    l=r=0;     for(i=0; i<n; i++)    {          //printf("%d %d/n", head, tail);      scanf("%s", oper);     if(strcmp(oper, "PUSH")==0)     {       if(p)       {	 scanf("%d", &x);    	 a[head--]=x;	 if(isfirst)	 {	    isfirst=0;	    tail++;//	    nand[i]=x;            if(x==0)zero[l--]=head+1, r++;	    continue;	 }         if(x==0) { zero[l--]=head+1;if(l+1==r)r++;};       }       else       {         scanf("%d", &x);	 a[tail++]=x;	if(isfirst)	{	   isfirst=0;	   head--;	   if(x==0) zero[r++]=tail-1, l--;	   continue;	}	          if(x==0){zero[r++]=tail-1;if((r-1)==l)l--;}       }     }     if(strcmp(oper, "POP")==0)     {	if(p)	{	   head++;	   if(a[head]==0)	   {	     l++;	   }	}	else	{	   tail--;	//   cout<<a[tail]<<endl;	   if(a[tail]==0)	   {	      r--;	   }	}     }     if(strcmp(oper, "REVERSE")==0){ p=!p;}      if(strcmp(oper, "QUERY")==0)     {	if(isfirst || head==(tail-1))printf("Invalid./n");	else 	{          if(p)	  {	     if(r-l>1)	     {	//	cout<<zero[r-1]<<endl; 		if((tail-zero[r-1])%2==1) 		{		   nand[i]=1;		}	        else		{		   nand[i]=0;		}	        if(zero[r-1]==head+1)nand[i]=!nand[i];		    }	     else	     {	//	cout<<r<<" "<<l<<endl;                if((tail-head-1)%2==1)nand[i]=1;		else nand[i]=0;	     }	  }	  else	  {	      if((r-l)>1)	      {                if((zero[l+1]-head)%2==1)		{ 		  nand[i]=1; 		}else		{		   nand[i]=0;		}		if(zero[l+1]==tail-1)nand[i]=!nand[i];	      }else	      { 		if((tail-head-1)%2==1)nand[i]=1;		else nand[i]=0;	      }	  }	  printf("%d/n", nand[i]);	}     }    }    }   }