题目背景

PA 2025 R5A.

警告：滥用本题评测一次即可封号。

这里提供了本题的部分测试点（你可以在附件中下载它们），强烈建议上述题目提交通过后再提交本题。

题目描述

有 $10^6$ 棵树，自西向东编号 $1\sim 10^6$。小恐龙的营地在第 $1$ 棵树西边。

在接下来的 $n$ 天中，小恐龙的饮食计划为：

• 第 $i$ 天，她将从营地步行到树 $a_i$，再返回营地。
• 从营地去树 $a_i$ 的途中，她会摘下遇到的所有奇数编号的树的 $v_i$ 片叶子；
• 从树 $a_i$ 返回营地的途中，她会摘下遇到的所有偶数编号的树的 $v_i$ 片叶子。

不难发现，每天，每棵树至多只被摘一次叶子。

一开始，$v_i=0$。有 $m$ 次修改：

• 第 $j$ 次修改将前 $p_j$ 天的 $v_i$（$i = 1, 2, \ldots, p_j$）每个增加 $w_j$。

此外，修改间隙有 $z$ 次查询：

• 第 $j$ 次查询：求出在前 $p_j$ 天中，第 $d_j$ 棵树被吃掉的总叶子数。

修改会影响所有后面的查询，但是每个查询之间是独立的。

输入格式

第一行，三个正整数 $n,m,z$。

第二行，$n$ 个正整数 $a_1,a_2,\ldots,a_n$。

接下来 $(m+z)$ 行，每行三个正整数：

• $\texttt{1}$ $p_j$ $w_j$，描述一次修改操作；
• $\texttt{2}$ $p_j$ $d_j$，描述一次查询操作。

输出格式

输出 $z$ 行，每行一个非负整数，表示查询的答案。

3 2 4
3 4 1
2 3 1
1 2 10
2 1 2
2 3 1
1 3 1
2 3 2

0
10
20
22

提示

样例解释

饮食计划如下：

• 第 $1$ 天：前往 $a_1 = 3$ 号树；去程摘奇数编号树（$1, 3$）的叶子，返程摘偶数编号树（$2$）的叶子。
• 第 $2$ 天：前往 $a_2 = 4$ 号树；去程路径摘 $1, 3$ 的叶子；返程摘 $4, 2$ 的叶子。
• 第 $3$ 天：前往 $a_3 = 1$ 号树；去程摘 $1$ 的叶子，返程不摘叶子。

初始时所有 $v_1 = v_2 = v_3 = 0$，即实际上一片叶子都不会摘。

1. 第一次查询，问前 $3$ 天中，$1$ 号树被摘掉的叶子数。答案显然为 $0$。

2. 第一次修改，将前 $2$ 天的 $v_i$ 各增加 $10$。
   此时 $v_1=10,v_2=10,v_3=0$。

3. 第二次查询，问第 $1$ 天中，$2$ 号树被摘掉的叶子数。

   由于第一天返程时摘了 $2$ 号树的叶子，所以答案为 $10$。

4. 第三次查询，问前 $3$ 天中，$1$ 号树被摘掉的总叶子数。

   由于前两天都会摘 $1$ 号树的叶子，所以答案为 $10+10=20$。

5. 第二次修改，将前 $3$ 天的 $v_i$ 各加 $1$。

   此时，$v_1=11,v_2=11,v_3=1$。

6. 第四次查询，问前 $3$ 天中，$2$ 号树摘掉的叶子数。

   答案为 $11 + 11 + 0 = 22$。

数据范围

• $1 \leq n, m, z \leq 10^6$；
• $n \cdot m \cdot z \leq 10^{16}$；
• $1\le a_i,w_j,d_j\le 10^6$；
• $1\le p_j\le n$。

子任务

子任务 $0$ 为样例。

下表中，符号 $a \sim b$ 表示 $0.99 \cdot b < a \le b$。

子任务编号	限制
$1$	$(m + z) \cdot n \le 10^7$
$2$	$z \cdot m \le 10^7$，$n \cdot m \cdot z \sim 10^{13}$
$3$	$n = 10^4$，$n \cdot m \cdot z \sim 10^{14}$
$4$	$m = 10^4$，$n \cdot m \cdot z \sim 10^{14}$
$5$	$z = 10^4$，$n \cdot m \cdot z \sim 10^{14}$
$6$	$n \cdot m \cdot z \sim 10^{14}$
$7$	$n = 10^4$，$n \cdot m \cdot z \sim 10^{16}$
$8$	$m = 10^4$，$n \cdot m \cdot z \sim 10^{16}$
$9$	$z = 10^4$，$n \cdot m \cdot z \sim 10^{16}$
$10$	$n \cdot m \cdot z \sim 10^{16}$