[CSP-J 2020] 表达式

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

先按后缀表达式建树并求当前值，再从根向下传播“能否影响根”的标记，这样每个翻转询问都能 O(1) 回答。

OJ: luogu

题目 ID: P7073

难度:普及+/提高-

标签:栈字符串思维

创建: 2026-06-19 21:43

更新: 2026-10-11 21:56

形式化题目

给定一个后缀表达式：操作数是变量 $x_1, x_2, \dots, x_n$ ，每个变量在表达式中恰好出现一次；运算符只有 &（与）、|（或）、!（取反）三种，按后缀式的规则从左往右计算，括号内的子表达式先算。

每个变量有一个初始取值 $0$ 或 $1$ 。共有 $q$ 次询问，每次给出一个下标 $k$ ：把 $x_k$ 的值取反——这是临时修改，不影响后续询问——求此时整个表达式的值，每次输出一个 $0$ 或 $1$ 。

解法路线

题面「数据规模与约定」给出四个真实档位，每一档都指向一种做法：

档位	真实约束	做法	瓶颈
$20\%$	只含 `&`，或只含 `\|`	同种运算满足结合律，整式退化成「全与 / 全或」，数 $1$ 的个数	只对单一种运算成立
另 $30\%$	$\|s\|, q, n \leqslant 1000$	每次询问重新求值	$O(\|s\| \cdot q)$ ，小数据才够
另 $20\%$	初值全为 $0$ 或全为 $1$	化归成「翻转能不能传到根」，两遍 DFS	算法已无瓶颈，剩下 $10^6$ 级的实现问题
$100\%$	$\|s\| \leqslant 10^6$ ， $q \leqslant 10^5$ ， $n \leqslant 10^5$	同上一层，补上读入、树深、内存的处理	—

正文按「先暴力、再特例、最后正解」的顺序讲：暴力（另 30%）→ 只有一种运算（20%）→ 初值全同（20%）→ 正解（100%）。

前两层是各自独立的特例观察，正解不依赖它们；第三层给出本题的核心观察，正解与它共用同一套算法，区别只在 $10^6$ 级数据下的实现。正式主解是 main.cpp。

暴力解法：每次询问重算

适用范围

题面「另外 30%」的数据： $|s| \leqslant 1000$ ， $q \leqslant 1000$ ， $n \leqslant 1000$ 。

思路

后缀表达式求值是栈的标准应用，一趟扫描即可：

读到变量 x_i：把它的当前取值入栈；
读到 !：弹出一个值，取反后压回；
读到 & 或 |：弹出两个值（先右后左），算完压回。

扫描结束后栈里唯一的值就是表达式的值。每个询问先把 $x_k$ 取反，再把整条表达式重算一遍，栈顶即答案。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

vector<string> split_tokens(const string &s) {
    vector<string> tokens;
    int n = (int)s.size();
    int i = 0;
    while (i < n) {
        while (i < n && s[i] == ' ') {
            ++i;
        }
        if (i >= n) {
            break;
        }
        int j = i;
        while (j < n && s[j] != ' ') {
            ++j;
        }
        tokens.push_back(s.substr(i, j - i));
        i = j;
    }
    return tokens;
}

int evaluate_once(const vector<string> &tokens, const vector<int> &value, int flip_id) {
    vector<int> st;
    st.reserve(tokens.size());

    for (const string &token : tokens) {
        if (token[0] == 'x') {
            int id = stoi(token.substr(1));
            st.push_back(value[id] ^ (id == flip_id));
        } else if (token == "!") {
            int x = st.back();
            st.pop_back();
            st.push_back(x ^ 1);
        } else {
            int right = st.back();
            st.pop_back();
            int left = st.back();
            st.pop_back();
            if (token == "&") {
                st.push_back(left & right);
            } else {
                st.push_back(left | right);
            }
        }
    }
    return st.back();
}

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

    string expr;
    getline(cin, expr);
    vector<string> tokens = split_tokens(expr);

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

    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << evaluate_once(tokens, value, x) << '\n';
    }
    return 0;
}

复杂度与瓶颈

每次询问 $O(|s|)$ ， $q$ 次共 $O(|s| \times q)$ 。30% 档是 $1000 \times 1000 = 10^6$ ，轻松；100% 档是 $10^6 \times 10^5 = 10^{11}$ ，必超时。

瓶颈在于：除了被取反的那一个变量，所有询问的求值过程完全相同，重复计算占了绝大多数。

子任务解法：只有与运算或只有或运算

适用范围

题面第一个「对于 $20\%$ 的数据」：表达式中有且仅有与运算（&）或者或运算（|），既不混用，也不含 !。

思路

两个条件合起来就足够了：

每个变量在表达式里恰好出现一次；
全部二元运算符是同一种，而 &、| 都满足结合律与交换律。

