题目网址：
https://www.luogu.com.cn/problem/P7073
题目描述

小 C 热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。在这种逻辑表达式中，所有操作数都是变量，且它们的取值只能为 0 或 1，运算从左往右进行。如果表达式中有括号，则先计算括号内的子表达式的值。特别的，这种表达式有且仅有以下几种运算：

1. 与运算：a & b。当且仅当 a 和 b 的值都为 1 时，该表达式的值为 1。其余情况该表达式的值为 0。
2. 或运算：a | b。当且仅当 a 和 b 的值都为 0 时，该表达式的值为 0。其余情况该表达式的值为 1。
3. 取反运算：!a。当且仅当 a 的值为 0 时，该表达式的值为 1。其余情况该表达式的值为 0。

小 C 想知道，给定一个逻辑表达式和其中每一个操作数的初始取值后，再取反某一个操作数的值时，原表达式的值为多少。

为了化简对表达式的处理，我们有如下约定：

表达式将采用后缀表达式的方式输入。

后缀表达式的定义如下：

1. 如果 E 是一个操作数，则 E 的后缀表达式是它本身。
2. 如果 E 是 E1 op E2 形式的表达式，其中 op 是任何二元操作符，且优先级不高于 E1 、E2 中括号外的操作符，则 E 的后缀式为 E1′E2′op，其中 E1′ 、E2′ 分别为 E1、E2 的后缀式。
3. 如果 E 是 E1 形式的表达式，则 E1 的后缀式就是 E 的后缀式。

同时为了方便，输入中：

1. 与运算符（&）、或运算符（|）、取反运算符（！）的左右均有一个空格，但表达式末尾没有空格。
2. 操作数由小写字母 x 与一个正整数拼接而成，正整数表示这个变量的下标。例如：x10，表示下标为 10 的变量 x10。数据保证每个变量在表达式中出现恰好一次。

输入格式

第一行包含一个字符串 s，表示上文描述的表达式。
第二行包含一个正整数 n，表示表达式中变量的数量。表达式中变量的下标为 1,2,···,n。
第三行包含 n 个整数，第 i 个整数表示变量 xi 的初值。
第四行包含一个正整数 q，表示询问的个数。
接下来 q 行，每行一个正整数，表示需要取反的变量的下标。注意，每一个询问的修改都是临时的，即之前询问中的修改不会对后续的询问造成影响。
数据保证输入的表达式合法。变量的初值为 0 或 1。

输出格式

输出一共有 q 行，每行一个 0 或 1，表示该询问下表达式的值。

输入输出样例

输入 #1

x1 x2 & x3 |
3
1 0 1
3
1
2
3

输出 #1

1
1
0

输入 #2

x1 ! x2 x4 | x3 x5 ! & & ! &
5
0 1 0 1 1
3
1
3
5

输出 #2

0
1
1

说明/提示

样例 1 解释

该后缀表达式的中缀表达式形式为 (x1andx2)orx3。

• 对于第一次询问，将 x1 的值取反。此时，三个操作数对应的赋值依次为 0，0，1。原表达式的值为 (0&0)∣1=1。
• 对于第二次询问，将 x2 的值取反。此时，三个操作数对应的赋值依次为 1，1，1。原表达式的值为 (1&1)∣1=1。
• 对于第三次询问，将 x3 的值取反。此时，三个操作数对应的赋值依次为 1，0，0。原表达式的值为 (1&0)∣0=0。

样例 2 解释

该表达式的中缀表达式形式为 (notx1)and(not((x2orx4)and(x3and(notx5))))。

数据规模与约定

• 对于 20% 的数据，表达式中有且仅有与运算（&）或者或运算（|）。
• 对于另外 30% 的数据，∣s∣≤1000，q≤1000，n≤1000。
• 对于另外 20% 的数据，变量的初值全为 0 或全为 1。
• 对于 100% 的数据，1≤∣s∣≤1×106，1≤q≤1×105，2≤n≤1×105。

其中，∣s∣ 表示字符串 s 的长度。

题解：

算法思路：表达式树与短路标记

核心思想

表达式树构建：

• 用栈处理后缀表达式
• 操作数：入栈
• 运算符：弹出操作数创建新节点
• 取反：标记栈顶节点取反

短路分析：

• 与运算：若左子为0，则右子被短路（不影响结果）
• 或运算：若左子为1，则右子被短路

两次DFS：

• 第一次DFS：计算表达式的值，标记短路节点
• 第二次DFS：自顶向下传递短路标记

关键性质

• 被短路标记的变量取反不影响表达式结果
• 未被标记的变量取反会导致结果取反

代码详细注释

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

