← 返回题目列表

AtCoder · awc0076_c

C. 幻方反转

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥是一名学徒巫师,接受训练以破译魔法阵上铭刻的公式。魔法阵中有数学表达式 波兰表示法 (前缀表示法)。

波兰表示法是一种将运算符置于其操作数之前的表示法。这里处理的所有运算符都是 4 二元运算符的类型: +, -, *, /。波兰表示法表达式递归定义如下:

  • 单个整数是波兰表示法表达式,其计算结果是该整数本身。
  • op A B (其中 op 是一个二元运算符,并且 A 和 B 都是波兰记数表达式)也是一个波兰记数表达式,其求值结果是应用运算符的结果 op 评价结果 A 和 B.

司 / is 朝零方向截断除法。即舍去商作为实数的小数部分,取更接近的整数 0 被视为结果(例如, 7 / 2 = 3, (-7) / 2 = -3, 7 / (-2) = -3).

例如,表达式写为 标准中缀表示法中的 (3 + 5) * 2 表示为 * + 3 5 2 采用波兰表示法。该表达式由以下部分组成 5 代币 *, +, 3, 5, 2,其评价结果为 16.

表达式作为以下序列给出 代币 (表示运算符或整数的字符串)。令牌是运算符当且仅当它是 1- 与其中之一完全匹配的字符串 +, -, *, /。所有其他标记都表示整数。例如, -3 包括 2 字符且不匹配任何 +, -, *, /,所以它不是一个运算符,而是代表整数 -3。另一方面,当令牌 - 单独出现(作为 1- 字符串),它始终表示减法运算符,并且永远不会被解释为负号。

表示整数的标记以十进制表示法给出。对于负整数,负号 - 已预先添加。排除负号的部分不包含不必要的前导 0s(但是,代表整数的标记 0 是单个字符 0)。代币 -0 从未给出。

有一天,高桥发现了一个古老的魔法阵,并试图破译上面刻着的波兰符号表达式。然而,淘气的青木对魔法阵施加了反转诅咒,用配对的运算符取代了一些运算符。具体来说,青木选择了 K 不同的位置(1-索引)来自令牌序列。每个选定位置的令牌都保证是一个运算符,Aoki 对每个位置执行了以下替换:

  • + 替换为 -,和 - 替换为 +
  • * 替换为 /,和 / 替换为 *

Takahashi 想知道原始表达式的求值结果 之前 诅咒和表达式的求值结果 之后 诅咒。

给你一系列 N 代币 t_1, t_2, \ldots, t_N 构成原始波兰表示法表达式,以及 K 整数 p_1, p_2, \ldots, p_K 代表青木反转的运算符的位置。分别计算原表达式的求值结果和反演表达式的求值结果。

约束

  • 1 \leq N \leq 2 \times 10^5
  • N 是奇数
  • 令牌序列 t_1, t_2, \ldots, t_N 构成有效的波兰表示法表达式
  • 每个令牌 t_i 是一个运算符( 1- 与以下之一完全匹配的字符串 +, -, *, /) 或表示整数的字符串
  • 每个整数标记所表示的整数的绝对值最多为 10^9
  • 0 \leq K \leq N
  • 1 \leq p_i \leq N (1 \leq i \leq K)
  • p_1, p_2, \ldots, p_K 都是不同的
  • 令牌 t_{p_i} 在每个位置 p_i 是一个运算符
  • 不除以 0 在计算原始表达式或反转表达式期间发生
  • 在原始表达式或倒排表达式求值期间出现的每个子表达式(中间结果和最终结果)的求值结果的绝对值最多为 10^{18}

输入

当 K > 0:

N
t_1 t_2 \cdots t_N
K
p_1 p_2 \cdots p_K

当 K = 0:

N
t_1 t_2 \cdots t_N
0
  • 第一行包含一个整数 N 代表代币数量。
  • 第二行包含 N 代币 t_1, t_2, \ldots, t_N 构成波兰表示法表达式,以空格分隔。
  • 第三行包含一个整数 K 代表青木倒数算子的数量。
  • 当 K > 0,第四行包含 K 整数 p_1, p_2, \ldots, p_K 以空格分隔,代表 1- 要反转的运算符的标记序列中的索引位置。当 K = 0,第四行不存在。

输出

输出 2 行。

  • 在第一行,以整数形式输出原始表达式(求逆前)的求值结果。
  • 在第二行,以整数形式输出倒置表达式的求值结果。

示例输入 1

5
* + 3 5 2
1
1

示例输出 1

16
4

示例输入 2

3
/ -7 2
1
1

示例输出 2

-3
-14

示例输入 3

21
+ / + * -8 3 7 - 10 2 * - / 20 3 -5 + * 2 -3 4
5
1 2 4 11 18

示例输出 3

-24
38

示例输入 4

31
- * - + 5 1 * 2 3 + / 21 3 - 9 2 / - * 7 2 + 1 3 * - 9 4 / 50 5
7
1 4 7 11 17 25 29

示例输出 4

0
280

示例输入 5

1
-1000000000
0

示例输出 5

-1000000000
-1000000000