A0783 [2020J3]表达式

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int type;          // 0 变量，1 取反 !，2 与 &，3 或 |
    int l = -1, r = -1; // 孩子
    int parent = -1;   // 父节点（建树时填）
    int val = 0;       // 该节点在初始赋值下的值
    int var = 0;       // 变量下标（type == 0 时有效）
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> ws;
    getline(cin, s);

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

    vector<Node> nodes;
    nodes.reserve(s.size() / 2 + 2);
    vector<int> st;
    st.reserve(s.size() / 2 + 2);
    vector<int> varNode(n + 1, -1);

    // 1) 扫描后缀表达式：一边求值，一边建表达式树
    size_t p = 0;
    while (p < s.size()) {
        char c = s[p];
        if (c == 'x') {
            p++;
            int k = 0;
            while (p < s.size() && isdigit(static_cast<unsigned char>(s[p]))) {
                k = k * 10 + (s[p] - '0');
                p++;
            }
            Node nd;
            nd.type = 0;
            nd.val = init[k];
            nd.var = k;
            varNode[k] = (int)nodes.size();
            nodes.push_back(nd);
            st.push_back((int)nodes.size() - 1);
        } else if (c == '!') {
            p++;
            int a = st.back();
            st.pop_back();
            Node nd;
            nd.type = 1;
            nd.l = a;
            nd.val = !nodes[a].val;
            nodes[a].parent = (int)nodes.size();
            nodes.push_back(nd);
            st.push_back((int)nodes.size() - 1);
        } else if (c == '&' || c == '|') {
            p++;
            int b = st.back();
            st.pop_back();
            int a = st.back();
            st.pop_back();
            Node nd;
            nd.type = (c == '&') ? 2 : 3;
            nd.l = a;
            nd.r = b;
            nd.val = (c == '&') ? (nodes[a].val & nodes[b].val) : (nodes[a].val | nodes[b].val);
            nodes[a].parent = (int)nodes.size();
            nodes[b].parent = (int)nodes.size();
            nodes.push_back(nd);
            st.push_back((int)nodes.size() - 1);
        } else {
            p++; // 跳过空格等分隔符
        }
    }

    int root = st.back();
    int base = nodes[root].val;   // 初始赋值下表达式的值

    // 2) 敏感度：把某个节点的值取反，会不会改变整个表达式的值
    //
    // 关键：每个变量在表达式中只出现一次，所以取反某个变量不会改变它的“兄弟”的值。
    // 于是「取反孩子会不会改变父亲的值」只取决于兄弟的值：
    //   & ：兄弟为 1 时才会变（兄弟为 0 时两边都是 0）
    //   | ：兄弟为 0 时才会变（兄弟为 1 时两边都是 1）
    //   ! ：一定会变
    // 父节点编号一定大于孩子编号，所以按编号从大到小处理就是自顶向下。
    vector<char> sens(nodes.size(), 0);
    sens[root] = 1;
    for (int i = (int)nodes.size() - 1; i >= 0; i--) {
        if (i == root) continue;
        int pa = nodes[i].parent;
        if (!sens[pa]) continue;
        if (nodes[pa].type == 1) {
            sens[i] = 1;
        } else {
            int sib = (nodes[pa].l == i) ? nodes[pa].r : nodes[pa].l;
            sens[i] = (nodes[pa].type == 2) ? (char)nodes[sib].val : (char)(!nodes[sib].val);
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int k;
        cin >> k;
        int ans = base;
        if (sens[varNode[k]]) ans = !ans;
        cout << ans << '\n';
    }
    return 0;
}