2020 T3 表达式

主知识点：动态规划。交叉标签：动态规划、树形动态规划、深搜、栈、表达式。
暴力标注：DP 可用暴力拿部分分。
OJ 使用标准输入与标准输出。原比赛文件名为 expr.in / expr.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 256 MiB；测试点 20；总分 100。
数据来源：公开存档数据；未逐文件对照官网下载包。

题目描述

输入一个后缀逻辑表达式，变量只能取 0 或 1，每个变量出现恰好一次。二元运算 & 表示逻辑与，| 表示逻辑或；一元运算 ! 表示取反。变量写为 x 加正整数下标，如 x10。运算符和操作数由空格分隔，末尾无空格。

后缀表达式中，二元运算写为“左子表达式 右子表达式 运算符”，一元运算写为“子表达式 !”。给出每个变量初值，随后每次询问指定一个变量：仅翻转这个变量后，求整个表达式的值。所有询问独立，之前询问的翻转不会保留。

输入格式

第一行包含一个字符串 $s$，表示上文描述的表达式。

第二行包含一个正整数 $n$，表示表达式中变量的数量。表达式中变量的下标为 $1,2, \cdots , n$。

第三行包含 $n$ 个整数，第 $i$ 个整数表示变量 $x_i$ 的初值。

第四行包含一个正整数 $q$，表示询问的个数。

接下来 $q$ 行，每行一个正整数，表示需要取反的变量的下标。注意，每一个询问的修改都是临时的，即之前询问中的修改不会对后续的询问造成影响。

数据保证输入的表达式合法。变量的初值为 $0$ 或 $1$。

输出格式

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

样例

样例 1

输入：

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

输出：

1
1
0

样例 2

输入：

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

输出：

0
1
1

数据范围与特殊性质

• 对于 $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$ 的长度。

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

暴力退路标注（教学补充）

DP 可用暴力拿部分分。每次询问临时翻转该变量，再用栈从头计算后缀表达式，最后恢复变量。O(q|s|)，另外 30% 的 |s|、n、q≤1000 数据可做。查询相互独立。

目标范围：30 分规模部分；加仅 &/仅 | 特判可争取 50 分。部分分按原题规模判断，不构成对任意实现或评测机的得分保证。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P7073
• 赛事：CSP-J 第二轮入门级 2020。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。