表达式

GitHub跳转原题关系图返回列表

后缀表达式建树后正序求值、逆序传播翻转信号：非运算恒穿过，与运算看兄弟是否为 1，或运算看兄弟是否为 0，每次询问 O(1) 作答，总复杂度 O(|s|+q)。

OJ: roj

题目 ID: 3666

难度:普及+/提高-

标签:栈树递推python

创建: 2026-10-02 14:23

更新: 2026-10-10 11:30

形式化题目

给定一个后缀（逆波兰）表达式，操作数是变量 $x_1,\dots,x_n$ ，取值为 $0/1$ ，每个变量在表达式中恰好出现一次且各有一个初值。运算只有三种、从左往右结合：

a b &：与，仅当两者都为 $1$ 时结果为 $1$ ；
a b |：或，仅当两者都为 $0$ 时结果为 $0$ ；
a !：取反， $0$ 变 $1$ 、 $1$ 变 $0$ 。

有 $q$ 次询问，每次给出一个下标 $i$ ，把 $x_i$ 的取值取反（临时修改，不影响后续询问）后，求整个表达式的值；输出每次询问的结果。

样例 1 的后缀式 x1 x2 & x3 | 对应中缀 $(x_1 \mathbin{\&} x_2) \mid x_3$ ，初值 $(1,0,1)$ ：询问 1 翻 $x_1$ 得 $(0\&0)|1=1$ ；询问 2 翻 $x_2$ 得 $(1\&1)|1=1$ ；询问 3 翻 $x_3$ 得 $(1\&0)|0=0$ ，即输出 1 1 0。样例 2 的 x1 ! x2 x4 | x3 x5 ! & & ! & 对应 $(!x_1) \mathbin{\&} \bigl(!\bigl((x_2 \mid x_4) \mathbin{\&} (x_3 \mathbin{\&} (!x_5))\bigr)\bigr)$ ，输出 0 1 1。

正解

思路

朴素做法与瓶颈。 每次询问把变量取反后重新求值：单次 $O(|s|)$ ， $q$ 次共 $O(q|s|)$ ，最坏 $10^{5}\times10^{6}=10^{11}$ ，跑不动。退一步先建好树、每次只沿"叶子到根"的路径增量更新结点值，单次 $O(\text{深度})$ ；但链状表达式（一串 & 左结合）深度 $O(n)$ ，总 $O(nq)=10^{10}$ ，同样超时。瓶颈在于回答一次询问的代价仍与树的规模或深度挂钩。

关键观察：变量只出现一次，翻转的影响只有一条路径，且可以静态判定。 翻转 $x_i$ 时，从它的叶子到根的唯一路径之外的子树不含 $x_i$ 、值不变；路径上每道门的兄弟子树也不含 $x_i$ ，兄弟值保持原值。于是"翻转能不能穿过这道门"不需要真的翻转重算，用原表达式已求出的值就能判断：

!：孩子翻则自己翻，恒穿过；
&：输出锁死为 $0$ 的情形是兄弟为 $0$ ，故兄弟为 $1$ 才穿过；
|：输出锁死为 $1$ 的情形是兄弟为 $1$ ，故兄弟为 $0$ 才穿过。

定义翻转信号 $d(v)$ ：把结点 $v$ 的值取反，根的值是否也取反。 按穿过条件自顶向下递推：

d(\text{root}) = 1, \qquad d(\text{child}) = d(\text{parent}) \wedge \bigl[\text{child 的翻转能穿过 parent}\bigr]

递推合法的原因：翻转 child 若过不了这道门，parent 的值不变、根自然不变；若过了，parent 的值取反而其余输入与原情形完全相同，根的结果就等于"原情形下单独翻转 parent"，即 $d(\text{parent})$ 。逐层归纳即得 $d(v)$ 恰为"翻转 $v$ 是否让根取反"，且判定只用兄弟原值——变量唯一出现保证它不受污染。

预处理三步 + 询问查表：

建树：后缀表达式用栈一遍扫描建出表达式树；按 token 顺序编号，孩子一定先于父结点产生；
正序求值：孩子编号小于父编号，正序扫一遍就是拓扑序，得到每个结点的原值（穿过条件的依据）；
逆序下传信号：根编号最大、父大于子，逆序扫一遍（反拓扑序）把 $d$ 按递推式下传到所有叶子。

此后每次询问 $O(1)$ 作答：答案 $= \text{根的值} \oplus d(\text{被翻转变量的叶子})$ 。

下图在样例 1 的表达式树上标出每个结点的原值与信号 $d$ ：

