Language: C++

#include <bits/stdc++.h>
#include <iostream>
#include <ctime>
#include <atcoder/all>
using namespace std;
#define _LL long long
#define rep(i, n) for (_LL i = 0; i < (_LL)(n); i++)
#define vecrep(itr, v) for (auto itr = (v).begin(); itr != (v).end(); itr++)
using namespace atcoder;


template<class T, class U> class SegTreeDelaySkelton
{
    private:
        int _n;
        int _d;
        int _bit;
        T* nodes;
        bool *_used;
        // 子に伝搬する情報があるか
        bool *_last;

        // leftとrightでparentを更新。left, rightにNULLが入ることも。[indexl, indexr)までがparentの担当
        void (*_update)(T* parent, T* left, T* right, int indexl, int indexr);

        // nodeをvで更新する。（親への伝搬はクラス内で処理）
        void (*_rangef)(T* node, T* v, int indexl, int indexr);

        U (*_get)(T* node, U lv, U rv, int l, int r, int indexl, int indexr);

    public:
        SegTreeDelaySkelton(int n, void (*update)(T*, T*, T*, int, int), void (*f)(T*, T*, int, int) )
        {
            construct(n, update, f);
            int d = _d;
            for(int i = _bit - 1; i >= 0; i-- ) 
            {
                if( i < (1 << (d - 1)) ) d--; 
                if(_used[i]) callupdate(i, d);
            }
        }

        SegTreeDelaySkelton(int n, void (*update)(T*, T*, T*, int, int), void (*f)(T*, T*, int, int), T def)
        {
            construct(n, update, f);
            for(int i = 0; i < n; i++ ) nodes[_bit + i] = def;
            int d = _d;
            for(int i = _bit - 1; i >= 0; i-- ) 
            {
                if( i < (1 << (d - 1)) ) d--; 
                if(_used[i]) callupdate(i, d);
            }
        }

        void setGet( U (*get)(T*, U, U, int, int, int, int) )
        {
            _get = get;
        }

        void set(int index, T node)
        {
            nodes[_bit + index] = node;
            updatenode((_bit + index) / 2, _d - 1);
        }

        void updatenode(int i, int d)
        {
            callupdate(i, d);
            if( i > 1) updatenode( i / 2, d - 1 );
        }

        T* top() { return nodes + 1;}
        U get(int l) { return getRangeSub(l, l + 1, 1, 1); }

        void range(int l, int r, T* v)
        {
            rangeSub(l, r, v, 1, 1);
        }

        U getrange(int l, int r)
        {
            return getRangeSub(l, r, 1, 1);
        }

        ~SegTreeDelaySkelton()
        {
            delete nodes;
            delete _used;
        }
    private:

        T* getnode(int i)
        {
            return _used[i] ? nodes + i : NULL;
        }

        void callupdate(int i, int d)
        {
            int nodel, noder;
            int nodesize = 1 << (_d - d);
            int nodetop = 1 << (d - 1);
            nodel = (d - nodetop) * nodesize;
            noder = nodel + nodesize;

            int t = i; int topd = 1;
            while( t > 1 ) { topd = (topd << 1); t = ( t >> 1);}
            int no = i - topd;
            int k = _bit / topd;            
            _update(nodes + i, getnode(i * 2), getnode(i * 2 + 1), nodel, noder);
        }

        void construct(int n, void (*update)(T*, T*, T*, int, int), void (*f)(T*, T*, int, int))
        {
            _get = NULL;
            _update = update;
            _rangef = f;
            _n = n;
            _d = 1;
            _bit = 1;
            while( _bit < _n )
            {
                _bit *= 2;
                _d++;
            }
            nodes = new T[_bit * 2];
            _used = new bool[_bit * 2];
            _last = new bool[_bit * 2];
            for(int i = 0; i < _bit * 2; i++ ) _last[i] = false;
            for(int i = 0; i < n; i++ ) _used[_bit + i] = true;
            for(int i = _bit - 1; i > 0; i-- ) _used[i] = (_used[i * 2] || _used[i * 2 + 1]);
        }

        void rangeSub(int l, int r, T *v, int index, int d)
        {
            int nodel, noder, nodec;
            int nodesize = 1 << (_d - d);
            int nodetop = 1 << (d - 1);
            nodel = (index - nodetop) * nodesize;
            noder = nodel + nodesize;
            nodec = nodel + (nodesize >> 1);
            if( noder - nodel <= 1 || (l <= nodel && r >= noder) ) { _last[index] = true; _rangef(nodes + index, v, nodel, noder); return;}
            // 伝搬
            if(  _last[index] )
            {
                if( _used[index * 2]) { _rangef(nodes + index * 2, nodes + index, nodel, nodec); _last[index * 2] = true; }
                if( _used[index * 2 + 1]) {_rangef(nodes + index * 2 + 1, nodes + index, nodec, noder); _last[index * 2 + 1] = true; }
                nodes[index].reset();
            }
            _last[index] = false;

            if( l < nodec && r > nodel ) rangeSub(l, r, v, index * 2, d + 1);
            if( r > nodec && l < noder ) rangeSub(l, r, v, index * 2 + 1, d + 1);
            _update(nodes + index, getnode(index * 2), getnode(index * 2 + 1), nodel, noder);
        }    

        U getRangeSub(int l, int r, int index, int d)
        {
            int nodel, noder, nodec;
            int nodesize = 1 << (_d - d);
            int nodetop = 1 << (d - 1);
            nodel = (index - nodetop) * nodesize;
            noder = nodel + nodesize;
            nodec = nodel + (nodesize >> 1);
            if( r <= nodel || l>= noder ) return U();
            if( noder - nodel <= 1 || (l <= nodel && r >= noder) ) return _get(nodes + index, U(), U(), l, r, nodel, noder);
            return _get(nodes + index, getRangeSub(l, r, index * 2, d + 1), getRangeSub(l, r, index * 2 + 1, d + 1), l, r, nodel, noder);
        }              
};

