这是一份符合 CSP-J/S 竞赛标准的 C++ AC 代码。

解题核心回顾

1. 建树：利用栈将后缀表达式解析为表达式树。
2. 预处理值（DFS 1 / 循环）：从底向上计算出所有节点在初始状态下的值。
3. 预处理影响权（DFS 2 / 循环）：从根节点向下，标记哪些节点的值改变会“传递”到根节点。利用逻辑运算的短路特性（如 0 & x，x 变了结果也不变）来阻断标记。
4. 查询：如果被修改的变量节点有“影响权”，则答案翻转；否则答案不变。

为了防止递归深度过深导致栈溢出，本代码采用了**迭代（循环）**的方式来替代 DFS，这在处理 $10^6$ 级别的链状数据时更安全。

标准 C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <cctype> // for isdigit

using namespace std;

// 数据规模：|s| <= 10^6，开 1000005 足够
const int MAXN = 1000005;

// 树的结构数组
// L[i], R[i]: 节点 i 的左、右孩子编号
// op[i]: 节点 i 的类型 (0:变量, 1:&, 2:|, 3:!)
// val[i]: 节点 i 当前计算出的逻辑值 (0 或 1)
// affect[i]: 标记节点 i 的翻转是否会影响最终结果 (true/false)
int L[MAXN], R[MAXN];
int op[MAXN];
int val[MAXN];
bool affect[MAXN];

// 映射数组：变量下标 -> 树节点编号
// 题目保证变量 x1...xn 恰好出现一次
int var_node[100005]; 
// 存储变量的初始值
int input_val[100005];

// 节点计数器
int cnt = 0;
// 手写栈，比 std::stack 略快且方便
int stk[MAXN], top = 0;

// 辅助函数：解析字符串中的数字
int parse_num(const string& s, int& i) {
    int res = 0;
    while (i < s.length() && isdigit(s[i])) {
        res = res * 10 + (s[i] - '0');
        i++;
    }
    return res;
}

int main() {
    // 1. 优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(0);

    // 读取后缀表达式整行
    string s;
    getline(cin, s);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> input_val[i];
    }

    // 2. 解析后缀表达式并建树
    // 后缀表达式的特性保证了：操作数在前，运算符在后
    int len = s.length();
    for (int i = 0; i < len; i++) {
        if (s[i] == ' ') continue; // 跳过空格

        cnt++; // 新建一个节点，编号为 cnt

        if (s[i] == 'x') {
            // 情况 A: 变量 (叶子节点)
            i++; // 跳过 'x'
            int idx = parse_num(s, i); // 解析下标
            i--; // 回退一格，因为 for 循环会 i++

            op[cnt] = 0; // 类型 0 表示变量
            val[cnt] = input_val[idx]; // 直接赋值
            var_node[idx] = cnt;       // 记录映射关系

            stk[++top] = cnt; // 入栈
        } 
        else if (s[i] == '&') {
            // 情况 B: 与运算
            op[cnt] = 1;
            R[cnt] = stk[top--]; // 栈顶是右操作数
            L[cnt] = stk[top--]; // 次顶是左操作数
            stk[++top] = cnt;    // 结果节点入栈
        } 
        else if (s[i] == '|') {
            // 情况 C: 或运算
            op[cnt] = 2;
            R[cnt] = stk[top--];
            L[cnt] = stk[top--];
            stk[++top] = cnt;
        } 
        else if (s[i] == '!') {
            // 情况 D: 非运算
            op[cnt] = 3;
            L[cnt] = stk[top--]; // 单目运算符，只取一个操作数(作为左孩子)
            stk[++top] = cnt;
        }
    }

    // 3. 计算所有节点的初始值 (Bottom-Up)
    // 技巧：后缀表达式解析生成的节点顺序天然就是拓扑序 (子节点编号 < 父节点编号)
    // 所以直接从 1 循环到 cnt 即可，无需递归 DFS
    for (int i = 1; i <= cnt; i++) {
        if (op[i] == 0) continue; // 叶子节点值已在建树时赋值

        if (op[i] == 1)      val[i] = val[L[i]] & val[R[i]];
        else if (op[i] == 2) val[i] = val[L[i]] | val[R[i]];
        else if (op[i] == 3) val[i] = !val[L[i]];
    }

    // 4. 计算影响标记 (Top-Down)
    // 同样利用拓扑序，倒着循环 (cnt -> 1) 即可替代递归 DFS，防止爆栈
    int root = cnt;
    affect[root] = true; // 根节点肯定影响结果

    for (int i = cnt; i >= 1; i--) {
        // 如果当前节点本身都不影响结果，那它的子节点肯定也不影响，跳过
        if (!affect[i]) continue;
        if (op[i] == 0) continue; // 叶子节点无子节点，跳过

        if (op[i] == 1) { // & 运算
            // 如果 R 是 1，那么 L 的改变会传递上去 -> 标记 L
            if (val[R[i]] == 1) affect[L[i]] = true;
            // 如果 L 是 1，那么 R 的改变会传递上去 -> 标记 R
            if (val[L[i]] == 1) affect[R[i]] = true;
        } 
        else if (op[i] == 2) { // | 运算
            // 如果 R 是 0，L 才能决定结果 -> 标记 L
            if (val[R[i]] == 0) affect[L[i]] = true;
            // 如果 L 是 0，R 才能决定结果 -> 标记 R
            if (val[L[i]] == 0) affect[R[i]] = true;
        } 
        else if (op[i] == 3) { // ! 运算
            // 非运算一定会传递改变
            affect[L[i]] = true;
        }
    }

    // 5. 处理询问
    int q;
    cin >> q;
    int root_val = val[root]; // 原表达式的结果

    while (q--) {
        int x_idx;
        cin >> x_idx;
        int u = var_node[x_idx]; // 找到对应的叶子节点

        // 如果该变量有影响权，结果取反；否则结果不变
        if (affect[u]) {
            cout << !root_val << "\n";
        } else {
            cout << root_val << "\n";
        }
    }

    return 0;
}

