提出 #48476989

---

ソースコード 拡げる

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 998244353;

struct segTree{
    vector<ll> val, cnt, mult, sum;
    int size;

    void build(int x, int lx, int rx, vector<int>& a){
        if(rx - lx == 1){
            if(lx < (int)a.size()){
                cnt[x] = 1;
                val[x] = a[lx];
            }
            return;
        }
        int m = (lx + rx) / 2;
        build(2 * x + 1, lx, m, a);
        build(2 * x + 2, m, rx, a);
        cnt[x] = cnt[2 * x + 1] + cnt[2 * x + 2];
        val[x] = val[2 * x + 1] + val[2 * x + 2];
    }

    void init(vector<int>& a){
        int n = (int)a.size();
        size = 1;
        while(size < n) size *= 2;
        val.assign(2 * size, 0);
        cnt.assign(2 * size, 0);
        mult.assign(2 * size, 1);
        sum.assign(2 * size, 0);
        build(0, 0, size, a);
    }

    void push(int x){
        if(2 * x + 2 >= (int)val.size()) return;
        val[2 * x + 1] *= mult[x]; val[2 * x + 1] += sum[x] * cnt[2 * x + 1]; val[2 * x + 1] %= MOD;
        val[2 * x + 2] *= mult[x]; val[2 * x + 2] += sum[x] * cnt[2 * x + 2]; val[2 * x + 2] %= MOD;
        mult[2 * x + 1] *= mult[x]; mult[2 * x + 1] %= MOD; sum[2 * x + 1] *= mult[x]; sum[2 * x + 1] += sum[x]; sum[2 * x + 1] %= MOD;
        mult[2 * x + 2] *= mult[x]; mult[2 * x + 2] %= MOD; sum[2 * x + 2] *= mult[x]; sum[2 * x + 2] += sum[x]; sum[2 * x + 2] %= MOD;
        mult[x] = 1;
        sum[x] = 0;
    }

    void set(int l, int r, ll u, int type, int x, int lx, int rx){
        if(lx >= l && rx <= r){
            if(type == 1) {val[x] *= u; mult[x] *= u; sum[x] *= u;}
            else {val[x] += u * (rx - lx); sum[x] += u;}
            val[x] %= MOD; mult[x] %= MOD; sum[x] %= MOD;
            return;
        }else if(lx >= r || rx <= l) return;
        int m = (lx + rx) / 2;
        push(x);
        set(l, r, u, type, 2 * x + 1, lx, m);
        set(l, r, u, type, 2 * x + 2, m, rx);
        val[x] = val[2 * x + 1] + val[2 * x + 2];
        val[x] %= MOD;
    }

    void set(int l, int r, ll u, int type){ //Type = 1, multiplication. Type = 2, sum.
        set(l, r, u, type, 0, 0, size);
    }

    ll query(int l, int r, int x, int lx, int rx){
        if(lx >= l && rx <= r) return val[x];
        else if(lx >= r || rx <= l) return 0;
        int m = (lx + rx) / 2;
        push(x);
        ll s1 = query(l, r, 2 * x + 1, lx, m);
        ll s2 = query(l, r, 2 * x + 2, m, rx);
        return (s1 + s2) % MOD;
    }

    ll query(int l, int r){
        return query(l, r, 0, 0, size);
    }
};

ll binpow(ll a, ll b, int mod = MOD){
    if(!b) return 1;
    else if(b % 2 == 0){
        ll x = binpow(a, b / 2, mod);
        return (x * x) % mod;
    }else{
        ll x = binpow(a, b / 2, mod);
        return (((x * x) % mod) * a) % mod;
    }
}

ll inv(ll x, ll mod = MOD){
    x %= mod;
    return binpow(x, mod - 2, mod);
}

void solve(){
    int n, q; cin >> n >> q;
    vector<int> a(n);
    for(auto &i : a) cin >> i;
    segTree st; st.init(a);
    while(q--){
        int l, r, X; cin >> l >> r >> X; l--; r--;
        ll size = (r - l + 1);
        st.set(l, r + 1, ((size - 1) * inv(size)) % MOD, 1);
        st.set(l, r + 1, (X * inv(size)) % MOD, 2);
    }
    for(int i = 0; i < n; i++) cout << st.query(i, i + 1) << " ";
    cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    solve();
}

提出情報

ジャッジ結果