计算器 - 代码源竞赛平台

题目描述

一台计算器可以执行以下两种指令：

• ADD a：将当前的数加上整数 $a$。
• FLIP：将当前的数取相反数。

现有 $n$ 条指令，按执行顺序依次编号为 $1,2,\ldots,n$。

你需要回答 $q$ 次询问。每次询问给出三个整数 $l,r,K$：将计算器的初始值设为 $K$，跳过编号为 $l,l+1,\ldots,r$ 的指令，并按原顺序执行其余指令。请计算所有剩余指令执行完毕后，计算器中的数。

各次询问相互独立，跳过的指令不会影响其他询问。若跳过全部指令，计算器中的数保持为初始值 $K$。

输入格式

第一行包含两个整数 $n,q$，分别表示指令数和询问数。

接下来 $n$ 行，第 $i$ 行描述第 $i$ 条指令，格式为 ADD a 或 FLIP，含义如题目描述所示。

接下来 $q$ 行，每行包含三个整数 $l,r,K$，表示一次询问。

输出格式

输出 $q$ 行，按输入顺序给出各次询问的答案。每行输出一个整数，表示该次询问中计算器的最终值。

样例

5 4
ADD 3
FLIP
ADD -2
FLIP
ADD 4
2 3 1
1 1 2
4 5 -3
1 5 7

0
8
-2
7

1 2
FLIP
1 1 0
1 1 -5

0
-5

样例解释

对于样例 $1$：

• 第一次询问跳过第 $2,3$ 条指令，计算器中的数依次为 $1\to 4\to -4\to 0$，最终值为 $0$。
• 第二次询问跳过第 $1$ 条指令，计算器中的数依次为 $2\to -2\to -4\to 4\to 8$，最终值为 $8$。
• 第三次询问跳过第 $4,5$ 条指令，计算器中的数依次为 $-3\to 0\to 0\to -2$，最终值为 $-2$。
• 第四次询问跳过全部指令，最终值为初始值 $7$。

对于样例 $2$，两次询问均跳过唯一的一条指令，因此最终值分别为各自的初始值 $0$ 和 $-5$。

数据规模

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

子任务编号	分数	$n,q\le$	特殊性质
$1$	$30$	$1000$	无
$2$	$30$	$2\times 10^5$	A
$3$	$40$		无

特殊性质 A：每次询问均有 $l=r$ 且 $K = 1$。

对于 $100\%$ 的数据，$1\le n,q\le 2\times 10^5$，$1\le l\le r\le n$，$-10^9\le a,K\le 10^9$。每条指令均为 ADD a 或 FLIP。