时间复杂度理论是 $O(n+q)$ 然而出了点问题？

有大佬能看一下吗？

#include<bits/stdc++.h>
using namespace std;
const int INF=1e7;
bool x[INF],mark[INF];
int LeaF[INF][3],Op[INF],tot,n,q;
stack<int>stk;
char s[INF];
void Build_Tree()
{
	tot=n;
	for(int i=0;i<strlen(s);i++)
	{
		switch(s[i])
		{
			case 'x':{
				int temp=0;
				i++;
				while(s[i]!=' ')
				{
					temp=temp*10+s[i]-'0';
					i++;
				}
				i--;
				stk.push(temp);
				break;
			}
			case '&':{
				int L=stk.top();
				stk.pop();
				int R=stk.top();
				stk.pop();
				stk.push(++tot);
				Op[tot]=0;
				LeaF[tot][0]=L;
				LeaF[tot][1]=R;
				break;
			}
			case '|':{
				int L=stk.top();
				stk.pop();
				int R=stk.top(); 
				stk.pop();
				stk.push(++tot);
				Op[tot]=1;
				LeaF[tot][0]=L;
				LeaF[tot][1]=R;
				break;
			}
			case '!':{
				int L=stk.top();
				stk.pop();
				stk.push(++tot);
				Op[tot]=2;
				LeaF[tot][0]=L;
				break;
			}
			default:continue;
		}
	}
}
bool Calculate_Tree(int cur)
{
	if(cur<=n)
		return x[cur];
	bool L=Calculate_Tree(LeaF[cur][0]),R=Calculate_Tree(LeaF[cur][1]);
	switch(Op[cur])
	{
		case 0:{
			x[cur]=L&R;
			break;
		}
		case 1:{
			x[cur]=L|R;
			break;
		}
		case 2:{
			x[cur]=!L;
			break;
		}
	}
	return x[cur];
}
void Mark(int cur)
{
	mark[cur]=1;
	if(cur<=n)
		return;
	int L=LeaF[cur][0],R=LeaF[cur][1];
	bool a=x[L],b=x[R];
	switch(Op[cur])
	{
		case 0:{
			if(b==1)
				Mark(L);
			if(a==1)
				Mark(R);
			break;
		}
		case 1:{
			if(a==0&&b==0)
			{
				Mark(L);
				Mark(R);
			}
			if(a==1&&b==0)
				Mark(L);
			if(a==0&&b==1)
				Mark(R);
			break;
		}
		case 2:{
			Mark(L);
			break;
		}
	}
}
int main()
{
	//freopen("expr20.in","r",stdin);
	//freopen("expr20.out","w",stdout);
	
	gets(s);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&x[i]);
	Build_Tree();
	Calculate_Tree(tot);
	Mark(tot); 
	bool ans=x[tot];
	//printf("ans=%d\n",ans);
//	for(int i=1;i<=n;i++)
	//	printf("%d ",mark[i]);
	//printf("\n");
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		int TEMP;
		scanf("%d",&TEMP);
		if(mark[TEMP])
			printf("%d\n",1-ans);
		else
			printf("%d\n",ans);
	}
	return 0;
}