struct ModInt
{
    static int _BM;
    long long int m_value;

    int getint() const { return (int) m_value; }
    void _mod() 
    {
        if( m_value < 0 ) m_value += ((-m_value) / _BM + 1) * _BM;
        m_value %= _BM;
    }
    ModInt() { m_value = 0; }
    ModInt(int v) { m_value = (_LL) v; _mod(); }
    ModInt(_LL v) { m_value = (_LL) v; _mod(); }    
    ModInt(const ModInt &t) { m_value = t.getint(); }
    ModInt& operator += ( int v ) { m_value += v; _mod(); return *this; }
    ModInt& operator -= ( int v ) { m_value -= v; _mod(); return *this; }
    ModInt& operator *= ( int v ) { m_value *= v; _mod(); return *this; }
    ModInt& operator += ( _LL v ) { return (*this) += (int)(v % _BM); }
    ModInt& operator -= ( _LL v ) { return (*this) -= (int)(v % _BM); }
    ModInt& operator *= ( _LL v ) { return (*this) *= (int)(v % _BM); }
    ModInt& operator += ( const ModInt &t ) { (*this) += t.getint(); return (*this); }
    ModInt& operator *= ( const ModInt &t ) { (*this) *= t.getint(); return (*this); }
    ModInt& operator -= ( const ModInt &t ) { (*this) -= t.getint(); return (*this); }
    bool operator < ( int v ) { return m_value < v; }
    bool operator > ( int v ) { return m_value > v; }
    bool operator <= ( int v ) { return m_value <= v; }
    bool operator >= ( int v ) { return m_value >= v; }
    bool operator == ( int v ) { return m_value == v; }
    bool operator != ( int v ) { return m_value != v; }
    static int reciprocal(_LL a)
    {
        _LL b = _BM, u = 1, v = 0;
        while (b) {
            _LL t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        u %= _BM; 
        if (u < 0) u += _BM;
        return (int)u;
    }
    static int reciprocal(int a) { return reciprocal((_LL) a); }

    ModInt& operator /= ( const ModInt &t ) { (*this) /= t.getint(); return (*this); }
    ModInt& operator /= ( int v ) { (*this) *= reciprocal(v); return *this; }    
    ModInt& operator /= ( _LL v ) { (*this) *= reciprocal(v); return *this; }    
    const ModInt operator + (const ModInt &t) const { ModInt ans(*this); return ans += t; }
    const ModInt operator + (int t)  const { ModInt ans(*this); return ans += t; }
    const ModInt operator + (_LL t)  const { ModInt ans(*this); return ans += t; }        
    const ModInt operator - (const ModInt &t) const { ModInt ans(*this); return ans -= t; }
    const ModInt operator - (int t)  const { ModInt ans(*this); return ans -= t; }
    const ModInt operator - (_LL t)  const { ModInt ans(*this); return ans -= t; }        
    const ModInt operator * (const ModInt &t) const { ModInt ans(*this); return ans *= t; }
    const ModInt operator * (int t)  const { ModInt ans(*this); return ans *= t; }
    const ModInt operator * (_LL t)  const { ModInt ans(*this); return ans *= t; }
    const ModInt operator / (const ModInt &t) const { ModInt ans(*this); return ans /= t; }
    const ModInt operator / (int t)  const { ModInt ans(*this); return ans /= t; }
    const ModInt operator / (_LL t)  const { ModInt ans(*this); return ans /= t; }

    static int modadd( int a, int b ) { ModInt t(a); t += b; return t.getint(); }
    static int modminus( int a, int b ) { ModInt t(a); t -= b; return t.getint(); }
    static int modmul( int a, int b ) { ModInt t(a); t *= b; return t.getint(); }
    static int modadd( _LL a, _LL b ) { ModInt t(a); t += b; return t.getint(); }
    static int modminus( _LL a, _LL b ) { ModInt t(a); t -= b; return t.getint(); }    
    static int modmul( _LL a, _LL b ) { ModInt t(a); t *= b; return t.getint(); } 
    static int modpow(int a, int b) { return modpow((_LL) a, (_LL)b); }
    static int modpow(_LL a, _LL b)
    {
        ModInt ans(1);
        int heap[64];
        heap[0] = (a % _BM);
        for( int bit = 0; b >= (((_LL)1) << bit); bit++ )
        {
            if( bit > 0 ) heap[bit] = modmul( heap[bit - 1], heap[bit - 1] );
            if( b & (((_LL)1) << bit) )
            {
                ans *= heap[bit];
            }
        }
        return ans.getint();
    }

    static int getCombination(_LL n, _LL r)
    {
        _LL ans;
        ans = 1;
        for(_LL i = 0; i < r; i++) ans = modmul(ans, n - i);
        _LL inv = 1;
        for(_LL i = 0; i < r; i++) inv = modmul(inv, i + 1);
        return modmul(ans, (_LL) reciprocal(inv));
    }

    static int combination(int n, int r)
    {
        int *fac = (int *)malloc(sizeof(int) * (n + 1));
        int *facinv = (int *)malloc(sizeof(int) * (n + 1));
        fac[0] = 1;
        for( int k = 1; k <= n; k++) fac[k] = modmul(k, fac[k - 1]);
        facinv[n] = reciprocal( fac[n] );
        for( int k = n ; k > 0; k--) facinv[k - 1] = modmul(k, facinv[k]);

        ModInt ans(fac[n]);
        ans *= facinv[r];
        ans *= facinv[n - r];

        free(fac);
        free(facinv);
        return ans.getint();
    }
};

int ModInt::_BM = 998244353;
int mypow10[200001];
ModInt inv9;
struct MyNode
{
    int value;
    ModInt ans;
    int leaf;