const int MAXN = 1e6 + 5;
string s;               // 后缀表达式
int n, q;               // 变量数 n，查询数 q
int a[MAXN];            // a[i]：变量 i 的值或节点的运算符类型
int son[MAXN][2];       // son[u][0/1]：节点 u 的左右子节点
int flag[MAXN];         // flag[u]：节点 u 的取反标记
int mark[MAXN];         // mark[u]：短路标记（1 表示被短路）
int id;                 // 节点编号计数器

// 第一次 DFS：计算表达式值并标记短路节点
int dfs(int u, int g) {
    // 应用取反标记
    a[u] ^= g;
    
    // 叶子节点（变量）直接返回值
    if (u <= n) {
        return a[u];
    }
    
    // 递归计算左右子节点（传递取反标记）
    int left_g = g ^ flag[son[u][0]];
    int right_g = g ^ flag[son[u][1]];
    int x = dfs(son[u][0], left_g);
    int y = dfs(son[u][1], right_g);
    
    // 根据运算符类型处理
    if (a[u] == -1) { // 与运算 (&)
        // 短路标记：若左子为 0 则右子被短路
        if (x == 0) mark[son[u][1]] = 1;
        // 短路标记：若右子为 0 则左子被短路
        if (y == 0) mark[son[u][0]] = 1;
        return x & y;
    } else { // 或运算 (|)
        // 短路标记：若左子为 1 则右子被短路
        if (x == 1) mark[son[u][1]] = 1;
        // 短路标记：若右子为 1 则左子被短路
        if (y == 1) mark[son[u][0]] = 1;
        return x | y;
    }
}

// 第二次 DFS：传递短路标记
void dfs2(int u) {
    // 叶子节点终止
    if (u <= n) return;
    
    // 将短路标记传递给子节点
    mark[son[u][0]] |= mark[u];
    mark[son[u][1]] |= mark[u];
    
    // 递归子节点
    dfs2(son[u][0]);
    dfs2(son[u][1]);
}

int main() {
    // 读入后缀表达式
    getline(cin, s);
    // 读入变量数
    cin >> n;
    // 节点编号初始化（变量编号 1~n，新节点从 n+1 开始）
    id = n;
    
    // 读入变量初始值
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    stack<int> st;
    // 解析后缀表达式
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == ' ') continue;  // 跳过空格
        
        // 处理操作数（如 "x123"）
        if (s[i] == 'x') {
            i++;  // 跳过 'x'
            int num = 0;
            // 提取数字（可能多位数）
            while (i < s.size() && isdigit(s[i])) {
                num = num * 10 + (s[i] - '0');
                i++;
            }
            i--;  // 回退最后一位
            st.push(num);  // 操作数入栈
        }
        // 处理取反运算符
        else if (s[i] == '!') {
            // 标记栈顶节点取反
            flag[st.top()] ^= 1;
        }
        // 处理与运算符
        else if (s[i] == '&') {
            // 弹出右子节点和左子节点
            int right = st.top(); st.pop();
            int left = st.top(); st.pop();
            
            // 创建新节点
            id++;
            a[id] = -1;  // -1 表示与运算
            son[id][0] = left;
            son[id][1] = right;
            st.push(id);  // 新节点入栈
        }
        // 处理或运算符
        else if (s[i] == '|') {
            // 弹出右子节点和左子节点
            int right = st.top(); st.pop();
            int left = st.top(); st.pop();
            
            // 创建新节点
            id++;
            a[id] = -2;  // -2 表示或运算
            son[id][0] = left;
            son[id][1] = right;
            st.push(id);  // 新节点入栈
        }
    }
    
    // 根节点为栈顶元素
    int root = st.top();
    // 第一次 DFS：计算初始表达式值并标记短路节点
    int ans = dfs(root, flag[root]);
    // 第二次 DFS：传递短路标记
    dfs2(root);
    
    // 处理查询
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        // 输出结果：若被短路则结果不变，否则取反
        cout << (mark[x] ? ans : !ans) << endl;
    }
    
    return 0;
}

关键步骤图解

1. 表达式树构建（示例：x1 ! x2 &）

后缀表达式：x1 ! x2 &
  构建过程：
    1. x1 入栈 → [1]
    2. ! 标记栈顶取反 → 节点1标记
    3. x2 入栈 → [1,2]
    4. & 创建节点3 → 左右子为1和2
  最终树：
        &
       / \
      !   x2
      |
      x1

2. 短路标记传播

示例：x1=0, x2=1
  第一次DFS：
    节点1：0（取反后）
    节点3：0 & 1 = 0
    短路标记：节点1为0 → 节点2被短路 (mark[2]=1)
  第二次DFS：
    节点3标记传递给子节点 → mark[1]和mark[2]都为0
    但节点2已有短路标记 → mark[2]=1

3. 查询处理

复杂度分析

• 时间复杂度：O(∣s∣+n)
• 表达式解析 O(∣s∣)，两次DFS O(n)
• 空间复杂度：O(MAXN)
• 存储树结构和标记数组