题解 P7077 【函数调用（洛谷民间数据）】
Alex_Wei
2020-11-11 18:44:57
upd on 2020.11.17：补充说明。
[题目传送门](https://www.luogu.com.cn/problem/P7077)。
不妨将题目看成：将所有数乘上 $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$：
$deg_2\gets deg_2-1=0$，入度为 $0$ 被压入队列。
$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$。
最后分别输出：
$a_1\times mult+add_1=1\times 4+2=6$；
$a_2\times mult+add_2=2\times 4+0=8$；
$a_3\times mult+add_3=3\times 4+0=12$。
---
非考场代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
ll x=0,sign=0; char s=getchar();
while(s>'9'||s<'0')sign|=s=='-',s=getchar();
while(s<='9'&&s>='0')x=(x<<1)+(x<<3)+s-'0',s=getchar();
return sign?-x:x;
}
const int N=1e5+5;
const int mod=998244353;
int n,m,c,a[N],deg[N],func[N];
int tp[N],pos[N],val[N];
ll mu=1,mul[N],dp[N],add[N];
vector <int> e[N];
queue <int> q;
bool vis[N];
void dfs(int id){
vis[id]=1,mul[id]=(tp[id]==2?val[id]:1);
for(int it:e[id]){
if(!vis[it])dfs(it);
mul[id]=mul[id]*mul[it]%mod;
}
}
int main(){
n=read(); for(int i=1;i<=n;i++)a[i]=read();
m=read();
for(int i=1;i<=m;i++){
tp[i]=read();
if(tp[i]==1)pos[i]=read(),val[i]=read();
else if(tp[i]==2)val[i]=read();
else{
c=read();
while(c--){
int to=read();
e[i].push_back(to),deg[to]++;
}
}
} c=read();
for(int i=1;i<=m;i++)if(!vis[i]&&!deg[i])dfs(i);
for(int i=1;i<=c;i++)func[i]=read();
for(int i=c,f=func[i];i;i--,f=func[i]){
if(tp[f]==1)dp[f]=(dp[f]+mu);
else if(tp[f]==2)mu=mu*val[f]%mod;
else dp[f]=(dp[f]+mu),mu=mu*mul[f]%mod;
} for(int i=1;i<=m;i++)if(!deg[i])q.push(i);
while(!q.empty()){
int t=q.front(); q.pop();
if(tp[t]==1)add[pos[t]]=(add[pos[t]]+dp[t]*val[t])%mod;
ll z=dp[t]; reverse(e[t].begin(),e[t].end());
for(int p:e[t]){
deg[p]--; if(!deg[p])q.push(p);
dp[p]=(dp[p]+z)%mod,z=z*mul[p]%mod;
}
} for(int i=1;i<=n;i++)cout<<(a[i]*mu+add[i])%mod<<" ";
return 0;
}
```