题解 P7077 【函数调用（洛谷民间数据）】

Alex_Wei · 2020-11-11 18:44:57 · 题解

upd on 2020.11.17：补充说明。

题目传送门。

不妨将题目看成：将所有数乘上 mult，再给某些数加上 add_i，其中 mult 是所有被调用的 type II 函数给所有数乘的 V_j 之积。

不难发现函数的调用关系是 DAG，建完图后可以一遍 dfs 求出 mul_i 表示第 i 个函数调用后会将所有数乘上 mul_i。

现在只要求出 add_i 即可：

想一下，如果一个 type I 函数被调用之后，所有数又乘上了 mult，那么就相当于该函数产生了 mult 倍的贡献，这启发我们用数组 f_i 表示第 i 个函数对它所调用的单点加法产生了 f_i 倍的贡献。

可以先把每个函数在一开始调用时的产生的贡献求出，对于 type III 函数，不进行下传递归，最后再用拓扑排序更新真正的 f_i。

一开始的贡献可以倒序处理所有函数调用：

• 如果调用 I 类函数，那么 f_i\gets f_i+mult。
• 如果调用 II 类函数，那么 mult\gets mult\times V_i。
• 如果调用 III 类函数，那么 f_i\gets f_i+mult，mult\gets mult\times mul_i。

为什么要倒序处理：一开始计算的贡献 f_i 是在调用该函数后所有数被乘了 f_i，因此需要倒序处理。

最后拓扑排序时，对于每个函数：

• 如果是 I 类函数，那么 add_{P_i}\gets add_{P_i}+f_i\times V_i。

• 如果是 III 类函数，那么从后往前处理所有调用的函数（原因同上）：

  对于每个被调用的函数 j，f_j\gets f_j+f_i。

  此时 j 被调用前一个调用的函数 pre 相当于产生了 f_i\times mul_j 倍的贡献，因为调用 pre 后调用 j 将所有数乘上了 mul_j，也就是说调用 pre 产生的单点加法贡献被放大了 mul_j 倍，此时我们将 f_i\gets f_i\times mul_j。

  但是这样会导致原来的 f_i 被覆盖，那么用一个变量代替 f_i 即可。

最后每个数输出 a_i\times mult+add_i 即可。

感觉可以通过差分做到线性时间区间修改，要是我就加强了（

时间，空间复杂度 O(n+m)。读入量较大，建议使用快读。

拿样例 1 举个例子：

不难求出 mul=\{1,2,2\}。此时 mult=1。

调用的函数分别为 2,3，那么我们倒序处理调用：

首先是 3，f_3\gets f_3+mult=1，mult\gets mult\times mul_3=2。

然后是 2，mult\gets mult\times mul_2=4。

此时 mult=4，f=\{0,0,1\}，度数 deg=\{1,1,0\}。

接下来拓扑排序，因为 3 的入度为 0 所以首先被压入队列。

• 对于队首函数 3，倒序处理所有其调用的函数：

  设变量 z\gets f_3=1。

  • 首先是 2：
  $f_2\gets f_2+z=1$（没有必要）。 $z\gets z\times mul_2=2$。 - 然后是 $1$： $deg_1=\gets deg_1-1=0$，入度为 $0$ 被压入队列。 $f_1\gets f_1+z=2$。 $z\gets z\times mul_1=2$（没有必要）。

• 对于队首函数 2，不做任何操作。

• 对于队首函数 1，add_{pos_1}\gets add_{pos_1}+f_1\times V_1=0+2\times 1=2。

最后分别输出：