题目
点这里看题目。
分析
考场上觉得很难，考完发现 T4 才是最难的。
显然有：每个位置的值最终一定是一次函数形式：(f_i(x)=kx+b_i) 。我们可以直接算出 (k) ，那么我们只需要想办法求出 (b_i) 。
对于一个加法函数而言，每次加的值是固定的，因此我们只需要计算这个值之前的一个系数。
对于加法函数 (u) ，我们设它的系数为 (p_u) 。那么 (p_u) 即为所有在 (u) 之后调用的乘法函数之积。
一个函数 (u) 可能会被多次调用，只需要将每次调用的系数求和即可。我们只需要考虑单次调用的情况。
在单次被调用中，我们考虑该次操作直接调用的函数 (f) 。那么 (p_u) 可以拆分成两部分：调用 (f) 的时候调用的，且在 (u) 之后被执行的乘法函数的积和在 (f) 之后被操作调用的导致的积。
后一个部分很好处理，我们可以直接计算操作的后缀积。然后发现，其实前一个部分也比较简单。我们只需要将原先的调用顺序倒过来处理，同时维护当前节点的计算次数即可。
时间复杂度就是线性的。
小结：
- 答案的一次函数形式，将问题缩小到了加法上面。
- 利用 (p) 与时间相关的特性，将它与后缀积挂钩；同时将后缀拆分成两个部分。可以发现这就是不断缩减问题范围的过程。
代码
#include <cstdio>
#include <vector>
using namespace std;
typedef long long LL;
const int mod = 998244353;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;
template<typename _T>
void read( _T &x )
{
x = 0; char s = getchar(); int f = 1;
while( s < '0' || '9' < s ) { f = 1; if( s == '-' ) f = -1; s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) write( x / 10 );
putchar( x % 10 + '0' );
}
vector<int> que[MAXN], Graph[MAXN];
int add[MAXN];
int func[MAXN], suf[MAXN];
int q[MAXN];
int T[MAXN], P[MAXN], V[MAXN], mul[MAXN], extra[MAXN];
int into[MAXN];
int a[MAXN];
int N, M, Q, cnt;
int Sub( int x, int v ) { return x < v ? x + mod - v : x - v; }
int Mul( LL x, int v ) { x *= v; if( x >= mod ) x %= mod; return x; }
int Add( int x, int v ) { return x + v >= mod ? x + v - mod : x + v; }
void AddEdge( const int from, const int to )
{
Graph[from].push_back( to ), into[to] ++;
}
void Init()
{
int h = 1, t = 0, u, v;
for( int i = 1 ; i <= M ; i ++ )
if( ! into[i] ) q[++ t] = i;
while( h <= t )
{
u = q[h ++];
for( int i = 0 ; i < ( int ) Graph[u].size() ; i ++ )
if( ! ( -- into[v = Graph[u][i]] ) )
q[++ t] = v;
}
for( int i = M ; i ; i -- )
{
int u = q[i]; mul[u] = 1;
if( T[u] == 2 ) mul[u] = V[u];
if( T[u] == 3 )
for( int k = 0 ; k < ( int ) Graph[u].size() ; k ++ )
mul[u] = Mul( mul[u], mul[Graph[u][k]] );
}
}
int main()
{
read( N );
for( int i = 1 ; i <= N ; i ++ ) read( a[i] );
read( M );
for( int i = 1 ; i <= M ; i ++ )
{
read( T[i] );
if( T[i] == 1 ) read( P[i] ), read( V[i] );
if( T[i] == 2 ) read( V[i] );
if( T[i] == 3 )
{
int C, v; read( C );
while( C -- ) read( v ), AddEdge( i, v );
}
}
Init(), read( Q );
for( int i = 1 ; i <= Q ; i ++ )
read( func[i] ), que[func[i]].push_back( i );
suf[Q + 1] = 1; for( int i = Q ; i ; i -- ) suf[i] = Mul( suf[i + 1], mul[func[i]] );
for( int i = 1, u, v ; i <= M ; i ++ )
{
u = q[i];
for( int k = 0 ; k < ( int ) que[u].size() ; k ++ )
extra[u] = Add( extra[u], suf[que[u][k] + 1] );
if( T[u] == 1 ) add[P[u]] = Add( add[P[u]], Mul( V[u], extra[u] ) );
else if( T[u] == 3 )
for( int k = ( int ) Graph[u].size() - 1 ; ~ k ; k -- )
{
v = Graph[u][k];
extra[v] = Add( extra[v], extra[u] );
extra[u] = Mul( extra[u], mul[v] );
}
}
for( int i = 1 ; i <= N ; i ++ ) write( Add( Mul( suf[1], a[i] ), add[i] ) ), putchar( i == N ? '
' : ' ' );
return 0;
}