    MyNode() { value = 0; leaf = 1; ans = 0;}
    void reset()
    {
        value = 0;
    }
};

void myupdate(MyNode* parent, MyNode* left, MyNode* right, int indexl, int indexr)
{
    if( right == NULL )
    {
        parent->leaf = left->leaf;
        parent->ans = left->ans;
    }
    else if( left == NULL )
    {
        parent->leaf = right->leaf;
        parent->ans = right->ans;
    }
    else
    {
        parent->leaf = left->leaf + right->leaf;    
        parent->ans = right->ans + left->ans * mypow10[right->leaf];
    }
}

void setrange(MyNode* node, MyNode *v, int indexl, int indexr)
{
    node->value = v->value;
    node->ans = ModInt( mypow10[node->leaf] - 1) * inv9 * v->value;
}

int main()
{
    int n, q; cin >> n >> q;
    MyNode defv;
    defv.value = 1;
    defv.leaf = 1;
    defv.ans = 1;
    ModInt x10 = 1;
    inv9 = ModInt::reciprocal(9);
    rep(i, n + 1) { mypow10[i] = x10.getint(); x10 *= 10;}
    SegTreeDelaySkelton<MyNode, int> st(n, myupdate, setrange, defv);
    rep(i, q)
    {
        int l, r, d; cin >> l >> r >> d;
        l--; r--;
        defv.value = d;
        st.range(l, r + 1, &defv);
        cout << st.top()->ans.getint() << endl;
    }
}

Compiler output:
a.cc:4:10: fatal error: atcoder/all: No such file or directory
    4 | #include <atcoder/all>
      |          ^~~~~~~~~~~~~
compilation terminated.