P11930 [PA 2025] 吃树叶 / Liście

PA 2025 R5A. **警告：滥用本题评测一次即可封号。** [这里](https://www.luogu.com.cn/problem/U547677)提供了本题的部分测试点（你可以在**附件**中下载它们），**强烈建议上述题目提交通过后再提交本题。** 注记：原题评测机速度应该不快于洛谷的 $1/4$。

有 $10^6$ 棵树，自西向东编号 $1\sim 10^6$。小恐龙的营地在第 $1$ 棵树西边。  在接下来的 $n$ 天中，小恐龙的饮食计划为： - 第 $i$ 天，她将从营地步行到树 $a_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$ 行，每行一个非负整数，表示查询的答案。

### 样例解释 饮食计划如下： - 第 $1$ 天：前往 $a_1 = 3$ 号树； - 第 $2$ 天：前往 $a_2 = 4$ 号树； - 第 $3$ 天：前往 $a_3 = 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}$ |