P7077 [CSP-S 2020] 函数调用

理清题意

题目描述

某数据库应用程序提供了若干函数用以维护数据。已知这些函数的功能可分为三类：

1. 将数据中的指定元素加上一个值；
2. 将数据中的每一个元素乘以一个相同值；
3. 依次执行若干次函数调用，保证不会出现递归（即不会直接或间接地调用本身）。

在使用该数据库应用时，用户可一次性输入要调用的函数序列（一个函数可能被调用多次），在依次执行完序列中的函数后，系统中的数据被加以更新。请你根据这些信息帮他计算出更新后的数据应该是多少。

输入格式

第一行一个正整数 $n$，表示数据的个数。
第二行 $n$ 个整数，第 $i$ 个整数表示下标为 $i$ 的数据的初始值为 $a_i$。
第三行一个正整数 $m$，表示数据库应用程序提供的函数个数。函数从 $1 \sim m$ 编号。
接下来 $m$ 行中，第 $j$（$1 \le j \le m$）行的第一个整数为 $T_j$，表示 $j$ 号函数的类型：

1. 若 $T_j = 1$，接下来两个整数 $P_j, V_j$ 分别表示要执行加法的元素的下标及其增加的值；
2. 若 $T_j = 2$，接下来一个整数 $V_j$ 表示所有元素所乘的值；
3. 若 $T_j = 3$，接下来一个正整数 $C_j$ 表示 $j$ 号函数要调用的函数个数，
   随后 $C_j$ 个整数 $g^{(j)}_1, g^{(j)}_2, \ldots , g^{(j)}_{C_j}$ 依次表示其所调用的函数的编号。

第 $m + 4$ 行一个正整数 $Q$，表示输入的函数操作序列长度。
第 $m + 5$ 行 $Q$ 个整数 $f_i$，第 $i$ 个整数表示第 $i$ 个执行的函数的编号。

输出格式

一行 $n$ 个用空格隔开的整数，按照下标 $1 \sim n$ 的顺序，分别输出在执行完输入的函数序列后，数据库中每一个元素的值。答案对 $\boldsymbol{998244353}$ 取模。

说明/提示

【数据范围】

测试点编号	$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$	无

对于所有数据：$0 \le a_i \le 10^4$，$T_j \in \{1,2,3\}$，$1 \le P_j \le n$，$0 \le V_j \le 10^4$，$1 \le g^{(j)}_k \le m$，$1 \le f_i \le m$。

HINTS

HINT 1

指定元素加上一个值
每一个元素乘以一个相同值

发现是数列上操作，首先想到线段树。

HINT 2

在依次执行完序列中的函数后，系统中的数据被加以更新

最后更新数据。可能需要离线后处理。重点考虑离线算法。

HINT 3

函数调用关系构成一棵树

提示已经非常明显了，我们把整个操作放到树上。

更进一步的，甚至是图上。

HINT 4

不含第 $2$ 类函数或不含第 $1$ 类函数

这提示我们将两种函数分开思考，这也是一种常用的思考方式。

1. 不含全局乘函数
   此时仅剩 单点加函数 和 调用函数
   受 HINT 3 启发，我们把函数调用抽象成一个 DAG （题目中特别指出了没有递归，说明调用图中不可能存在环）。
   于是我们很容易想到在 DAG 上跑 dp（先进行topo排序，这自然不必多言）。
   受 HINT 2 启发，我们可以使用一个数组记录每个 单点加函数 会运行多少次。为了与图上dp相融合，可以将定义拓广为每个 函数 会运行多少次。这样我们可以在操作结束后，遍历每一个单点加函数。

