$WA$ $on$ #11 #13 #14 #16 #18 #20

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6;
string s,str;
int n,q;
bool a[MAXN];
struct node{
	int idx,lson,rson;
	bool val,rev;
	char op;
}t[MAXN];
int indexs,times;
stack<int> stk;
void build(int k,int opt){
	if(t[k].idx<=n){
		if(opt^t[k].rev)t[k].val=!t[k].val;
		return;
	}
	if(t[k].op=='&'){
		build(t[k].lson,opt^t[k].rev);
		build(t[k].rson,opt^t[k].rev);
		if(opt^t[k].rev){
			t[k].op='|';
			t[k].val=t[t[k].lson].val|t[t[k].rson].val;
		}
		else t[k].val=t[t[k].lson].val&t[t[k].rson].val;
	}
	else if(t[k].op=='|'){
		build(t[k].lson,opt^t[k].rev);
		build(t[k].rson,opt^t[k].rev);
		if(opt^t[k].rev){
			t[k].op='&';
			t[k].val=t[t[k].lson].val&t[t[k].rson].val;
		}
		else t[k].val=t[t[k].lson].val|t[t[k].rson].val;
	}
}
bool flag[MAXN];
void search(int k,bool opt){
	if(t[k].idx<=n){
		flag[t[k].idx]=opt;
		return;
	}
	if(t[k].op=='&'){
		if(!t[t[k].rson].val)search(t[k].lson,true);
		else search(t[k].lson,opt);
		if(!t[t[k].lson].val)search(t[k].rson,true);
		else search(t[k].rson,opt);
	}
	else if(t[k].op=='|'){
		if(t[t[k].rson].val)search(t[k].lson,true);
		else search(t[k].lson,opt);
		if(t[t[k].lson].val)search(t[k].rson,true);
		else search(t[k].rson,opt);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	getline(cin,s);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	stringstream ss(s);
	while(ss>>str){
		if(str=="&"){
			indexs++,times++;
			t[indexs].rson=stk.top();
			stk.pop();
			t[indexs].lson=stk.top();
			stk.pop();
			t[indexs].idx=times+n;
			t[indexs].op='&';
			stk.push(indexs);
		}
		else if(str=="|"){
			indexs++,times++;
			t[indexs].rson=stk.top();
			stk.pop();
			t[indexs].lson=stk.top();
			stk.pop();
			t[indexs].idx=times+n;
			t[indexs].op='|';
			stk.push(indexs);
		}
		else if(str=="!")t[stk.top()].rev=true;
		else{
			indexs++;
			int temp=0;
			for(char to:str){
				if(to=='x')continue;
				temp=temp*10+(to-'0');
			}
			t[indexs].idx=temp;
			t[indexs].val=a[temp];
			stk.push(indexs);
		}
	}
	build(indexs,false);
	search(indexs,false);
	cin>>q;
	while(q--){
		int query;
		cin>>query;
		if(flag[query])cout<<t[indexs].val<<'\n';
		else cout<<!t[indexs].val<<'\n';
	}
	return 0;
}

$d$了五六个小时，死活过不了，也不知道思路有没有问题