于是无论表达式树长成什么形状，算出来的结果都等于对全部 $n$ 个变量做同一种运算：

运算符	整式的值
只有 `&`	所有变量都是 $1$ 时才是 $1$
只有 `\|`	至少有一个变量是 $1$ 就是 $1$

所以不必建树：数出初值里 $1$ 的个数 ones，翻转 $x_k$ 后新的个数是 $ones - v_k + (1 - v_k)$ ，再按上表判断，每次询问 $O(1)$ 。

代码里只需要从输入中认出是哪一种运算符，表达式结构本身可以整段跳过。

代码

cpp

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/**
 * 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-11 21:51
 * update_at: 2026-10-11 21:51
 */
/*
 * subtask_and_or.cpp：P7073 的 20% 档（表达式中只有一种二元运算）
 *
 * 这一档保证表达式里只有 & 或者只有 |，且不含 !。
 * 又因为每个变量恰好出现一次，同一种二元运算满足结合律：
 *   - 只有 &  => 整个表达式 = x1 & x2 & ... & xn（全为 1 才是 1）
 *   - 只有 |  => 整个表达式 = x1 | x2 | ... | xn（有一个 1 就是 1）
 * 所以根本不用建树，统计 1 的个数就能回答每次询问。
 */

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

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

    // 读表达式：只需要认出唯一出现的二元运算符，表达式结构本身不用管
    string tok;
    char op = 0;
    while (cin >> tok) {
        if (tok[0] >= '0' && tok[0] <= '9') {
            break; // 读到 n（表达式之后的第一个数字），此时 n 已经在 tok 里
        }
        if (tok[0] == '&' || tok[0] == '|') {
            op = tok[0]; // 该档只会出现其中一种
        }
    }
    int n = stoi(tok);

    int ones = 0; // 初值里 1 的个数
    vector<int> value(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> value[i];
        ones += value[i];
    }

    int q;
    cin >> q;
    while (q--) {
        int k;
        cin >> k;
        // 翻转 x_k：先减掉旧值，再加上取反后的值
        int new_ones = ones - value[k] + (1 - value[k]);
        if (op == '&') {
            // 全与：翻转后每个变量都是 1，结果才是 1
            cout << (new_ones == n ? 1 : 0) << '\n';
        } else {
            // 全或：翻转后至少有一个 1，结果就是 1
            cout << (new_ones > 0 ? 1 : 0) << '\n';
        }
    }
    return 0;
}

复杂度与瓶颈

时间 $O(|s| + n + q)$ （读表达式 + 统计 + 回答），空间 $O(n)$ 。

瓶颈：结论完全依赖「只有一种运算」。一旦 &、| 混用或出现 !，结合律就断了——例如 !x1 会让 $x_1$ 的贡献不再对称，光数个数就不够。所以这一档拿不到 100% 的分。

子任务解法：初值全为 0 或全为 1

适用范围

题面「另外 20%」：所有变量的初值相同（全 $0$ 或全 $1$ ），其余约束仍是 100% 档的规模，即 $|s|$ 可以到 $10^6$ 、 $q$ 可以到 $10^5$ 。

思路

第一步：把问题化归。

初值全同时，整个表达式算出来是一个常数 $V$ 。一次询问只翻转一个变量，所以根的值只有两种可能：跟着翻成 $\neg V$ ，或者原地不动仍是 $V$ 。于是每次询问真正在问的是：

这个变量的翻转，能不能一路传到根？

这一步与初值究竟是 $0$ 还是 $1$ 无关，可以对所有询问统一预处理一次。

（顺带说明：这个化归对任意初值其实都成立；题面把它单列成一档，是因为全同初值下 $V$ 是常数，「答案只有 $V$ 和 $\neg V$ 两种」一眼可见，观察最容易落地。）

第二步：把后缀表达式建成树。

后缀表达式天然对应一棵表达式树，用栈就能建出来：

遇到变量 x_i：建一个叶子节点，节点编号入栈；
遇到 !：弹出栈顶节点当孩子，建非门节点入栈；
遇到 & 或 |：弹出两个节点（先右后左），建对应节点入栈。

最后栈底剩下的就是根。拿样例 x1 x2 & x3 | 走一遍：

text

1
2
3
4
5读 x1 → 栈: [1]             节点1 = x1
读 x2 → 栈: [1, 2]          节点2 = x2
读 &  → 弹出 2、1 → 栈: [3]  节点3 = &，左孩子 1，右孩子 2
读 x3 → 栈: [3, 4]          节点4 = x3
读 |  → 弹出 4、3 → 栈: [5]  节点5 = |，左孩子 3，右孩子 4

得到的节点 5 就是根，它的左孩子是 & 节点，右孩子是 x3。

第三步：自底向上求一遍值。