2. 不含单点加函数
   此时仅剩 全局乘函数 和 调用函数。
   因为乘法满足交换律与结合律，且所有操作均可视为对整个数组的乘法贡献。
   同样基于 DAG 拓扑排序：

   1. 首先处理出每个函数自身的全局乘法贡献 $mul[u]$：
      • 若 $u$ 是第 $2$ 类函数，$mul[u] = V_u$；
      • 若 $u$ 是第 $3$ 类函数，$mul[u] = \prod_{v \in \text{son}(u)} mul[v]$。
   2. 按照调用序列的顺序，将对应函数的 $mul$ 值累乘到总乘积上。
   3. 最后对数组所有元素乘以该总乘积即可。

综合分析

下面主要分析同时存在单点加函数与全局乘函数时的情况。

受 HINT 4 启发，我们将两类函数的影响分开计算。
核心矛盾在于：加法执行次数的权重会受到后续乘法的影响。

具体设计如下：

1. 第一步：预处理每个函数的乘法贡献 $mul[u]$
   这一步与情形 2 完全一致。对 DAG 做一次正向拓扑排序，计算出每个函数对全局乘法的净贡献。

2. 第二步：计算每个函数被调用的“等效次数” $cnt[u]$
   注意到，一个加法函数（第 $1$ 类）执行一次，并不意味着它只对答案贡献 $V_u$；如果它后面跟了一个 $\times k$ 的乘法函数，那么它的实际贡献其实是 $V_u \times k$。

   我们可以定义 $cnt[u]$ 为：函数 $u$ 的执行次数，乘上了它之后所有乘法操作的累积。

   计算过程采用 逆序拓扑排序（即按照调用图的反向边进行拓扑）：

   1. 初始化：对于最外层调用序列 $f_i$（注意：序列可能包含多次调用，且顺序敏感），我们需要从后往前遍历序列：

      • 维护一个变量 $prod$，记录从后往前累积的乘法倍数。
      • 对于序列中的第 $i$ 个函数 $f_i$：
        • $cnt[f_i] \leftarrow cnt[f_i] + prod$
        • $prod \leftarrow prod \times mul[f_i]$
          （这体现了：先执行的函数会被后执行的乘法放大。）

   2. 在 DAG 上逆序遍历（即对反向图拓扑排序）：

      • 对于当前节点 $u$，它目前的 $cnt[u]$ 已经包含了外部序列给予它的“带权重执行次数”。
      • 我们需要将这个次数按照调用顺序逆序分配给它的子调用 $g^{(u)}_k$。
      • 具体来说，遍历 $u$ 的子调用序列 $g^{(u)}_{C_u} \dots g^{(u)}_1$（注意是倒序遍历）：
        维护变量 $w = 1$（表示当前子调用之后的兄弟调用带来的乘法积）。
        • 子节点 $v = g^{(u)}_k$ 获得的额外次数为：$cnt[u] \times w$ 注意：同一函数可能被调用多次
        • $cnt[v] \leftarrow cnt[v] + cnt[u] \times w$
        • 更新 $w \leftarrow w \times mul[v]$
      • 同一个函数内，先被调用的子函数会被后调用的子函数带来的乘法放大。

3. 第三步：应用结果

   1. 对于初始数组 $a_i$，全局乘法贡献为：$\text{GlobalMul} = \prod_{i=1}^{Q} mul[f_i]$。
   2. 对于每个单点加函数 $j$（假设其参数为 $P_j, V_j$）：
      其最终带来的总增加量为：$cnt[j] \times V_j$。
      将 $a[P_j]$ 增加该值即可。

   算法复杂度为 $O(n + m + \sum C_j)$，完全符合 $10^5$ 数据范围要求。

AC Code

实现细节：

1. 创建一个主函数，注意初始化主函数的相关数组。
2. 注意取模
3. 代码中使用了一个模板函数对topo序列进行翻转，实际无需。

   template<typename T>
   T reverse(const T& c){return T(std::rbegin(c), std::rend(c));}//使用反向迭代器
   

   但使用反向迭代器初始化数组是一种常用的技巧，写起来较为简便。（虽然可能会增加一些常数时间开销）

Review

1. 通过特殊性质和题目描述调整思考方向
2. 处理多种条件时，可以先分别分析，后综合考量