求助求助求助

60分, 第9个点和16 WA

10-11, 17-20 MLE

#include <bits/stdc++.h>
#define mod 998244353
#define int long long
#define maxn 400005
using namespace std;
int n, m, mps[maxn], k;
int cl[maxn][15], flag[maxn], s[maxn << 3], cnt, ansn[maxn << 2], tag1[maxn << 2], tag2[maxn << 2];
void call(int x) {
    if(flag[x] == 1) {
        s[++cnt] = x;
        return;
    }
    else if(flag[x] == 2) {
        s[++cnt] = x;
        return;
    }
    else {
        for(int j = 1;j <= cl[x][0];j++) call(cl[x][j]);
    }
}
int ls(int p) {
    return p << 1;
}
int rs(int p) {
    return p << 1 | 1;
}
void pushup(int p) {
    ansn[p] = (ansn[ls(p)] + ansn[rs(p)]) % mod;
}
void build(int p, int l, int r) {
    int mid = (l + r) >> 1;
    if(l == r) {
        ansn[p] = mps[l];
        return;
    }
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    pushup(p);
}
void f(int p, int l, int r, int k) {
    ansn[p] *= k;
    ansn[p] %= mod;
    tag1[p] *= k;
    tag1[p] %= mod;
    tag2[p] *= k;
    tag2[p] %= mod;
}
void fx(int p, int l, int r, int k) {
    ansn[p] += k * (r - l + 1);
    ansn[p] %= mod;
    tag2[p] += k;
    tag2[p] %= mod;
}
void pushdown(int p, int l, int r) {
    int mid = (l + r) >> 1;
    if(tag1[p] != 1) {
        f(ls(p), l, mid, tag1[p]);
        f(rs(p), mid + 1, r, tag1[p]);
        tag1[p] = 1;
    }
    if(tag2[p]) {
        fx(ls(p), l, mid, tag2[p]);
        fx(rs(p), mid + 1, r, tag2[p]);
        tag2[p] = 0;
    }

}
void update(int p, int l, int r, int nl, int nr, int k) {
    if(nl <= l && r <= nr) {
        ansn[p] *= k;
        ansn[p] %= mod;
        tag1[p] *= k;
        tag1[p] %= mod;
        tag2[p] *= k;
        tag2[p] %= mod;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(p, l, r);
    if(nl <= mid) update(ls(p), l, mid, nl, nr, k);
    if(nr > mid) update(rs(p), mid + 1, r, nl, nr, k);
    pushup(p);
}
void update2(int p, int l, int r, int nl, int nr, int k) {
//  cout << p << " " << l << " " << r << " " << nl << " " << nr << " " << k << endl; 
    if(l == r) {
        ansn[p] += k;
        ansn[p] %= mod;
//      cout << p << " " << k << endl;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(p, l, r);
    if(nl <= mid) update2(ls(p), l, mid, nl, nr, k);
    else update2(rs(p), mid + 1, r, nl, nr, k);
    pushup(p);
}
int query(int nl, int nr, int l, int r, int p) {
    int mid = (l + r) >> 1, res = 0;
    if(l == r) return ansn[p];
    pushdown(p, l, r);
    if(nl <= mid) res += query(nl, nr, l, mid, ls(p)), res %= mod;
    else res += query(nl, nr, mid + 1, r, rs(p)), res %= mod;
    return res % mod;
}
signed main() {
    scanf("%lld", &n);
    for(int i = 1;i <= n;i++) {
        scanf("%lld", &mps[i]);
        mps[i] %= mod;
    }
    for(int i = 1;i <= (n << 2);i++) tag1[i] = 1;
    build(1, 1, n);
    scanf("%lld", &m);
    for(int i = 1;i <= m;i++) {
        int op, x, y, z;
        scanf("%lld%lld", &op, &x);
        if(op == 3) {
            flag[i] = 3;
            for(int j = 1;j <= x;j++) {
                int p;
                scanf("%lld", &p);
                cl[i][++cl[i][0]] = p;
            }
        }
        else if(op == 1){
            flag[i] = 1;
            scanf("%lld", &y);
            cl[i][0] = x;
            cl[i][1] = y; 
        }
        else {
            flag[i] = 2;
            cl[i][0] = x;
        }
    }
    scanf("%lld", &k);
    for(int i = 1;i <= k;i++) {
        int x;
        scanf("%lld", &x);
        call(x);
    }
    int op = 1;
    for(int i = 1;i <= cnt;i++) {
//      cout << s[i] << endl;
        if(flag[s[i]] == 2) op *= cl[s[i]][0], op %= mod;
        else if(flag[s[i]] == 1) {
            if(op != 1) {
                update(1, 1, n, 1, n, op % mod);
                op = 1;
            }
            update2(1, 1, n, cl[s[i]][0], cl[s[i]][0], cl[s[i]][1]);
        }
    }
    if(op != 1) update(1, 1, n, 1, n, op % mod);
    for(int i = 1;i <= n;i++) cout << query(i, i, 1, n, 1) % mod << " ";
}