flowchart TD
    R["|（根）<br/>值 1，信号 1"] --> A["&<br/>值 0，信号 0"]
    R --> X3["x3<br/>值 1，信号 1"]
    A --> X1["x1<br/>值 1，信号 0"]
    A --> X2["x2<br/>值 0，信号 0"]

根是或门：判断左孩子 & 的信号要看兄弟 $x_3=1$ ，"兄弟为 $0$ "不成立，信号在根就被吸收，& 子树信号全为 $0$ ；判断右孩子 $x_3$ 要看兄弟 & 的值 $0$ ，条件成立，信号传到 $x_3$ 。对应到三个询问：

询问	翻转的变量	该叶子的信号 $d$	答案 $= 1 \oplus d$
1	$x_1$	0	1
2	$x_2$	0	1
3	$x_3$	1	0

翻 $x_1$ 、 $x_2$ 答案不变，翻 $x_3$ 答案取反，与样例输出 1 1 0 完全一致。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int AND=0, OR=1, NOT=2;
struct Child{int l,r;};
int calc(int op,int l,int r){ if(op==AND) return l&r; if(op==OR) return l|r; return l^1; }
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); vector<string> tokens; string tok; while(cin>>tok) tokens.push_back(tok); if(tokens.empty()) return 0; int pos=0; vector<string> expr; while(pos<(int)tokens.size() && !(tokens[pos][0]>='0'&&tokens[pos][0]<='9')) expr.push_back(tokens[pos++]); int n=atoi(tokens[pos++].c_str()); vector<int> val(n); for(int i=0;i<n;i++) val[i]=atoi(tokens[pos++].c_str()); int q=atoi(tokens[pos++].c_str()); vector<int> op_of, leaf_val, var_leaf(n,-1), stack; vector<Child> child; for(int ti=0;ti<(int)expr.size();ti++){string s=expr[ti]; int v=op_of.size(); if(s=="!"){int c=stack.back(); stack.pop_back(); stack.push_back(v); op_of.push_back(NOT); child.push_back({c,-1}); leaf_val.push_back(-1);} else if(s=="&"||s=="|"){int cr=stack.back(); stack.pop_back(); int cl=stack.back(); stack.pop_back(); stack.push_back(v); op_of.push_back(s=="&"?AND:OR); child.push_back({cl,cr}); leaf_val.push_back(-1);} else {int id=atoi(s.c_str()+1)-1; stack.push_back(v); op_of.push_back(-1); child.push_back({-1,-1}); leaf_val.push_back(val[id]); var_leaf[id]=v;}} int root=stack[0]; vector<int> node_val(op_of.size()); for(int v=0;v<(int)op_of.size();v++){int op=op_of[v]; if(op<0) node_val[v]=leaf_val[v]; else {int cl=child[v].l, cr=child[v].r; node_val[v]=calc(op,node_val[cl],cr>=0?node_val[cr]:0);}} vector<int> sens(op_of.size()); sens[root]=1; for(int v=(int)op_of.size()-1;v>=0;v--){int op=op_of[v]; if(op<0) continue; int cl=child[v].l, cr=child[v].r; if(op==NOT){sens[cl]=sens[v]; continue;} int pass_l=op==AND?node_val[cr]:1-node_val[cr]; int pass_r=op==AND?node_val[cl]:1-node_val[cl]; sens[cl]=sens[v]&pass_l; sens[cr]=sens[v]&pass_r;} for(int i=0;i<q;i++){int id=atoi(tokens[pos++].c_str()); cout<<(node_val[root]^sens[var_leaf[id-1]])<<'\n';} return 0;}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 14:31
# update_at: 2026-10-02 14:54

import sys

AND = 0  # 结点运算符编码：0 = &，1 = |，2 = !，-1 = 变量叶子
OR = 1
NOT = 2


def calc(op: int, l: int, r: int) -> int:
    """按运算符合成左右孩子的值；! 只用左值，右位的 -1 是占位。"""
    if op == AND:
        return l & r
    if op == OR:
        return l | r
    return l ^ 1


