CSP-S2020 T3 函数调用
题目描述
函数是各种编程语言中一项重要的概念，借助函数，我们总可以将复杂的任务分解成一个个相对简单的子任务，直到细化为十分简单的基础操作，从而使代码的组织更加严密、更加有条理。然而，过多的函数调用也会导致额外的开销，影响程序的运行效率。
某数据库应用程序提供了若干函数用以维护数据。已知这些函数的功能可分为三类：
- 将数据中的指定元素加上一个值；
- 将数据中的每一个元素乘以一个相同值；
- 依次执行若干次函数调用，保证不会出现递归（即不会直接或间接地调用本身）。
在使用该数据库应用时，用户可一次性输入要调用的函数序列（一个函数可能被调用多次），在依次执行完序列中的函数后，系统中的数据被加以更新。某一天，小 A 在应用该数据库程序处理数据时遇到了困难：由于频繁而低效的函数调用，系统在执行操作时进入了无响应的状态，他只好强制结束了数据库程序。为了计算出正确数据，小 A 查阅了软件的文档，了解到每个函数的具体功能信息，现在他想请你根据这些信息帮他计算出更新后的数据应该是多少。
输入格式
第一行一个正整数 nn，表示数据的个数。
第二行 nn 个整数，第 ii 个整数表示下标为 ii 的数据的初始值为 a_ia**i。
第三行一个正整数 mm，表示数据库应用程序提供的函数个数。函数从 1 sim m1∼m 编号。
接下来 mm 行中，第 jj（1 le j le m1≤j≤m）行的第一个整数为 T_jT**j，表示 jj 号函数的类型：
- 若 T_j = 1T**j=1，接下来两个整数 P_j, V_jP**j,V**j 分别表示要执行加法的元素的下标及其增加的值；
- 若 T_j = 2T**j=2，接下来一个整数 V_jV**j 表示所有元素所乘的值；
- 若 T_j = 3T**j=3，接下来一个正整数 C_jC**j 表示 jj 号函数要调用的函数个数，
随后 C_jC**j 个整数 g^{(j)}_1, g^{(j)}2, ldots , g^{(j)}{C_j}g1(j),g2(j),…,gCj(j) 依次表示其所调用的函数的编号。
第 m + 4m+4 行一个正整数 QQ，表示输入的函数操作序列长度。
第 m + 5m+5 行 QQ 个整数 f_if**i，第 ii 个整数表示第 ii 个执行的函数的编号。
输出格式
一行 nn 个用空格隔开的整数，按照下标 1 sim n1∼n 的顺序，分别输出在执行完输入的函数序列后，数据库中每一个元素的值。答案对 oldsymbol{998244353}998244353 取模。
题解：
考试之前特意总结的图论模型的抽象。甚至还无限接近正解地压了拓扑序上DP。结果来了一道这样的题，还是不会。
太菜了。
考场策略就是个渣渣。本来以为多考了一年能够好一些，结果还是渣渣。甚至还不如第一年去考。
太菜了。
太菜了。
真是太菜了。
题目中有很多地方暗示了要建图来考虑解决这个问题。比如无递归，就暗示了没有环。比如函数调用。调用的过程就是一张图。比如部分分给的调用关系是一棵树。
考场上时间真的不够了。这道题甚至都没有细细思考。就直接上手打了最裸的暴力，连线段树架上去优化都没加。真的没有发挥到自己比其他人优秀的地方，光看代码，给人的感觉就是这个人和普及选手甚至0基础没有任何的区别。
太菜了。
然后中间过程还爆。讲过多少遍，还是忘记了。
太菜了。
真的只是紧张么？
太菜了。
总的来说，这道题是一张DAG。这是很显然的。然后我们发现，不能简单地按拓扑序架数据结构。因为这个两种操作和两种操作各自的顺序就让人很迷茫。
于是考虑加法和乘法之间的转换。可以看出，乘法可以转化成若干次加法。所以对于一次加法，其后面的乘法操作可以转换成加几次来赋给这个加法，作为这个加法的贡献。
也就是，对于一个加法操作，其贡献是后面所有乘法操作的积。
对于整张拓扑图进行DP。统计后缀即。至于同一层的顺序问题，在使用链式前向星存储的时候，就是按顺序存的了，所以自然也会按顺序去遍历。
然后对整张拓扑图DP的时候可以把整张图的遍历顺序用深搜序转成序列问题。这样倒序再来一遍DP。就保证了转移的阶段性，即统计出了所有加法得到的贡献。
所以：
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read()
{
int x=0,gx=1;
char ch=nc();
while(ch<48||ch>57)
if(ch=='-')
gx=-1,ch=nc();
while(ch>=48&&ch<=57)
x=x*10+ch-48,ch=nc();
return x*gx;
}
const int maxn=1e6+5;
const int mod=998244353;
int n,m,q;
int pos[maxn],val[maxn<<1],id[maxn],opt[maxn<<1],cnt;
int tot,head[maxn<<1],nxt[maxn<<1],to[maxn<<1],lazy[maxn<<1];
int gx[maxn],dp[maxn],ans[maxn];
void add(int x,int y)
{
to[++tot]=y;
lazy[tot]=1;
nxt[tot]=head[x];
head[x]=tot;
}
int dfs(int x)
{
if(~gx[x])
return gx[x];
if(opt[x]==1)
gx[x]=1;
else if(opt[x]==2)
gx[x]=val[x];
else
{
gx[x]=1;
for(int i=head[x];i;i=nxt[i])
{
lazy[i]=gx[x];
gx[x]=(gx[x]*1ll*dfs(to[i]))%mod;
}
}
id[++cnt]=x;
return gx[x];
}
signed main()
{
n=read();
opt[0]=3;
for(int i=1;i<=n;i++)
{
add(0,i);
pos[i]=i;
val[i]=read();
opt[i]=1;
}
m=read();
for(int i=n+1;i<=n+m;i++)
{
opt[i]=read();
if(opt[i]==1)
pos[i]=read(),val[i]=read();
else if(opt[i]==2)
val[i]=read();
else
{
int c=read();
while(c--)
{
int x=read();
add(i,x+n);
}
}
}
q=read();
for(int i=1;i<=q;i++)
{
int x=read();
add(0,x+n);
}
memset(gx,-1,sizeof(gx));
dfs(0);
dp[0]=1;
for(int i=cnt;i>=1;i--)
{
int x=id[i];
for(int j=head[x];j;j=nxt[j])
{
int y=to[j];
dp[y]=(dp[y]+dp[x]*1ll*lazy[j])%mod;
}
if(opt[x]==1)
ans[pos[x]]=(ans[pos[x]]+dp[x]*1ll*val[x])%mod;
}
for(int i=1;i<=n;i++)
printf("%lld ",ans[i]);
puts("");
return 0;
}