Submission #68159465

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
static const int MOD = 998244353;

int mod_pow(long long a, long long e = MOD-2) {
    long long r = 1 % MOD;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return (int)r;
}

struct SegTree {
    struct Node {
        int sum;
        int assign;
    };
    int n;
    vector<Node> st;
    
    SegTree(int _n, vector<int>& A) : n(_n) {
        st.assign(4*n, {0, -1});
        build(1,1,n,A);
    }
    
    void build(int p, int l, int r, vector<int>& A) {
        if (l == r) {
            st[p].sum = A[l] % MOD;
        } else {
            int m = (l + r) >> 1;
            build(p<<1, l, m, A);
            build(p<<1|1, m+1, r, A);
            st[p].sum = (st[p<<1].sum + st[p<<1|1].sum) % MOD;
        }
    }
    
    void apply_assign(int p, int l, int r, int v) {
        st[p].sum    = (long long)v * (r - l + 1) % MOD;
        st[p].assign = v;
    }
    
    void push(int p, int l, int r) {
        if (st[p].assign >= 0 && l < r) {
            int m = (l + r) >> 1;
            apply_assign(p<<1,   l,   m, st[p].assign);
            apply_assign(p<<1|1, m+1, r, st[p].assign);
            st[p].assign = -1;
        }
    }
    
    void update_assign(int p, int l, int r, int L, int R, int v) {
        if (R < l || r < L) return;
        if (L <= l && r <= R) {
            apply_assign(p, l, r, v);
            return;
        }
        push(p,l,r);
        int m = (l + r) >> 1;
        update_assign(p<<1,   l,   m, L, R, v);
        update_assign(p<<1|1, m+1, r, L, R, v);
        st[p].sum = (st[p<<1].sum + st[p<<1|1].sum) % MOD;
    }
    
    int query_sum(int p, int l, int r, int L, int R) {
        if (R < l || r < L) return 0;
        if (L <= l && r <= R) return st[p].sum;
        push(p,l,r);
        int m = (l + r) >> 1;
        int s1 = query_sum(p<<1,   l,   m, L, R);
        int s2 = query_sum(p<<1|1, m+1, r, L, R);
        return (s1 + s2) % MOD;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    cin >> N >> M;
    vector<int> A(N+1);
    for(int i = 1; i <= N; i++){
        cin >> A[i];
        A[i] %= MOD;
    }
    
    SegTree st(N, A);
    
    while (M--) {
        int L, R;
        cin >> L >> R;
        int len = R - L + 1;
        int S   = st.query_sum(1,1,N,L,R);
        int avg = (long long)S * mod_pow(len) % MOD;
        st.update_assign(1,1,N,L,R,avg);
    }
    for(int i = 1; i <= N; i++){
        int v = st.query_sum(1,1,N,i,i);
        cout << v << (i==N?'\n':' ');
    }
    return 0;
}

Submission Info

Judge Result