def build(tokens: list[bytes], val: list[int]) -> tuple[list[int], list[tuple[int, int]], list[int], list[int], int]:
    """后缀表达式逐词建树：变量出叶子，运算符不断把栈顶片段合并成更大片段。

    每个变量在表达式中恰好出现一次，叶子按变量下标登记，与出现顺序无关。
    返回 (op_of, child, leaf_val, var_leaf, root)：op_of[v] 是 v 的运算符（叶子为 -1），
    child[v] 是 (左孩子, 右孩子)（! 没有右孩子，右位记 -1），leaf_val[v] 是叶子初值
    （内部结点记 -1），var_leaf[i] 是变量 xi 的叶子。结点按 token 顺序编号，
    孩子一定先于父结点出现，所以正序是拓扑序、逆序是反拓扑序。
    """
    var_leaf = [-1] * len(val)  # 变量下标 → 叶子结点编号
    op_of: list[int] = []
    child: list[tuple[int, int]] = []
    leaf_val: list[int] = []
    stack: list[int] = []  # 栈里是各"表达式片段"的根结点编号

    for tok in tokens:
        v = len(op_of)  # 新结点编号
        if tok == b'!':
            c = stack.pop()  # 一元运算：唯一的孩子放左位
            stack.append(v)
            op_of.append(NOT)
            child.append((c, -1))
            leaf_val.append(-1)
        elif tok == b'&' or tok == b'|':
            cr = stack.pop()  # 右操作数先进栈，先弹的是右孩子
            cl = stack.pop()
            stack.append(v)
            op_of.append(AND if tok == b'&' else OR)
            child.append((cl, cr))
            leaf_val.append(-1)
        else:  # token 形如 x10：x + 正整数下标
            i = int(tok[1:]) - 1
            stack.append(v)
            op_of.append(-1)
            child.append((-1, -1))
            leaf_val.append(val[i])
            var_leaf[i] = v
    return op_of, child, leaf_val, var_leaf, stack[0]


def fill_values(op_of: list[int], child: list[tuple[int, int]], leaf_val: list[int]) -> list[int]:
    """自底向上求每个结点的值：孩子编号一定小于父结点，正序扫一遍就是拓扑序。"""
    node_val = [0] * len(op_of)
    for v, op in enumerate(op_of):
        if op < 0:  # 变量叶子：值就是输入给的初值
            node_val[v] = leaf_val[v]
        else:
            cl, cr = child[v]
            node_val[v] = calc(op, node_val[cl], node_val[cr] if cr >= 0 else 0)
    return node_val


def fill_sens(root: int, op_of: list[int], child: list[tuple[int, int]], node_val: list[int]) -> list[int]:
    """反向传播"翻转信号"：sens[v] = 1 表示把 v 的值取反能让根的值也取反。

    父结点编号一定大于孩子，逆序扫（根最先）就能保证下传时父结点的信号已就位。
    信号穿过结点的条件只看兄弟的原值——变量各出现一次，翻转不会影响兄弟。
    """
    sens = [0] * len(op_of)
    sens[root] = 1  # 根自己取反，答案当然跟着取反
    for v in range(len(op_of) - 1, -1, -1):
        op = op_of[v]
        if op < 0:
            continue  # 叶子是信号终点，答案查询时直接读它
        cl, cr = child[v]
        if op == NOT:
            sens[cl] = sens[v]  # 取反不吸收信号，原样传给唯一的孩子
            continue
        # 与门要兄弟为 1、或门要兄弟为 0，孩子的翻转才穿得过本结点
        pass_l = node_val[cr] if op == AND else 1 - node_val[cr]
        pass_r = node_val[cl] if op == AND else 1 - node_val[cl]
        sens[cl] = sens[v] & pass_l
        sens[cr] = sens[v] & pass_r
    return sens


def solve() -> None:
    tokens = sys.stdin.buffer.read().split()
    it = iter(tokens)

    # 表达式 token 只有 x 开头的变量与 & | !，读到第一个纯数字（就是 n）为止
    expr_tokens: list[bytes] = []
    for tok in it:
        if tok.isdigit():
            data = iter(map(int, [tok] + list(it)))
            break
        expr_tokens.append(tok)

    n = next(data)
    val = [next(data) for _ in range(n)]  # val[i]：xi 的初值
    q = next(data)

    op_of, child, leaf_val, var_leaf, root = build(expr_tokens, val)
    node_val = fill_values(op_of, child, leaf_val)
    sens = fill_sens(root, op_of, child, node_val)

    # 每个询问只临时翻一个变量：答案 = 根值 XOR 该叶子的翻转信号，O(1) 作答
    out: list[str] = []
    for _ in range(q):
        idx = next(data)
        out.append(str(node_val[root] ^ sens[var_leaf[idx - 1]]))
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

build() 对应第 1 步：op_of/child/leaf_val 是结点三元组，var_leaf 按 token 内的变量下标登记叶子（出现顺序与下标无关），stack[0] 即根；fill_values() 对应第 2 步，正序枚举、叶子取初值、内部结点交给 calc() 合成；fill_sens() 对应第 3 步，sens[root] = 1 起步逆序下传，其中 pass_l/pass_r 就是穿过条件（与门取兄弟原值、或门取兄弟的非），NOT 分支不读右孩子。注意下标约定：正文变量是 1 基的 $x_1,\dots,x_n$ ，代码里 var_leaf[i - 1] 与询问行的 int(...) - 1 都先减 1；! 结点没有右孩子，child 右位存 -1，求值时以 0 占位（calc 对 NOT 只用左值）。

