[CSP-J2020] 表达式复赛在线求调

#include<iostream>
#include<iomanip>
#include<string>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<map>
#include<deque>
#include<stack>
#include<set>
#include<vector>
#define ll long long
#define ull unsigned long long
using namespace std;
const int N = 1e6 + 5;
struct edge{
	ll value, left_root, right_root, identifier;
	char symbol;
};
edge tree[N];
char x[N];
bool f[N];
ll n, q, ops[N];
stack<ll> s;
ll tree_num;
void build(ll length){
	for(int i = 0; i < length; i ++){
		if(x[i] == 'x'){
			ll num = 0;
			while(isdigit(x[++ i])){
				num = (num << 1) + (num << 3) + x[i] ^ 48;
			}
			tree_num ++;
			tree[tree_num].value = ops[num];
			tree[tree_num].identifier = num;
			tree[tree_num].symbol = '0';
			s.push(tree_num);
		} else if(x[i] != ' '){
			ll tree_left = s.top();
			s.pop();
			tree_num ++;
			if(x[i] == '!'){
				tree[tree_num].value = tree[tree_left].value ^ 1;
				tree[tree_num].left_root = tree_left;
			} else {
				ll tree_right = s.top();
				s.pop();
				tree[tree_num].left_root = tree_left;
				tree[tree_num].right_root = tree_right;
				if(x[i] == '&'){
					tree[tree_num].value = tree[tree_left].value & tree[tree_right].value;
				} else {
					tree[tree_num].value = tree[tree_left].value | tree[tree_right].value;
				}
			}
			s.push(tree_num);
			tree[tree_num].symbol = x[i];
			
		}
	}
	return;
}
void dfs(ll rt){
	if(tree[rt].symbol == '0'){
		f[tree[rt].identifier] = true;
		return;
	}
	if(tree[rt].symbol == '!'){
		dfs(tree[rt].left_root);
	} else if(tree[rt].symbol == '&'){
		if(tree[tree[rt].left_root].value + tree[tree[rt].right_root].value == 1){
			if(tree[tree[rt].left_root].value == 0){
				dfs(tree[rt].left_root);
			} else {
				dfs(tree[rt].right_root);
			}
		} else if(tree[tree[rt].left_root].value + tree[tree[rt].right_root].value == 2){
			dfs(tree[rt].left_root);
			dfs(tree[rt].right_root);
		}
	} else if(tree[rt].symbol == '|'){
		if(tree[tree[rt].left_root].value + tree[tree[rt].right_root].value == 1){
			if(tree[tree[rt].left_root].value == 1){
				dfs(tree[rt].left_root);
			} else {
				dfs(tree[rt].right_root);
			}
		} else if(tree[tree[rt].left_root].value + tree[tree[rt].right_root].value == 0){
			dfs(tree[rt].left_root);
			dfs(tree[rt].right_root);
		}
	}
}
int main(){
	//freopen("fraction.in","r",stdin);
	//freopen("fraction.out","w",stdout);
	cin.getline(x, 1000005);
	ll length = strlen(x);
	cin >> n;
	for(int i = 1; i <= n; i ++){
		cin >> ops[i];
	}
	build(length);
	dfs(tree_num);
	ll ans = tree[s.top()].value;
	cin >> q;
	while(q --){
		ll question;
		cin >> question;
		cout << (f[question] ^ ans) << endl;
	}
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}