dfs1(u) 递归算出每个节点的当前值：叶子取变量初值，非门取反，与门、或门按左右孩子的值算。这趟结束时根节点的值就是原表达式的值 $V$ 。

第四步：自顶向下传播「能否影响根」。

dfs2(u, about) 中的 about 表示：当前节点 $u$ 的值发生变化时，会不会影响根。传播规则只有三条：

门	传递条件
`!`	永远原样传给孩子——取反是可逆的，孩子变了它一定变
`&`	只有当另一个孩子当前值为 $1$ 时才传
`\|`	只有当另一个孩子当前值为 $0$ 时才传

二元门这两条正是短路：0 & x 已经被那个 $0$ 卡死，1 | x 已经被那个 $1$ 卡死，另一边怎么翻都无济于事；只有没被卡死的一侧，变化才穿得过去。

可以把 about 想成一根从根放下来的绳子，每个门要么让绳子过去，要么把它剪断：! 永远放行，& 只有另一边是 $1$ 才放行，| 只有另一边是 $0$ 才放行。绳子最后连到某个变量叶子上，就说明翻转这个变量能改变根。

第五步：回答询问。

叶子上记下的 can_affect 就是最终答案。因为只有一个变量被翻转、其余都没动，能影响根时根值一定取反，不能影响时根值一定不变：

text

1can_affect[x_k] ? 输出 V ^ 1 : 输出 V

代码

本层不单独给出代码：算法与正解完全相同，实现见下文正解的 main.cpp。

复杂度与瓶颈

建树、求值、影响传播都是线性的，预处理 $O(|s|)$ ，每个询问 $O(1)$ ，总复杂度 $O(|s| + q)$ ，空间 $O(|s|)$ 。

瓶颈已经不在算法上，而在实现上： $|s|$ 到 $10^6$ 时读入怎么写、节点开多大、表达式退化成链时递归会不会爆栈——这些留给正解。

正解

关键观察

算法在上一层已经写完，100% 档的新问题全在规模上：

读入： $|s|$ 达 $10^6$ ，不能先读整行再切分，用 cin >> tok 流式读 token 即可；读到第一个纯数字时它就是 $n$ ，表达式到此结束。
节点数：节点数 = 变量数 + 运算符数 $= O(|s|)$ ，用静态大数组 node[]，按 ++node_cnt 递增编号分配（数组 + 分配指针的动态化静态写法）。
树深：链状表达式（如 x1 x2 & x3 & x4 & ...）的深度是 $O(|s|)$ ，dfs1 / dfs2 是递归，深度极端时有爆栈风险，必要时可换成显式栈的迭代写法；本实现按评测环境的栈空间直接递归。
询问： $q$ 到 $10^5$ ，必须 $O(1)$ ，靠 var_node[x] → can_affect[] 查表，不再碰表达式。

思路

对应代码的五个部分：

init_tokens()：流式读入后缀表达式的 token，遇到第一个数字就拿到 $n$ 并结束；
build_tree()：按上一层第二步的栈规则建树，var_node[id] 记下每个变量对应的叶子节点，返回根编号；
dfs1(root)：自底向上求出每个节点的当前值，根值记为 root_val；
dfs2(root, true)：自顶向下按三条短路规则标 can_affect[]；
询问阶段只查表：能影响根就输出 root_val ^ 1，否则输出 root_val。

代码

cpp

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147/**
 * 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: 2025-11-28 15:41
 * update_at: 2025-11-28 15:41
 */
/*
 * 题目：[CSP-J 2020] 表达式 (luogu 7073)
 * 核心思路：
 * 1. 表达式为后缀表达式，通过栈将其转化为表达式树。
 * 2. 第一次 DFS (dfs1)：从下往上求出所有节点原本的值。
 * 3. 第二次 DFS (dfs2)：从上往下传递"当前节点的改变是否会影响最终结果"。
 *    - 对于非门 (!)，影响直接向下传递。
 *    - 对于与门 (&)，如果另一半的值为 1，则本侧的改变会影响整体结果；否则被短路。
 *    - 对于或门 (|)，如果另一半的值为 0，则本侧的改变会影响整体结果；否则被短路。
 * 4. 预处理结束后，针对每个查询只需 O(1) 查表。
 */

#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;

// ===== 输入数据 =====
const int MAXN = 1e6+5;
int n, q;
int init_val[MAXN];
vector<string> tokens; // 后缀表达式的所有 token

// ===== 表达式树 =====
struct Node {
    char type; // 'x' 变量, '!' 非门, '&' 与门, '|' 或门
    int lch, rch;
    int var_id;
    int val;
} node[MAXN];
int node_cnt = 0;

int var_node[MAXN]; // 变量 x_i 对应的节点编号
stack<int> stk;

// ===== 预处理结果 =====
bool can_affect[MAXN]; // 该节点的变化是否影响根节点