复杂度

时间：建树、求值、信号下传三遍扫描各 $O(|s|)$ ，询问每条 $O(1)$ ，合计 $O(|s| + n + q)$ ，与正解同阶；朴素的 $O(q|s|)$ 与爬树的 $O(nq)$ 都被消除。
空间：token 列表与结点数组 $O(|s| + n)$ 。
实测 20 组真实数据全部输出一致，最慢测例 0.124s、峰值约 84MB（OJ 限制 1000ms / 128MB，本地为 Python 放宽计时口径；Python 若在 OJ 上 TLE/MLE 按仓库约定可接受，算法本身与 C++ 正解同阶）。

总结

变量唯一出现是全题支点：翻转只沿一条路径传播、兄弟子树值不变，"翻转能否穿过这道门"因此可用原值静态判定——非恒穿过、与看兄弟为 $1$ 、或看兄弟为 $0$ 。
把"翻转是否传到根"抽象成信号 $d(v)$ 自顶向下递推，三遍 $O(|s|)$ 扫描换每次询问 $O(1)$ ：建树 → 正序求值 → 逆序下传。
后缀表达式按 token 编号天然给出拓扑序：正序求值、逆序下传，无需递归或父指针，也避开了链状深树的深度瓶颈。
易错点：叶子必须按变量下标登记（出现顺序≠下标顺序）；! 是一元运算，右孩子要占位且两种扫描都不能碰它。

题目描述

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

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

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

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

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

后缀表达式的定义如下：

如果 $E$ 是一个操作数，则 $E$ 的后缀表达式是它本身。
如果 $E$ 是 $E_1~\texttt{op}~E_2$ 形式的表达式，其中 $\texttt{op}$ 是任何二元操作符，且优先级不高于 $E_1$ 、 $E_2$ 中括号外的操作符，则 $E$ 的后缀式为 $E_1' E_2' \texttt{op}$ ，其中 $E_1'$ 、 $E_2'$ 分别为 $E_1$ 、 $E_2$ 的后缀式。
如果 $E$ 是 $E_1$ 形式的表达式，则 $E_1$ 的后缀式就是 $E$ 的后缀式。

同时为了方便，输入中：

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

输入格式

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

输出格式

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

样例

|----|----| |输入 #1 |输出 #1 | | |
|x1 x2 & x3 | |1
|3 |1
|1 0 1 |0
|3 | \ |1 | \ |2 | \ |3 | \ | | \ | | | |输入 #2 |输出 #2 | | |
|x1 ! x2 x4 | x3 x5 ! & & ! & |0
|5 |1
|0 1 0 1 1 |1
|3 |
|1 | \ |3 | \ |5 | \ | | \ | | |

说明/提示

样例 1 解释

该后缀表达式的中缀表达式形式为 $(x_1 \& x_2) | x_3$ 。

对于第一次询问，将 $x_1$ 的值取反。此时，三个操作数对应的赋值依次为 $0$ ， $0$ ， $1$ 。原表达式的值为 $(0\&0)|1=1$ 。
对于第二次询问，将 $x_2$ 的值取反。此时，三个操作数对应的赋值依次为 $1$ ， $1$ ， $1$ 。原表达式的值为 $(1\&1)|1=1$ 。
对于第三次询问，将 $x_3$ 的值取反。此时，三个操作数对应的赋值依次为 $1$ ， $0$ ， $0$ 。原表达式的值为 $(1\&0)|0=0$ 。

样例 2 解释

该表达式的中缀表达式形式为 $(!x_1)\&(!((x_2|x_4)\&(x_3\&(!x_5))))$ 。

数据规模与约定

对于 $20\%$ 的数据，表达式中有且仅有与运算（&）或者或运算（|）。
对于另外 $30\%$ 的数据， $|s| \le 1000$ ， $q \le 1000$ ， $n \le 1000$ 。
对于另外 $20\%$ 的数据，变量的初值全为 $0$ 或全为 $1$ 。
对于 $100\%$ 的数据， $1 \le |s| \le 1 \times 10^6$ ， $1 \le q \le 1 \times 10^5$ ， $2 \le n \le 1 \times 10^5$ 。

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

表达式

目录

形式化题目

正解

思路

代码

复杂度

总结