考虑如果没有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;
}
最后修改:2020 年 11 月 17 日 01 : 40 PM