// dfs1: 从下至上求出每个节点的值
int dfs1(int u) {
    if (node[u].type == 'x') {
        return node[u].val = init_val[node[u].var_id];
    }
    if (node[u].type == '!') {
        int child_val = dfs1(node[u].lch);
        return node[u].val = child_val ^ 1;
    }
    int lval = dfs1(node[u].lch);
    int rval = dfs1(node[u].rch);
    if (node[u].type == '&') {
        return node[u].val = lval & rval;
    }
    return node[u].val = lval | rval;
}

// dfs2: 从根向下传播"影响标记"
// affects_root: 当前节点的变化是否会影响根节点
void dfs2(int u, bool affects_root) {
    can_affect[u] = affects_root;
    if (node[u].type == 'x') return;
    if (!affects_root) {
        dfs2(node[u].lch, false);
        if (node[u].type != '!')
            dfs2(node[u].rch, false);
        return;
    }
    if (node[u].type == '!') {
        dfs2(node[u].lch, true);
        return;
    }
    int lch = node[u].lch, rch = node[u].rch;
    if (node[u].type == '&') {
        dfs2(lch, node[rch].val == 1);
        dfs2(rch, node[lch].val == 1);
    } else {
        dfs2(lch, node[rch].val == 0);
        dfs2(rch, node[lch].val == 0);
    }
}

// 读入表达式所有 token 和变量个数 n
void init_tokens() {
    string tok;
    while (cin >> tok) {
        if (tok[0] >= '0' && tok[0] <= '9') {
            n = stoi(tok);
            break; // 表达式 token 只含 x... ! & |，遇到数字就是 n
        }
        tokens.push_back(tok);
    }
}

// 根据全局 tokens 建立表达式树，返回根节点编号
int build_tree() {
    for (const string &tok : tokens) {
        if (tok[0] == 'x') {
            int id = stoi(tok.substr(1));
            node[++node_cnt] = {'x', 0, 0, id, 0};
            var_node[id] = node_cnt;
            stk.push(node_cnt);
        } else if (tok[0] == '!') {
            int child = stk.top(); stk.pop();
            node[++node_cnt] = {'!', child, 0, 0, 0};
            stk.push(node_cnt);
        } else {
            int right = stk.top(); stk.pop();
            int left  = stk.top(); stk.pop();
            node[++node_cnt] = {tok[0], left, right, 0, 0};
            stk.push(node_cnt);
        }
    }
    return stk.top();
}

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

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

    int root = build_tree();
    dfs1(root);
    dfs2(root, true);

    cin >> q;
    int root_val = node[root].val;
    while (q--) {
        int x;
        cin >> x;
        if (can_affect[var_node[x]])
            cout << (root_val ^ 1) << '\n';
        else
            cout << root_val << '\n';
    }
    return 0;
}

复杂度

时间复杂度 $O(|s| + q)$ ，空间复杂度 $O(|s|)$ 。

总结

这题的难点不在后缀表达式本身，而在看出「翻转一个变量是否有用」可以预处理。把「每次重算整式」改成「先判断哪些变量能影响根」，复杂度就从 $O(|s| \times q)$ 降到 $O(|s| + q)$ 。

另一个重要的思维是短路传播：二叉树中一个节点的值是否受某个子树影响，往往取决于另一棵子树的值。「一边卡死另一边」的模式在表达式求值、决策树剪枝里都很常见。

四个分数档位串起来是一条「从重复计算到预处理」的路线：每次重算整条式子 → 结构特殊时直接看出答案 → 把重算变成影响标记 → 在 $10^6$ 规模上把它落地。真正需要记住的只有那三条短路规则。

图示解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P7073 [CSP-J 2020] 表达式

题目描述

小 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

text

1
2
3
4
5
6
7x1 x2 & x3 |
3
1 0 1
3
1
2
3

输出 #1

text

输入输出样例 #2

输入 #2

text

1
2
3
4
5
6
7x1 ! x2 x4 | x3 x5 ! & & ! &
5
0 1 0 1 1
3
1
3
5

输出 #2

text

说明/提示

样例 1 解释

该后缀表达式的中缀表达式形式为 $(x_1 \operatorname{and} x_2) \operatorname{or} 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 解释

该表达式的中缀表达式形式为 $(\operatorname{not}x_1)\operatorname{and}(\operatorname{not}((x_2\operatorname{or}x_4)\operatorname{and}(x_3\operatorname{and}(\operatorname{not}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$ 的长度。

[CSP-J 2020] 表达式

目录

形式化题目

解法路线

暴力解法：每次询问重算

适用范围

思路

代码

复杂度与瓶颈

子任务解法：只有与运算或只有或运算

适用范围

思路

代码

复杂度与瓶颈

子任务解法：初值全为 0 或全为 1

适用范围

思路

代码

复杂度与瓶颈

正解

关键观察

思路

代码

复杂度

总结

图示解析