提出 #17042935

---

ソースコード 拡げる

/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

#include <bits/stdc++.h>
using namespace std;

const bool ready = [](){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(12);
    return true;
}();

const double PI = acos(-1);
using ll= long long;
#define int ll
#define all(v) (v).begin(), (v).end()
#define fori(n) for(int i=0; i<int(n); i++)

#define cini(i) int i; cin>>i;
#define cins(s) string s; cin>>s;
#define cind(d) double d; cin>>d;
#define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; }
#define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; }

using pii= pair<int, int>;
using pdd= pair<double, double>;
using vd= vector<double>;
using vb= vector<bool>;
using vi= vector<int>;
using vvi= vector<vi>;
using vs= vector<string>;

#define endl "\n"


template<typename E>
struct SegmentTreeLazy {
    vector<E> data;
    vector<E> lazySet;
    vector<bool> lazySetB;  /* flag if there is a pending lazySet in node */

    E neutral;
    int n;

    function<E(E,E)> plus;
    function<E(E,int,int)> mult2;

    SegmentTreeLazy(int _n, E _neutral) {
        n=1;
        while(n<_n)
            n*=2;

        data.resize(n*2, _neutral);
        lazySet.resize(n*2, _neutral);
        lazySetB.resize(n*2);
        neutral=_neutral;
    }

    /* bulk update in O(n) */
    template<typename Iterator>
    void init(Iterator beg, Iterator end) {
        for(int idx=n; beg!=end; beg++, idx++)
            data[idx]=*beg;

        for(int idx=n-1; idx>=1; idx--)
            data[idx]=plus(data[idx*2], data[idx*2+1]);
    }

    /* pushes down the pending updates to the vertex node 
     * If both lazies are set then the inc was later, so both
     * have to be pushed.
     * But first the set, which erases all previously set 
     * and inc on the child nodes, then the inc.
     * */
    void pushlazy(int node, int sL, int sR) {
        if(lazySetB[node]) {
            //cerr<<"pushlazy Set, node="<<node<<" sL="<<sL<<" sR="<<sR<<endl;

            if(sL!=sR) {
                int mid=(sL+sR)/2;
                rangeSet(node*2, sL   , mid, sL   , mid, lazySet[node]);
                rangeSet(node*2+1, mid+1, sR , mid+1, sR , lazySet[node]);
            }

            lazySetB[node]=false;
            lazySet[node]=neutral;
        }
    }

    /* @return accumulative (l,r), both inclusive, top down */
    E query(int node, int sL, int sR, int l, int r) {
        if (r < sL || l > sR)
            return neutral;
        //cerr<<"query, node="<<node<<" sL="<<sL<<" sR="<<sR<<" l="<<l<<" r="<<r<<" data[node]="<<data[node]<<endl;

        if (l<=sL && r>=sR)
            return data[node];

        pushlazy(node, sL, sR);

        int mid = (sL+sR)/2;
        return plus(query(node*2, sL, mid, l, r), query(node*2+1, mid+1, sR, l, r));
    }
    E query(int l, int r) {
        return query(1, 0, n-1, l, r);
    }

    /* set all position in (l,r) to val */
    void rangeSet(int node, int sL, int sR, int l, int r, E val) {
        if (r < sL || l > sR)
            return;
        //cerr<<"rangeSet node="<<node<<" sL="<<sL<<" sR="<<sR<<" l="<<l<<" r="<<r<<" val="<<val<<endl;

        if(l<=sL && r>=sR) {
            lazySet[node]=val;
            lazySetB[node]=true;
            data[node]=mult2(val, sL, sR);
            //cerr<<"rangeSet did set node="<<data[node]<<endl;
            return;
        }

        pushlazy(node, sL, sR);

        int mid = (sL+sR)/2;
        rangeSet(node*2  , sL   , mid, l, r, val);
        rangeSet(node*2+1, mid+1, sR , l, r, val);
        data[node]=plus(data[node*2], data[node*2+1]);
    }

    /* set val at positions (l,r) */
    void rangeSet(int l, int r, E val) {
        rangeSet(1, 0, n-1, l, r, val);
    }
};


const int MOD=998244353;

int mul(const int v1, const int v2, int mod=MOD) {
    return (int)((1LL * v1 * v2) % mod);
}

int pl(int v1, int v2, int mod=MOD) {
    int res = v1 + v2;

    while(res < 0)
        res += mod;

    while(res>=mod)
        res-=mod;

    return res;
}

/* 
 * SegmentTree, lazy updates.
 *
 * But the update-function is complecated :/
 * We need to consider the sum of the pows of the positions...somehow.
 *
 */
void solve() {
    cini(n);
    cini(q);

    vi ten(n);
    vi pten(n+1);   /* prefix sums of ten[] */
    ten[0]=1;
    pten[1]=ten[0];
    for(int i=1; i<n; i++) {
        ten[i]=mul(ten[i-1], 10);
        pten[i+1]=pl(pten[i], ten[i]);
    }

    SegmentTreeLazy<int> seg(n, 0);
    seg.plus=[](int i1, int i2) { return (i1+i2)%MOD; };
    seg.mult2=[&](int v, int l, int r) {
        return mul(pl(pten[r+1], -pten[l]), v);
    };

    seg.rangeSet(0,n-1,1);

    for(int i=0; i<q; i++) {
        cini(l); l--;
        cini(r); r--;
        cini(d);
        seg.rangeSet(n-1-r, n-1-l,d);
        cout<<seg.query(0,n-1)<<endl;
    }
}

signed main() {
    solve();
}

// FIRST THINK, THEN CODE
// DO NOT JUMP BETWEEN PROBLEMS

提出情報

ジャッジ結果