Submission #48519202

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/lazysegtree>

namespace {
    using ModInt [[maybe_unused]] = atcoder::modint998244353;
    using Num [[maybe_unused]] = long long int;
    using Vec [[maybe_unused]] = std::vector<Num>;
    using Set [[maybe_unused]] = std::set<Num>;
    using Mset [[maybe_unused]] = std::multiset<Num>;
    using Edges [[maybe_unused]] = std::vector<std::vector<Num>>;

    template<typename T>
    using Q [[maybe_unused]] = std::queue<T>;

    template<typename T>
    using PQ [[maybe_unused]] = std::priority_queue<T, std::vector<T>, std::greater<T>>;
}

struct Prob {
    ModInt prob_kept {1};
    ModInt value {0};
};

struct Node {
    Num width {0};
    ModInt average {0};

    Node merge(const Node& rhs) const {
        Num w = width + rhs.width;
        if (w == 0) {
            Node node;
            return node;
        }

        ModInt lsum = average;
        lsum *= width;

        ModInt rsum = rhs.average;
        rsum *= rhs.width;

        ModInt avg = lsum + rsum;
        avg /= w;

        Node result;
        result.width = w;
        result.average = avg;
        return result;
    }

    Node update(const Prob& prob) const {
        Node result;
        result.width = width;

        ModInt v = average;
        v *= prob.prob_kept;
        v += prob.value;
        result.average = v;
        return result;
    }
};

Node func_operate(Node a, Node b) {
    return a.merge(b);
}

Node func_unit() {
    return Node();
}

Node func_map(Prob p, Node node) {
    return node.update(p);
}

Prob func_compose(Prob a, Prob b) {
    ModInt v = b.value;
    v *= a.prob_kept;
    v += a.value;

    Prob p;
    p.prob_kept = a.prob_kept * b.prob_kept;
    p.value = v;
    return p;
}

Prob func_id() {
    Prob p;
    return p;
}

void solve(std::istream& is, std::ostream& os) {
    Num n, m;
    is >> n >> m;

    Vec aset(n);
    for(auto&& x : aset) {
        is >> x;
    }

    atcoder::lazy_segtree<Node, func_operate, func_unit, Prob, func_map, func_compose, func_id> tree(n+1);
    for(Num i{0}; i<n; ++i) {
        Node node;
        node.width = 1;
        node.average = aset.at(i);
        tree.set(i, node);
    }

    for(Num i{0}; i<m; ++i) {
        Num l, r, x;
        is >> l >> r >> x;
        --l;

        ModInt inverse_p = 1;
        inverse_p /= (r - l);

        Prob prob;
        ModInt p_remaining = 1;
        p_remaining -= inverse_p;
        prob.prob_kept = p_remaining;

        ModInt value = x;
        value *= inverse_p;
        prob.value = value;

        tree.apply(l, r, prob);
    }

    for(Num i{0}; i<n; ++i) {
        os << tree.prod(i, i+1).average.val();
        if ((i+1) >= n) {
            os << "\n";
        } else {
            os << " ";
        }
    }
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Judge Result