题目描述
函数是各种编程语言中一项重要的概念，借助函数，我们总可以将复杂的任务分解成一个个相对简单的子任务，直到细化为十分简单的基础操作，从而使代码的组织更加严密、更加有条理。然而，过多的函数调用也会导致额外的开销，影响程序的运行效率。
某数据库应用程序提供了若干函数用以维护数据。已知这些函数的功能可分为三类：
- 将数据中的指定元素加上一个值；
- 将数据中的每一个元素乘以一个相同值；
- 依次执行若干次函数调用，保证不会出现递归（即不会直接或间接地调用本身）。
在使用该数据库应用时，用户可一次性输入要调用的函数序列（一个函数可能被调用多次），在依次执行完序列中的函数后，系统中的数据被加以更新。 某一天，小 A 在应用该数据库程序处理数据时遇到了困难：由于频繁而低效的函数调用，系统在执行操作时进入了无响应的状态，他只好强制结束了数据库程序。为了计算出正确数据，小 A 查阅了软件的文档，了解到每个函数的具体功能信息，现在他想请你根据这些信息帮他计算出更新后的数据应该是多少。
输入格式
第一行一个正整数 $n$，表示数据的个数。
第二行 $n$ 个整数，第 $i$ 个整数表示下标为 $i$ 的数据的初始值为 $a_i$。
第三行一个正整数 $m$，表示数据库应用程序提供的函数个数。函数从 $1\ldots m$ 编号。
接下来 $m$ 行中，第 $j$（$1 \le j \le m$）行的第一个整数为 $T_j$，表示 $j$ 号函数的类型：
- 若 $T_j = 1$，接下来两个整数 $P_j,~V_j$ 分别表示要执行加法的元素的下标及其增加的值；
- 若 $T_j = 2$，接下来一个整数 $V_j$ 表示所有元素所乘的值；
- 若 $Tj = 3$，接下来一个正整数 $C_j$ 表示 $j$ 号函数要调用的函数个数，随后 $C_j$ 个整数 $g_1^{(j)},~g_2^{(j)},~\ldots,~g{C_j}^{(j)}$，依次表示其所调用的函数的编号。
第 $m + 4$ 行一个正整数 $Q$，表示输入的函数操作序列长度。
第 $m + 5$ 行 $Q$ 个整数 $f_i$，第 $i$ 个整数表示第 $i$ 个执行的函数的编号。
输出格式
一行 $n$ 个用空格隔开的整数，按照下标 $1\ldots n$ 的顺序，分别输出在执行完输入的函数序列后，数据库中每一个元素的值。答案对 $\boldsymbol{998244353}$ 取模。
Input & Output ‘s examples
Input ‘s eg 1
3 |
Output ‘s eg 1
6 8 12 |
Input ‘s eg 2
10 |
Output ‘s eg 2
36 282 108 144 180 216 504 288 324 360 |
数据范围和约定
| 测试点编号 | $n,m,Q\le$ | $\sum C_j$ | 其他特殊限制 |
|---|---|---|---|
| $1\sim 2$ | $1000$ | $=m-1$ | 函数调用关系构成一颗树 |
| $3\sim 4$ | $1000$ | $\le 100$ | |
| $5\sim 6$ | $20000$ | $\le 40000$ | 不含第 $2$ 类函数或不含第 $1$ 类函数 |
| $7$ | $20000$ | $=0$ | |
| $8\sim 9$ | $20000$ | $=m-1$ | 函数调用关系构成一颗树 |
| $10\sim 11$ | $20000$ | $\le 2\times 10^5$ | |
| $12\sim 13$ | $10^5$ | $\le 2\times 10^5$ | 不含第 $2$ 类函数或不含第 $1$ 类函数 |
| $14$ | $10^5$ | $=0$ | |
| $15\sim 16$ | $10^5$ | $=m-1$ | 函数调用关系构成一颗树 |
| $17\sim 18$ | $10^5$ | $\le 5\times 10^5$ | |
| $19\sim 20$ | $10^5$ | $\le 10^6$ |
分析
官方数据水到写了就是50起步真的可以……
读完题后不难发现数列的初始化相当于对于每一个 $i(i \in \lbrack 1 , n \rbrack)$ 执行操作 1 i a[i]。
先考虑不含操作三的 $10$ 分(可以直接线段树2草过去，但对于正解无任何启发作用)，手玩几组数据看一下操作二的本质：
设 $a = \lbrack 2 , 3 , 4 \rbrack$，操作序列分别为 $(1 , 1 , 1) , (2 , 4) , (1 , 1 , 2) , (2 , 3) , (1 , 2 , 4)$。
从初始化开始模拟，过程如下：
- 设初始时 $a = \lbrack 0 , 0 , 0 \rbrack$。
- 将 $1$ 号位置加 $2$，此时 $a = \lbrack 2 , 0 , 0 \rbrack$。
- 将 $2$ 号位置加 $3$，此时 $a = \lbrack 2 , 3 , 0 \rbrack$。
- 将 $3$ 号位置加 $4$，此时 $a = \lbrack 2 , 3 , 4 \rbrack$。
- 将 $1$ 号位置加 $1$，此时 $a = \lbrack 3 , 3 , 4 \rbrack$。
- 全局乘 $4$，此时 $a = \lbrack 12 , 12 , 16 \rbrack$。
- 将 $1$ 号位置加 $2$，此时 $a = \lbrack 14 , 12 , 16 \rbrack$。
- 全局乘 $3$，此时 $a = \lbrack 42 , 36 , 48 \rbrack$。
- 将 $2$ 号位置加 $4$，此时 $a = \lbrack 42 , 36 , 52 \rbrack$。
为行文方便，下文中用操作一代表题干中的操作一，用 $i$ 号操作代指上面模拟时的编号 $i$。
之后考虑每一个操作二对其前面操作的影响，可以发现，$5$ 号操作相当于让前四个操作执行了 $4$ 次，而 $7$ 号操作相当于让 “前四个操作执行 $4$ 次” 这个操作再执行 $3$ 次，故前四个操作总共执行了 $12$ 次。
综上所述，操作二的本质即让前面的操作执行 $val_i$ 次。
定义执行 $T$ 次操作二之后 (下文简称 $T$ 时刻) 所有操作执行的次数为 $T$时刻的 叠乘系数，则对于上面的情况我们只需要维护这个叠乘系数即可，这可以通过倒着处理所有操作实现。
接下来继续考虑有操作三的情况，我们将每一个操作抽象为一个点，对于每一个操作三，我们将其向其所有子操作连边。因为题面已经提到不会出现递归，故完成后的图一定是一个 $\text{DAG}，则我们可以通过 \text{dp}$ 计算每个操作之后叠乘系数将会乘上的值 $V_i$。
设在当前情况下第 $i$ 号操作会执行 $C_i$ 次，若 $i$ 号操作之后还有操作需要执行时，$C_i$ 将会乘上该操作之后所有操作的 $\prod V_j$。当其后面没有操作(即没有入度)，就可以对其进行更新并且将其删除。故对整张图进行拓扑排序，顺着拓扑序进行处理即可。
还有一个值得提到的细节就是若出现无用操作，则我们需要直接将其忽略，否则其产生的度数将对拓扑序产生影响。
剩下的细节详见代码。
Code[Accepted]
写的是真的丑……但感觉思路还是比较清晰的。
|
