Submission #17047509

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using i64 = long long;

template <typename T, typename U, typename F, typename G, typename H>
class LazySegmentTree {
    int size;
    T tid;
    std::vector<T> dat;
    U uid;
    std::vector<U> lazy;

    F f;
    G g;
    H h;

    void propagate(const int k, const int l, const int r) {
        if (lazy[k] == uid) return;

        if (k < size - 1) {
            lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
            lazy[2 * k + 2] = h(lazy[2 * k + 2], lazy[k]);
        }

        dat[k] = g(dat[k], lazy[k], r - l);
        lazy[k] = uid;
    }

    T update_impl(const int a, const int b, const U x, const int k, const int l, const int r) {
        propagate(k, l, r);
        if (r <= a || b <= l) return dat[k];
        if (a <= l && r <= b) {
            lazy[k] = h(lazy[k], x);
            propagate(k, l, r);
            return dat[k];
        }

        return dat[k] = f(update_impl(a, b, x, 2 * k + 1, l, (l + r) / 2),
                          update_impl(a, b, x, 2 * k + 2, (l + r) / 2, r));
    }

    T query_impl(const int a, const int b, const int k, const int l, const int r) {
        propagate(k, l, r);
        if (r <= a || b <= l) return tid;
        if (a <= l && r <= b) return dat[k];
        return f(query_impl(a, b, 2 * k + 1, l, (l + r) / 2),
                 query_impl(a, b, 2 * k + 2, (l + r) / 2, r));
    }

    static int calc_size(const int n) {
        int ret = 2;
        while (ret < n) ret *= 2;
        return ret;
    }

public:
    LazySegmentTree(const int n, const T &tid, const U &uid, F f, G g, H h)
        : size(calc_size(n))
        , tid(tid)
        , dat(size * 2 - 1, tid)
        , uid(uid)
        , lazy(size * 2 - 1, uid)
        , f(f)
        , g(g)
        , h(h) {}

    template <template <class> class Container, class TId>
    LazySegmentTree(const Container<T> &v, const TId &tid, const U &uid, F f, G g, H h)
        : size(calc_size(v.size()))
        , tid(tid)
        , dat(size * 2 - 1, tid)
        , uid(uid)
        , lazy(size * 2 - 1, uid)
        , f(f)
        , g(g)
        , h(h)
    {
        std::copy(v.begin(), v.end(), dat.begin() + size - 1);
        dig(0);
    }

    void dig(const int v) {
        if (v >= size - 1) return;
        dig(2 * v + 1);
        dig(2 * v + 2);
        dat[v] = f(dat[2 * v + 1], dat[2 * v + 2]);
    }

    void update(const int a, const int b, const U x) {
        update_impl(a, b, x, 0, 0, size);
    }

    T query(const int a, const int b) {
        return query_impl(a, b, 0, 0, size);
    }

    T operator[](const int i) {
        return query(i, i + 1);
    }
};

constexpr auto pow(long long x, long long n, const long long mod) {
    long long ret = 1;
    while(n > 0) {
        if ((n & 1) == 1) ret = (ret * x) % mod;
        x = (x * x) % mod;
        n >>= 1;
    }
    return ret;
}

constexpr auto inverse(const long long x, const long long p) {
    return pow(x, p - 2, p);
}

int main() {
    constexpr i64 mod = 998244353;
    int n, q;
    std::cin >> n >> q;

    std::vector<i64> p10 { 1 };
    for (int i = 0; i < 200010; i++) p10.push_back(p10.back() * 10 % mod);
    constexpr i64 i9 = inverse(9, mod);

    std::vector v(n, std::pair { 1ll, 1 });
    LazySegmentTree lst(v, std::pair { 0ll, 0 }, 0,
        [&,mod](const auto &lhs, const auto &rhs) {
            return std::make_pair(
                (lhs.first * p10[rhs.second] % mod + rhs.first) % mod,
                lhs.second + rhs.second
            );
        },
        [&,mod,i9](const auto, const auto u, const auto len) {
            const i64 r = (p10[len] + mod - 1) % mod * i9 % mod * u % mod;
            return std::make_pair(r, len);
        },
        [](const auto, const auto curr) { return curr; });

    while (q--) {
        int l, r, d;
        std::cin >> l >> r >> d;
        lst.update(l - 1, r, d);
        std::cout << lst.query(0, n).first << '\n';
    }

    return 0;
}

Submission Info

Judge Result