P7077

Aryper · 2021-11-10 00:09:58 · 个人记录

[CSP-S2020] 函数调用

实证线段树暴力可以拿到理论 30pts，实际 70pts 的好成绩，在赛场上可以说是性价比最高的选择了。

正解非常的扯拐，让人觉得和模拟无甚区别。

首先将答案表示为 ba_i+k_i，其中 b 表示倍数（即操作 2 对此的影响），k_i 表示加数（即操作 1 对此的影响）。

然后着手考虑一下这个调用过程，如果边调用边进行更改意味着要面对单次修改可能出现的庞大复杂度，所以显然不能直接修改，因而我们采取标记的策略，并且尽可能的消除调用顺序的影响。

用数组 f_i 表示第 i 个函数被调用的次数。

首先预处理出单次调用每个函数对区间整体的所乘系数的影响，这个可以用记忆化搜索实现，时间复杂度线性。

然后我们可以离线询问，倒序访问查询（需要尝试消除调用顺序带来的影响），可见这样的话，我们的加法的系数需要乘上当前所存在的乘法系数（如果顺序则需要处理逆元）。然后考虑对每个函数 O(1) 标记。

对于所有操作，我们的先将 b（累积下来的乘系数）乘上 mul_i（单次调用的乘系数影响，对于操作 1，有 mul_i=1；对于操作 3，有 mul_i=\prod_{j\in g_i} mul_j）。然后我们想办法利用调用次数做标记。

对于操作 1，首先加数一定要乘上系数 b，但此时我们看作进行了 b 次操作 1，所以可以直接令 f(i)=f(i)+b。

对于操作 2，操作次数并不重要，因为除了对 b 产生影响它也没有别的功效了，所以我们可以直接略过 f(i) 的处理。

对于操作 3，同样操作次数 f(i)=f(i)+b。

那么怎么用现在的条件处理出每个元素的 k_i 呢？

我们可以尝试直接在函数调用的 DAG 中做拓扑序处理。

对于操作 1，显然其对其对应的元素的 k_{p_i} 影响为 k_{p_i}=k_{p_i}+f(i)v_i。

对于操作 2，对加法没有影响。

对于操作 3，倒序遍历其下的每一个操作，并且对每一个子操作的操作次数都要加上 f(i)，自身也被子操作所影响，有 f(i)=f(i)mul_j。

然后就线性完成了本题。

时间复杂度 O(n+m+Q)。

代码：

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;

const ll N=1e5,mo=998244353;

ll n,m,Q,b;

ll a[N+5],v[N+5],p[N+5],type[N+5],c[N+5];

ll mul[N+5],f[N+5],q[N+5],deg[N+5],k[N+5];

vector<ll> g[N+5];

ll calc(ll x) {
    if(mul[x]!=-1) return mul[x];
    if(type[x]==1) {
        mul[x]=1;
    }
    if(type[x]==2) {
        mul[x]=v[x];
    }
    if(type[x]==3) {
        mul[x]=1;
        for(ll i=0;i<c[x];i++) {
            mul[x]=calc(g[x][i])*mul[x]%mo;
        }
    }
    return mul[x];
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        a[i]=read();
    }

    m=read();

    for(ll i=1;i<=m;i++) {
        type[i]=read();
        if(type[i]==1) {
            p[i]=read();v[i]=read();
        }
        if(type[i]==2) {
            v[i]=read();
        }
        if(type[i]==3) {
            c[i]=read();
            for(ll j=1;j<=c[i];j++) {
                ll x=read();
                g[i].push_back(x);
            }
        }
    }

    memset(mul,-1,sizeof(mul));
    for(ll i=1;i<=m;i++) {
        if(mul[i]==-1) calc(i);
    }

    Q=read();

    for(ll i=1;i<=Q;i++) {
        q[i]=read();
    }

    b=1;
    for(ll i=Q;i>=1;i--) {
        if(type[q[i]]==1) {
            f[q[i]]=(f[q[i]]+b)%mo;
        }
        if(type[q[i]]==2) {
            b=(b*v[q[i]])%mo;
        }
        if(type[q[i]]==3) {
            f[q[i]]=(f[q[i]]+b)%mo;
            b=(b*mul[q[i]])%mo;
        }
    }

    for(ll i=1;i<=m;i++) {
        if(type[i]!=3) continue;
        for(ll j=0;j<c[i];j++) {
            deg[g[i][j]]++;
        }
    }
    queue<ll> q;
    for(ll i=1;i<=m;i++) {
        if(deg[i]==0) q.push(i);
    }

    while(!q.empty()) {
        ll h=q.front();q.pop();
        if(type[h]==1) {
            k[p[h]]=(k[p[h]]+f[h]*v[h])%mo;
        }
        if(type[h]==3) {
            for(ll i=c[h]-1;i>=0;i--) {
                if(--deg[g[h][i]]==0) q.push(g[h][i]);
                f[g[h][i]]=(f[g[h][i]]+f[h])%mo;
                f[h]=(f[h]*mul[g[h][i]])%mo;
            }
        }
    }

    for(ll i=1;i<=n;i++) {
        write((a[i]*b%mo+k[i])%mo);putchar(' ');
    }

    return 0;
}