#1470. CSP-模拟赛001-T3

CSP-模拟赛001-T3

题目描述

现给出一个后缀形式的逻辑表达式,其中只包含三种逻辑运算符:与(&)、或(|)、非(!)。

其中,操作数为变量,用 xix_i 来表示( ii 为正整数),具体为 x1x2x3 ... xnx1、x2、x3~...~x_n ,操作数、操作符之间都由一个空格隔开。

数据保证每个变量仅在表达式中出现一次

接下来给出 mm 次询问,每次询问会临时将一个变量的值取反,请计算出取反后表达式的值是多少。

注意:本次取反修改的值不保留,即不会影响下一次询问

输入格式

第一行为字符串 ss,即后缀形式的逻辑表达式。 第二行为正整数 nn,即表达式中变量的数量。 第三行为 nn 个整数,即变量 xix_i 的值,仅包含 00 或者 11。 第四行为正整数 mm,即询问的次数。 接下来 mm 行,每行一个正整数,表示需要取反的变量的下标(从 11 开始)。

输出格式

输出一共有 mm 行,每行为 0011,即该次询问时表达式的值。

样例 #1

样例输入 #1

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

样例输出 #1

1
1
0

样例 #2

样例输入 #2

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

样例输出 #2

0
1
1

提示

样例 1 解释

该样例的中缀表达式为: (x1 & x2)  x3(x_1~\&~x_2)~|~x_3。 其中 x1,x2,x3x_1,x_2,x_3 的值分别为 1,0,11,0,1

三次询问如下:

  • x1x_1 取反。 (0 & 0)  1=1(0~\&~0)~|~1=1
  • x2x_2 取反。 (1 & 1)  1=1(1~\&~1)~|~1=1
  • x3x_3 取反。 (1 & 0)  0=0(1~\&~0)~|~0=0

样例 2 解释

该样例的中缀表达式为:!x1 & !((x2  x4) & (x3 & !x5))!x_1~\&~!((x_2~|~x_4)~\&~(x_3~\&~!x_5))

数据规模与约定

字符串 ss 的长度记作s|s|,有:

1s1×1061 \le |s| \le 1 \times 10^61m1×1051 \le m \le 1 \times 10^52n1×1052 \le n \le 1 \times 10^5