$n=16666$

$\forall\space 1\le i\le n$

• $x_i=1$

所有符号为 &

为什么取反 15921 答案为 1 ?

#include <iostream>
#include <stack>
using namespace std;

const int N = 1e5;
const int LEN = 1e6;

struct Node
{
	char op;
	int id;
	int l, r;
} tree[LEN + 5];

int root;
int tot;

bool x[N + 5];
string expr;

int n, q;
bool val[N + 5];    // 以 i 为根点表达式树的值 
bool change[N + 5]; // 取反 x[i] 是否会影响最终答案 

int getnum(int &i)
{
	int res = 0;
	while (i < expr.size() && '0' <= expr[i] && expr[i] <= '9')
	{
		res = res * 10 + expr[i] - '0';
		++i;
	}

	return res;
}

int build()
{
	stack<int> st;

	int i = 0;
	while (i < expr.size())
	{
		char c = expr[i++];

		if (c == 'x')
		{
			Node &cur = tree[++tot];
			cur.id = getnum(i);
			cur.op = 'x';
			cur.l = cur.r = 0;

			st.push(tot);
		}
		else if (c == ' ')
		{
			continue;
		}
		else
		{
			Node &cur = tree[++tot];
			cur.id = 0;
			cur.op = c;
			cur.l = cur.r = 0;

			cur.l = st.top();
			st.pop();

			if (c != '!')
			{
				cur.r = st.top();
				st.pop();
			}

			st.push(tot);
		}
	}

	return st.top();
}

bool dfs1(int u) // 计算 val[i]
{
	Node cur = tree[u];

	if (cur.op == 'x')
	{
		val[u] = x[cur.id];
		return val[u];
	}

	if (cur.op == '&')
	{
		val[u] = dfs1(cur.l) && dfs1(cur.r);
		return val[u];
	}
	else if (cur.op == '|')
	{
		val[u] = dfs1(cur.l) || dfs1(cur.r);
		return val[u];
	}
	else
	{
		val[u] = !dfs1(cur.l);
		return val[u];
	}
}

void dfs2(int u) // 计算 change[i]
{
	Node cur = tree[u];

	if (cur.op == 'x')
	{
		change[u] = true;
		return;
	}

	if (cur.op == '&')
	{
		int lval = val[cur.l];
		int rval = val[cur.r];
		if (rval) dfs2(cur.l);
		if (lval) dfs2(cur.r);
	}
	else if (cur.op == '|')
	{
		int lval = val[cur.l];
		int rval = val[cur.r];
		if (!rval) dfs2(cur.l);
		if (!lval) dfs2(cur.r);
	}
	else
	{
		dfs2(cur.l);
	}
}

int main()
{
	ios::sync_with_stdio(false);

	getline(cin, expr);

	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> x[i];

	root = build();
	int comval = dfs1(root);
	dfs2(root);

	cin >> q;
	while (q--)
	{
		int p;
		cin >> p;
		cout << (comval ^ change[p]) << endl;
	}

	return 0;
}