你好！我是你的 OI 教练。

这道题（CSP-J 2020 T4 表达式）是当年的一道压轴题。虽然它是入门组题目，但涉及到了表达式树和DFS 标记的思想，对思维要求较高。

如果对每个询问都重新计算一遍表达式的值，复杂度是 $O(Q \cdot |S|)$，对于 $10^5$ 级别的数据肯定会超时。我们需要一种预处理的方法，使得每次询问都能 $O(1)$ 回答。

以下是解题思路的详细拆解：

1. 核心思路：短路效应与“关键变量”

我们要解决的问题是：修改某个叶子节点（变量）的值，会不会改变根节点（表达式最终结果）的值？

我们可以反过来思考：从根节点出发，寻找哪些节点的改变会影响结果。 这利用了逻辑运算中的**“短路效应”**：

• 对于与运算 (A & B)：
  • 如果 B 的值是 0，那么无论 A 是 0 还是 1，结果都是 0。此时 A 的改变无法影响结果（A 被短路了）。
  • 只有当 B 的值是 1 时，A 的改变才会传递上去。
• 对于或运算 (A | B)：
  • 如果 B 的值是 1，那么无论 A 是什么，结果都是 1。此时 A 的改变无法影响结果。
  • 只有当 B 的值是 0 时，A 的改变才会传递上去。
• 对于非运算 (!A)：
  • A 的改变一定会传递上去。

基于这个性质，我们可以通过两次 DFS（深度优先搜索）来解决问题。

2. 解题步骤拆解

第一步：构建表达式树（建树）

题目给出的是后缀表达式，这是最适合计算机处理的形式，通常配合栈 (Stack) 来操作。但在本题中，我们需要多次遍历结构，所以不仅要计算值，还要把树建出来。

• 栈中存什么：存树的节点编号。
• 遇到变量（x）：新建一个节点，设为叶子节点，压入栈。
• 遇到 !：从栈弹出一个节点作为左孩子，新建一个 ! 节点，压入栈。
• 遇到 & 或 |：从栈弹出两个节点（先弹的是右孩子，后弹的是左孩子），新建一个运算节点，压入栈。

最后栈里剩下的那个节点就是根节点。

第二步：第一次 DFS —— 计算原值

从根节点开始，自底向上计算每个节点在初始状态下的值（0 或 1）。记为 val[u]。 这一步顺便求出了原表达式的最终答案 ans。

第三步：第二次 DFS —— 标记“影响权” （核心）

这是最关键的一步。我们定义一个布尔数组 affect[u]，表示节点 u 的值发生翻转，是否会导致最终结果翻转。

• 初始化：根节点肯定影响自己，所以 affect[root] = true。
• 向下传递（假设当前节点 u，左右孩子为 l, r）：
  • 如果 affect[u] 是 false（当前节点已经没影响了），那么它的孩子肯定也没影响，affect[l] = affect[r] = false。
  • 如果 affect[u] 是 true：
    • 若 u 是 !：l 的改变肯定影响 u，所以 affect[l] = true。
    • 若 u 是 &：
      • 若 val[r] == 1，则 l 能影响 u，标记 affect[l] = true。
      • 若 val[r] == 0，则 l 被短路，标记 affect[l] = false。
      • 同理判断 r（看 val[l]）。
    • 若 u 是 |：
      • 若 val[r] == 0，则 l 能影响 u，标记 affect[l] = true。
      • 若 val[r] == 1，则 l 被短路，标记 affect[l] = false。
      • 同理判断 r（看 val[l]）。

第四步：处理询问

对于询问 q（翻转变量 $x_q$）：

• 找到变量 $x_q$ 对应的叶子节点编号。
• 检查该节点的 affect 标记。
• 如果为 true，说明它的改变能传递到根，输出 !ans（原答案取反）。
• 如果为 false，说明它被半路短路了，输出 ans（原答案）。

3. 实现细节提示

1. 字符串解析：

   • 输入包含空格，可以使用 getline(cin, s) 读取整行。
   • 遍历字符串时，如果是数字，可能有多位（如 x10），需要解析完整的数字。
   • 为了方便查找，可以开一个数组 pos[i] 记录变量 $x_i$ 对应的树节点编号。

2. 数据结构：

   • 使用结构体数组来模拟树：

   struct Node {
       int l, r; // 左右孩子编号，没有则为0
       int val;  // 当前节点计算出的值
       int op;   // 运算符类型：0代表数值，1代表&，2代表|，3代表!
   } tree[1000005];
   

3. 时间复杂度：

   • 建树：$O(|S|)$
   • 第一次 DFS：$O(N)$ （节点数）
   • 第二次 DFS：$O(N)$
   • 查询：$O(1)$
   • 总复杂度完全满足要求。

4. 代码逻辑框架

// 1. 读取字符串 (getline)
// 2. 遍历字符串，利用栈建树
//    - 解析出变量下标 idx，tree[cnt].val = input_val[idx]，pos[idx] = cnt
//    - 遇到运算符，弹出栈顶元素连边
// 3. DFS1(root): 计算每个节点的 val
// 4. DFS2(root): 计算每个节点的 affect 标记
//    - affect[root] = true
//    - 根据 val 和 op 规则向下递归
// 5. 循环处理询问 q:
//    - 找到节点 u = pos[q]
//    - if (affect[u]) print(!original_ans) else print(original_ans)

按照这个思路，这道题就变成了一道标准的树形 DP/搜索题目。加油！