考虑如果没有3操作,只是顺序执行一些单点加和全局乘操作,我们就可以从后往前扫一遍这些操作,记录一个全局变量$mult=1$,表示目前$mul$操作的后缀积。那么当前的$add$操作就会造成$mult$倍的效果。
所以我们考虑记录一个$f_i$表示每个单点加操作的贡献的倍数。
记录一个辅助数组$mul_i$表示每个3操作里的$mul$操作的积。通过dfs就可以统计。这一步的时间复杂度是$O(\sum c_j)$的。
接着就在要执行的函数序列上从后向前扫,就像开头一样的操作,计算出每个1操作和3操作里的单点修改的贡献的倍数。只有这里面的1操作才可能有$f_i$。
接着就进行拓扑排序,在拓扑排序的过程中进行计算,如果遇到了一个1操作就可以直接计算答案,否则就把三操作继续拓扑排序即可。
#include<bits/stdc++.h>
#define debug system("pause")
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e5+10;
const int mod=998244353;
int n,m;
int a[N],vis[N],deg[N],mul[N],add[N];
int pos[N],val[N],f[N],op[N],fc[N];
vector<int> g[N];
queue<int> q;
void dfs(int u){
vis[u]=1;
mul[u]=op[u]==2?val[u]:1;
for(int i=0,e=g[u].size();i<e;i++){
int v=g[u][i];
if(!vis[v])dfs(v);
(mul[u]*=mul[v])%=mod;
}
}
int mult=1;
signed main(){
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
m=read();
for(int i=1;i<=m;i++){
op[i]=read();
if(op[i]==1)pos[i]=read(),val[i]=read();
if(op[i]==2)val[i]=read();
if(op[i]==3){
int t=read();
while(t--){
int v=read();
g[i].push_back(v);
deg[v]++;
}
}
}
for(int i=1;i<=m;i++){
if(!vis[i]&&!deg[i])dfs(i);
}
int cnt=read();
for(int i=1;i<=cnt;i++)fc[i]=read();
for(int i=cnt;i>=1;i--){
int k=fc[i];
if(op[k]==1)(f[k]+=mult)%=mod;
if(op[k]==2)(mult*=val[k])%=mod;
if(op[k]==3)(f[k]+=mult)%=mod,(mult*=mul[k])%=mod;
}
for(int i=1;i<=m;i++){
if(!deg[i])q.push(i);
}
while(!q.empty()){
int i=q.front();
q.pop();
if(op[i]==1)(add[pos[i]]+=f[i]*val[i])%=mod;
int k=f[i];
for(int j=g[i].size()-1;j>=0;j--){
int v=g[i][j];
if(!(--deg[v]))q.push(v);
(f[v]+=k)%=mod;
(k*=mul[v])%=mod;
}
}
for(int i=1;i<=n;i++)
printf("%d ",(a[i]*mult+add[i])%mod);
return 0;
}