P16758 [GKS 2020 #C] Candies

Carl 有 $N$ 颗糖果组成的数组。数组的第 $i$ 个元素（下标从 $1$ 开始）为 $A_i$，表示第 $i$ 颗糖果的**甜度值**。他想执行一系列 $Q$ 个操作。操作有两种类型： - 更新数组中某颗糖果的甜度值。 - 查询某个子数组的**甜度分数**。 从下标 $l$ 到 $r$ 的子数组的甜度分数定义为： $A_l \times 1 - A_{l+1} \times 2 + A_{l+2} \times 3 - A_{l+3} \times 4 + A_{l+4} \times 5 \dots$ 形式化地，甜度分数为 $\sum_{i=l}^{r} (-1)^{i-l} A_i \times (i - l + 1)$。 例如： - $[3, 1, 6]$ 的甜度分数为 $3 \times 1 - 1 \times 2 + 6 \times 3 = 19$。 - $[40, 30, 20, 10]$ 的甜度分数为 $40 \times 1 - 30 \times 2 + 20 \times 3 - 10 \times 4 = 0$。 - $[2, 100]$ 的甜度分数为 $2 \times 1 - 100 \times 2 = -198$。 Carl 想求出所有查询操作的甜度分数之和。如果没有查询操作，则和为 $0$。你能帮助 Carl 求出这个和吗？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含 $N$ 和 $Q$。第二行包含 $N$ 个整数描述数组，其中第 $i$ 个整数为 $A_i$。接下来的 $Q$ 行中的第 $j$ 行描述第 $j$ 个操作。每行以一个字符开头，表示操作类型（`U` 表示更新，`Q` 表示查询）。 - 对于更新操作，后面跟两个整数 $X_j$ 和 $V_j$，表示将数组的第 $X_j$ 个元素修改为 $V_j$。 - 对于查询操作，后面跟两个整数 $L_j$ 和 $R_j$，表示查询从第 $L_j$ 个元素到第 $R_j$ 个元素（包含两端）的子数组的甜度分数。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是所有查询操作的甜度分数之和。

在样例 #1 中： - 第一个查询询问子数组 $[3, 9, 8]$ 的甜度分数，计算为 $3 \times 1 - 9 \times 2 + 8 \times 3 = 9$。 - 第二个查询询问子数组 $[2]$ 的甜度分数，计算为 $2 \times 1 = 2$。 - 第三个查询询问子数组 $[1, 10]$ 的甜度分数，计算为 $1 \times 1 - 10 \times 2 = -19$。 因此最终输出为 $9 + 2 - 19 = -8$。 在样例 #2 中： - 第一个（也是唯一一个）查询询问子数组 $[7, 5]$ 的甜度分数，计算为 $7 \times 1 - 5 \times 2 = -3$。 因此最终输出为 $-3$。 ### 限制条件 $1 \le T \le 100$。 对于所有 $i$，$1 \le A_i \le 100$。 最多 $6$ 个测试用例满足 $1 \le N \le 2 \times 10^5$ 且 $1 \le Q \le 10^5$。 其余测试用例满足 $1 \le N \le 300$ 且 $1 \le Q \le 300$。 如果第 $j$ 个操作为更新操作，则 $1 \le X_j \le N$ 且 $1 \le V_j \le 100$。 如果第 $j$ 个操作为查询操作，则 $1 \le L_j \le R_j \le N$。 **测试集 1** 最多有 $5$ 个更新操作。 **测试集 2** 无特殊限制。 翻译由 DeepSeek V4 Pro 完成