题解：P7077 [CSP-S2020] 函数调用

· · 题解

难道有人看题解不点赞的吗？

题目解析

我们发现题目一共有三种操作：单点加，区间乘，调用其他操作。我还以为是线段树……
接下来我们一步一步考虑：

如果没有第三种操作，那我们可以倒序遍历每个操作，维护每个元素加的次数 cnt，和全局乘数 mul。

如果没有第二种操作，那我们就加一个 0 号点，连向每个 f_i，再把每个操作三连边到它调用的函数，发现最终会形成一个 DAG（俗称大哥图）。接下来我们使用拓扑排序，算出每个函数调用的次数 cnt_i。

我们可以发现，其实上述两种情况可以合并，只要算出 mul 和 cnt_i 就能求出答案。

好啦，下面是……

AC 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10,mod=998244353;
queue<ll> q;
vector<ll> e1[N],e2[N];
ll n,m,Q,a[N],t[N],p[N],v[N],in[N],mul[N],cnt[N];
void get_mul() {
    for(ll i=0; i<=m; i++) {
        in[i]=e2[i].size();
        if(!in[i]) q.push(i);
    }
    while(!q.empty()) {
        ll u=q.front();
        q.pop();
        for(ll v:e1[u]) {
            mul[v]=mul[v]*mul[u]%mod;
            in[v]--;
            if(!in[v]) q.push(v);
        }
    }
}
void get_cnt() {
    for(ll i=0; i<=m; i++) {
        in[i]=e1[i].size();
        if(!in[i]) q.push(i);
    }
    while(!q.empty()) {
        ll u=q.front();
        q.pop();
        ll n_mul=1;
        for(ll i=e2[u].size()-1; i>=0; i--) {//注意这里要到序遍历，因为后面的乘操作会影响前面的，但前面的不会影响后面的
            ll v=e2[u][i];
            cnt[v]=(cnt[v]+n_mul*cnt[u])%mod;
            n_mul=n_mul*mul[v]%mod;
            in[v]--;
            if(!in[v]) q.push(v);
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(ll i=1; i<=n; i++) cin>>a[i];
    cin>>m;
    for(ll i=1; i<=m; i++) {
        cin>>t[i];
        mul[i]=1;
        if(t[i]==1) cin>>p[i]>>v[i];
        else if(t[i]==2) cin>>mul[i];
        else {
            ll c,g;
            cin>>c;
            while(c--) {
                cin>>g;
                e1[g].push_back(i);
                e2[i].push_back(g);
            }
        }
    }
    cin>>Q;
    mul[0]=cnt[0]=1;
    while(Q--) {
        ll f;
        cin>>f;
        e1[f].push_back(0);
        e2[0].push_back(f);
    }
    get_mul(),get_cnt();
    for(ll i=1; i<=n; i++) a[i]=a[i]*mul[0]%mod;
    for(ll i=1; i<=m; i++)
        if(t[i]==1) a[p[i]]=(a[p[i]]+cnt[i]*v[i])%mod;
    for(ll i=1; i<=n; i++) cout<<a[i]<<" ";
    return 0;
}

完结撒花~~