函数调用题解 | AlanSP's Blog

Description

给定一个序列和若干种操作，他们分成三类：

将序列中的指定元素加上一个值；
将序列中的每一个元素乘以一个相同值；
依次执行若干次操作，不会出现递归。
给出一个长度为 $q$ 的操作串，询问依次执行完上面的所有操作后，序列中每个元素的值是多少。

Solution

把每个操作和它所执行的操作连单向边，这样就形成了一个 $dag$ 。

在这个 $dag$ 上面，真正使答案变化的是那些出度为 $0$ 的点，其他点只是反复地"调用"它们。

那么不难联想到要处理出每一个点所能产生的贡献。

我们发现，对于乘法操作，越靠后进行它影响的范围就越广，而在它之前的所有操作，都受这个乘法的影响。

这样可以沿拓扑序倒序递推出每个节点的贡献，这里的贡献指进行这个操作，整个序列要乘以多少。

接下来我们再考虑加法操作。

同理，我们可以维护出对于每个操作，它在这个操作串中被加了多少次。

注意：这时我们就要整体考虑了，并且对于 $op\neq 1$ 的那些操作，我们递推不是为了统计答案，而是要得到后面状态的值。

很显然，我们要顺着拓扑序去更新。

此时也要把乘法标记下放，最后先乘再加，以防搞混。

Code

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e5+9,mod=998244353;
vector<int> G[N],g[N];
int n,m,q,mul[N],op[N],add[N],f[N];
int Q[N],hh,tt,a[N],pos[N],in[N];
int Add[N],Mul[N];
inline int read()
{
	int res=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') 
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		res=(res<<3)+(res<<1)+ch-'0',ch=getchar();
	return res*f;
}

inline void rev_toposort()
{
	hh=0,tt=-1;
	for(int i=1;i<=m;i++) if(!in[i]) Q[++tt]=i;
	while(hh<=tt)
	{
		int u=Q[hh++];
		for(int i=0;i<g[u].size();i++)
		{
			int v=g[u][i];
			mul[v]=1ll*mul[u]*mul[v]%mod;
			if(--in[v]==0) Q[++tt]=v;
		}
	}
}

inline void toposort()
{
	memset(in,0,sizeof in);
	for(int i=1;i<=m;i++)
		for(int j=0;j<G[i].size();j++)
			in[G[i][j]]++;
	hh=0,tt=-1;
	for(int i=1;i<=m;i++) if(!in[i]) Q[++tt]=i;
	while(hh<=tt)
	{
		int u=Q[hh++];
		for(int i=G[u].size()-1;i>=0;i--)
		{
			int v=G[u][i];
			Add[v]=(Add[v]+Add[u])%mod;
			Add[u]=1ll*Add[u]*mul[v]%mod;
			if(--in[v]==0) Q[++tt]=v;	
		}
	}
}

int main()
{
	// freopen("call.in","r",stdin);
	// freopen("call.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	m=read();
	for(int i=1;i<N;i++) mul[i]=1;
	for(int i=1;i<=m;i++)
	{
		op[i]=read();
		if(op[i]==1) pos[i]=read(),add[i]=read();
		if(op[i]==2) mul[i]=read();
		if(op[i]==3)
		{
			int cnt;cnt=read();
			while(cnt--)
			{
				int x;x=read();
				g[x].push_back(i);in[i]++;
				G[i].push_back(x);
			}
		}
	}
	rev_toposort();
	q=read();
	for(int i=1;i<=q;i++) f[i]=read();Mul[q+1]=1;
	for(int i=q;i>=1;i--)
	{
		Mul[i]=1ll*Mul[i+1]*mul[f[i]]%mod;
		Add[f[i]]=(Add[f[i]]+Mul[i+1])%mod;
	}
	for(int i=1;i<=n;i++) a[i]=1ll*a[i]*Mul[1]%mod;
	toposort();
	for(int i=1;i<=m;i++)
		if(op[i]==1) a[pos[i]]=(a[pos[i]]+1ll*add[i]*Add[i]%mod)%mod;//printf("%d %d\n",pos[i],Add[i]);
	for(int i=1;i<=n;i++)
		printf("%d ",a[i]);
	return 0;
}