分数: 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