55011 - [CSP-J2020]表达式（expr）

解题思路

题目说每个变量在表达式中出现恰好一次”，而每个询问只改变一个变量的值，这对原答案来说就产生两个可能：变或不变。其蕴含的意思是：有些变量对整个表达式其决定作用，其改变则原答案也改变；有些变量对整个表达式根本没用，其变不变原答案都不变。也就是说，1&x=x ，0|x=x ，这两个公式里的 x 就起了决定性作用，而0&x=0 ，1|x=1的x就一点用也没有了。 那我们就给树上每个结点建一个是否有用的标记，对&来说，如果一棵子树是 0，那另外一棵子树内所有叶结点都应该打上没有用的标记，对|同理。 先计算出原表示结果res，这样我们在查询的时候，没被标记的就说明它往上到根节点都不存在一种让它变成废物的运算，所以答案是!res，如果有标记则答案依旧为res。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f, N = 1e6 + 5; const LL mod = 1e9 + 7;
char ch[N]; int n, q, cnt;
int a[N], son[N][2], f[N], c[N];
int get(int u, int g) {
    a[u] ^= g;
    if (u <= n) {
        return a[u];
    }
    int x = get(son[u][0], g ^ f[son[u][0]]), y = get(son[u][1], g ^ f[son[u][1]]);
    if (a[u] == 2) {
        if (x == 0) {
			c[son[u][1]] = 1;
		} 
        if (y == 0) {
			c[son[u][0]] = 1;
		}
        return x & y;
    } else {
        if (x == 1) {
			c[son[u][1]] = 1;
		} 
        if (y == 1) {
			c[son[u][0]] = 1;
		}
        return x | y;
    }
}
void get2(int u) {
    if (u <= n) {
		return;
	}
    c[son[u][0]] |= c[u]; c[son[u][1]] |= c[u];
    get2(son[u][0]); get2(son[u][1]);
}
int main() {
    freopen("expr.in", "r", stdin);
    freopen("expr.out", "w", stdout);
    gets(ch); cin >> n; cnt = n;
    for (int i = 1; i <= n; ++i) {
    	cin >> a[i];
    }
    stack<int> b;
    for (int i = 0; ch[i]; i += 2) {
        if (ch[i] == 'x') {
            int sum = 0; ++i; 
            while (ch[i] != ' ') {
                sum = sum * 10 + ch[i++] - '0';
            }
            --i; b.push(sum);
        } else if (ch[i] == '&') {
            int A = b.top(); b.pop();
            int B = b.top(); b.pop();
            b.push(++cnt); a[cnt] = 2; son[cnt][0] = A; son[cnt][1] = B;
        } else if (ch[i] == '|') {
            int A = b.top(); b.pop();
            int B = b.top(); b.pop();
            b.push(++cnt); a[cnt] = 3; son[cnt][0] = A; son[cnt][1] = B;
        } else if (ch[i] == '!') {
            f[b.top()] ^= 1;
        }
    }
    int res = get(cnt, f[cnt]); get2(cnt);
    cin >> q;
    while (q--) {
        int x; cin >> x;
        cout << (c[x] ? res : !res) << '\n';
    }
    return 0;
}