该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

#include<bits/stdc++.h>
using namespace std;

string s;
int n, a[200005], q;
stack<int> stk;
int ans;  //原始答案
int son[200005][2];  //son[][0]和son[][1]分别表示左右儿子
int sec;
int flag[200005];  //flag[i]=1表示结点i是有非标记的
int f[200005];   //f[i]=1表示结点i是废结点

int dfs(int u, int g){
	a[u] ^= g;  //摩根定律
	if(u <= n) return a[u];
	int x = dfs(son[u][0], g ^ flag[son[u][0]]);
	int y = dfs(son[u][1], g ^ flag[son[u][1]]);
	if(a[u] == 2){
		if(x == 0) f[son[u][1]] = 1;
		if(y == 0) f[son[u][0]] = 1;
		return x & y;
	}
	if(x == 1) f[son[u][1]] = 1;
	if(y == 1) f[son[u][0]] = 1;
	return x | y;
}

void fei(int u){
	if(u <= n) return;
	f[son[u][0]] |= f[u];
	f[son[u][1]] |= f[u];
	fei(son[u][0]);
	fei(son[u][1]);
}

int main(){
	getline(cin, s);
	cin >> n;
	for(int i=1; i<=n; i++) cin >> a[i];
	//构建树
	sec = n;
	for(int i=0; s[i]; i+=2){
		if(s[i] == 'x'){
			int num = 0;
			i++;
			while(isdigit(s[i])) num = num * 10 + s[i] - '0', i++;
			stk.push(num);
			i--;
		}
		else if(s[i] == '&'){
			int x = stk.top(); stk.pop();
			int y = stk.top(); stk.pop();
			++sec;  //新建sec结点
			stk.push(sec);
			son[sec][0] = x;  //sec的左儿子
			son[sec][1] = y;  //sec的右儿子
			a[sec] = 2;  //与
		}
		else if(s[i] == '|'){
			int x = stk.top(); stk.pop();
			int y = stk.top(); stk.pop();
			++sec;  //新建sec结点
			stk.push(sec);
			son[sec][0] = x;  //sec的左儿子
			son[sec][1] = y;  //sec的右儿子
			a[sec] = 3;  //或
		}
		else if(s[i] == '!') flag[stk.top()] ^= 1;
	}
	//得到原始答案
	ans = dfs(sec, flag[sec]);
	
	//预处理处理废点
	fei(sec);
	
	//q次操作
	cin >> q;
	while(q--){
		int x;
		cin >> x;
		cout << (ans ^ !f[x]) << endl;
	}
	return 0;
}