[CSP-J 2020] 表达式55pts求调必关

#include<bits/stdc++.h>

using namespace std;
string s;
const int N=1e6+10;
const double eps=1e-8;
unordered_map<char,int> pr;
char sign[N];//表达式中i结点是什么符号 
int val[N];//用一个val数组记录数值 
stack<int> stk;//标号栈 
stack<char> op;//符号栈 
bool error;
//左儿子 右儿子 总结点数
int ls[N],rs[N],tot;
bool flag[N];
int res[N];
bool can[N];
int x[N];
void eval(char c){
	int idx1=stk.top();
	stk.pop();
	int idx2=stk.top();
	stk.pop();
	tot++;
	ls[tot]=idx2;
	rs[tot]=idx1;
	sign[tot]=c;
	//合并两个数值 
	stk.push(tot);
} 
void build(){
	int len=s.size();
	for(int i=0;i<len;i++){
		char c=s[i];
		if(c=='x'){
			int j=i+1;
			int num=0;
			while(j<len && isdigit(s[j])){
				num=num*10+s[j]-'0';
				j++;
			}
			i=j-1;
			//新建一个节点树
			tot++;
			val[tot]=num;
			//结点标号入栈
			stk.push(tot); 
		}else if(c=='!'){
			int top=stk.top();
			flag[top]^=1;
		}else if(c=='&' || c=='|'){
			eval(c);
		}
	}
}
double calc(int a,int b,char op,bool rev){
	if(rev){
		if(op=='&'){
			return !(a & b);
		}else{
			return !(a | b);
		}
	}else{
		if(op=='|'){
			return (a | b);
		}else{
			return (a & b);
		}
	}
}
double dfs(int now){
	if(ls[now]==0){
		if(flag[now]){
			int idx=val[now];
			res[now]=!x[idx];
			return res[now];
		}else{
			int idx=val[now];
			res[now]=x[idx];
			return res[now];
		}
	}
	int left=dfs(ls[now]);
	int right=dfs(rs[now]);
	res[now]=calc(left,right,sign[now],flag[now]);
	return res[now];
}
void check(int now){
	//就是一个叶子，能肯定影响根
	if(ls[now]==0){
		// x1 x2 x3 的下标
		int idx=val[now];
		can[idx]=1; 
	} 
	if(sign[now]=='&'){
		int idx1=rs[now];
		if(res[idx1]==1){
			check(ls[now]);
		}
		int idx2=ls[now];
		if(res[idx2]==1){
			check(ls[now]);
		}
	}else if(sign[now]=='|'){
		int idx1=ls[now];
		int idx2=rs[now];
		if(res[idx1]==1 && res[idx2]==1){
			return ;
		}else if(res[idx1]==1){
			check(idx1);
		}else if(res[idx2]==1){
			check(idx2);
		}else{
			check(idx1);
			check(idx2);
		}
	}
	
}

int main(){
	getline(cin,s);
	build();
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i];
	}
	int ans=dfs(tot);
	check(tot);
	int q;
	cin>>q;
	
	while(q--){
		int id;
		cin>>id;
		if(can[id]) cout<<!ans<<endl;
		else cout<<ans<<endl;
	}



	return 0;
}