Problem:


Score : 500 points

Problem Statement

You have a string S of length N.
Initially, all characters in S are 1s.

You will perform queries Q times.
In the i-th query, you are given two integers L_i, R_i and a character D_i (which is a digit).
Then, you must replace all characters from the L_i-th to the R_i-th (inclusive) with D_i.

After each query, read the string S as a decimal integer, and print its value modulo 998,244,353.

Constraints

1 \leq N, Q \leq 200,000

1 \leq L_i \leq R_i \leq N

1 \leq D_i \leq 9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
L_1 R_1 D_1
:
L_Q R_Q D_Q

Output

Print Q lines.
In the i-th line print the value of S after the i-th query, modulo 998,244,353.

Sample Input 1

8 5
3 6 2
1 4 7
3 8 3
2 2 2
4 5 1

Sample Output 1

11222211
77772211
77333333
72333333
72311333

Sample Input 2

200000 1
123 456 7

Sample Output 2

641437905

Don't forget to take the modulo.



Sample input:
8 5
3 6 2
1 4 7
3 8 3
2 2 2
4 5 1


Sample output:
11222211
77772211
77333333
72333333
72311333

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
# sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline
# readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class LazySegmentTree():
    def __init__(self, op, e, mapping, composition, im, init_array):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.im = im

        l = len(init_array)

        def ceil_pow2(n):
            x = 0
            while (1 << x) < n:
                x += 1
            return x
        self.log = ceil_pow2(l)
        self.size = 1 << self.log
        self.d = [e() for _ in range(2*self.size)]
        self.lz = [im() for _ in range(self.size)]

        for i, a in enumerate(init_array):
            self.d[i+self.size] = a

        for i in range(self.size-1, 0, -1):
            self.__update(i)

    def set(self, p, x):
        p += self.size

        for i in range(self.log, 0, -1):
            self.__push(p >> i)

        self.d[p] = x

        for i in range(1, self.log+1):
            self.__update(p >> i)

    def __getitem__(self, p):
        p += self.size
        for i in range(self.log, 0, -1):
            self.__push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        if l == r:
            return self.e()

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push(r >> i)

        sml = self.e()
        smr = self.e()

        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1

        return self.op(sml, smr)

    def apply(self, l, r, f):
        if l == r:
            return

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push((r-1) >> i)

        l2, r2 = l, r
        while l < r:
            if l & 1:
                self.__all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.__all_apply(r, f)
            l >>= 1
            r >>= 1
        l, r = l2, r2

        for i in range(1, self.log+1):
            if ((l >> i) << i) != l:
                self.__update(l >> i)
            if ((r >> i) << i) != r:
                self.__update((r-1) >> i)

    def __update(self, k):
        self.d[k] = self.op(self.d[2*k], self.d[2*k+1])

    def __all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def __push(self, k):
        self.__all_apply(2*k, self.lz[k])
        self.__all_apply(2*k+1, self.lz[k])
        self.lz[k] = self.im()


M = 998244353
m = 1 << 32
m -= 1


def ser(a, b):
    return (a << 32) + b


def des(v):
    return v >> 32, v & m


def e():
    return 0


def op(sl, sr):
    sl = des(sl)
    sr = des(sr)
    return ser((sl[0] + sr[0]) % M, (sl[1] + sr[1]) % M)


def mapping(fl, sr):
    fl = des(fl)
    if fl[0] == 0:
        return sr
    sr = des(sr)
    return ser((sr[1]*fl[0]) % M, sr[1])


def composition(fl, fr):
    fl2 = des(fl)
    fr2 = des(fr)
    if fl2[1] > fr2[1]:
        return fl
    return fr


def im():
    return 0


@mt
def slv(N, Q, LRQ):
    A = []
    for i in range(N):
        v = pow(10, N-i-1, M)
        v %= M
        A.append(ser(v, v))
    st = LazySegmentTree(op, e, mapping, composition, im, A)

    ans = []
    for i, (l, r, q) in enumerate(LRQ, start=1):
        l -= 1
        st.apply(l, r, ser(q, i))
        ans.append(des(st.prod(0, N))[0])
    return ans


def main():
    N, Q = read_int_n()
    LRQ = [read_int_n() for _ in range(Q)]
    print(*slv(N, Q, LRQ), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline


class LazySegmentTree:
    def __init__(self, n, unitX, unitA, X_f, A_f, XA_map):
        self.n = n
        self.unitX = unitX
        self.unitA = unitA
        self.X_f = X_f  # (X, X) -> X
        self.A_f = A_f  # (A, A) -> A
        self.XA_map = XA_map  # (X, A) -> X
        self.X = [unitX] * (self.n + self.n)
        self.A = [unitA] * (self.n + self.n)

    def __getitem__(self, i):
        i += self.n
        self._propagate_above(i)
        return self.X[i]

    def __setitem__(self, i, x):
        i += self.n
        self._propagate_above(i)
        self.X[i] = x
        self._calc_above(i)

    def build(self, array):
        for i, val in enumerate(array, self.n):
            self.X[i] = val
        for i in range(self.n - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def _calc_above(self, i):
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def _propagate_above(self, i):
        k = i >> 1
        H = k.bit_length() - 1
        for h in range(H, -1, -1):
            i = k >> h
            if self.A[i] == self.unitA:
                continue
            self.X[i << 1] = self.XA_map(self.X[i << 1], self.A[i])
            self.X[i << 1 | 1] = self.XA_map(self.X[i << 1 | 1], self.A[i])
            self.A[i << 1] = self.A_f(self.A[i << 1], self.A[i])
            self.A[i << 1 | 1] = self.A_f(self.A[i << 1 | 1], self.A[i])
            self.A[i] = self.unitA

    def fold(self, l, r):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self._propagate_above(l0)
        self._propagate_above(r0)
        xl = self.unitX
        xr = self.unitX
        while l < r:
            if l & 1:
                xl = self.X_f(xl, self.X[l])
                l += 1
            if r & 1:
                r -= 1
                xr = self.X_f(self.X[r], xr)
            l >>= 1
            r >>= 1
        return self.X_f(xl, xr)

    def apply(self, i, a):
        i += self.n
        self._propagate_above(i)
        self.X[i] = self.XA_map(self.X[i], a)
        self.A[i] = self.A_f(self.A[i], a)
        self._calc_above(i)

    def apply_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self._propagate_above(l0)
        self._propagate_above(r0)
        while l < r:
            if l & 1:
                self.X[l] = self.XA_map(self.X[l], a)
                self.A[l] = self.A_f(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.X[r] = self.XA_map(self.X[r], a)
                self.A[r] = self.A_f(self.A[r], a)
            l >>= 1
            r >>= 1
        self._calc_above(l0)
        self._calc_above(r0)


n, q = map(int, input().split())
queries = [list(map(int, input().split())) for i in range(q)]
MOD = 998244353


pow_ = [1] * (n + 1)
for i in range(n):
    pow_[i + 1] = (pow_[i] * 10) % MOD

digit = [[0] * (n + 1) for i in range(10)]
for i in range(n):
    for val in range(10):
        digit[val][i + 1] = (digit[val][i] + pow_[i] * val) % MOD

unitX = (0, 0)
def X_f(x1, x2):
   return ((x1[0] * pow_[x2[1]] + x2[0]) % MOD, x1[1] + x2[1])

unitA = -1
A_f = lambda a1, a2: a1 if a2 == unitA else a2
def XA_map(x, a):
    if a != unitA: x = (digit[a][x[1]], x[1])
    return x


lst = LazySegmentTree(n, unitX, unitA, X_f, A_f, XA_map) 
lst.build([(1, 1) for i in range(n)])

ans = []
for l, r, d in queries:
    l -= 1
    lst.apply_range(l, r, d)
    ans.append(lst.fold(0, n)[0])
    
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
# sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline
# readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class LazySegmentTree():
    def __init__(self, op, e, mapping, composition, im, init_array):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.im = im

        l = len(init_array)

        def ceil_pow2(n):
            x = 0
            while (1 << x) < n:
                x += 1
            return x
        self.log = ceil_pow2(l)
        self.size = 1 << self.log
        self.d = [e() for _ in range(2*self.size)]
        self.lz = [im() for _ in range(self.size)]

        for i, a in enumerate(init_array):
            self.d[i+self.size] = a

        for i in range(self.size-1, 0, -1):
            self.__update(i)

    def set(self, p, x):
        p += self.size

        for i in range(self.log, 0, -1):
            self.__push(p >> i)

        self.d[p] = x

        for i in range(1, self.log+1):
            self.__update(p >> i)

    def __getitem__(self, p):
        p += self.size
        for i in range(self.log, 0, -1):
            self.__push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        if l == r:
            return self.e()

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push(r >> i)

        sml = self.e()
        smr = self.e()

        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1

        return self.op(sml, smr)

    def apply(self, l, r, f):
        if l == r:
            return

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push((r-1) >> i)

        l2, r2 = l, r
        while l < r:
            if l & 1:
                self.__all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.__all_apply(r, f)
            l >>= 1
            r >>= 1
        l, r = l2, r2

        for i in range(1, self.log+1):
            if ((l >> i) << i) != l:
                self.__update(l >> i)
            if ((r >> i) << i) != r:
                self.__update((r-1) >> i)

    def __update(self, k):
        self.d[k] = self.op(self.d[2*k], self.d[2*k+1])

    def __all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def __push(self, k):
        self.__all_apply(2*k, self.lz[k])
        self.__all_apply(2*k+1, self.lz[k])
        self.lz[k] = self.im()


@mt
def slv(N, Q, LRQ):


    M = 998244353


    def ser(a, b):
        return (a << 32) + b


    m = 1 << 32
    m -= 1


    def des(v):
        return v >> 32, v & m


    def e():
        return 0


    def op(sl, sr):
        sl = des(sl)
        sr = des(sr)
        return ser((sl[0] + sr[0]) % M, (sl[1] + sr[1]) % M)


    def mapping(fl, sr):
        fl = des(fl)
        if fl[0] == 0:
            return sr
        sr = des(sr)
        return ser((sr[1]*fl[0]) % M, sr[1])


    def composition(fl, fr):
        fl2 = des(fl)
        fr2 = des(fr)
        if fl2[1] > fr2[1]:
            return fl
        return fr


    def im():
        return 0
    A = []
    for i in range(N):
        v = pow(10, N-i-1, M)
        v %= M
        A.append(ser(v, v))
    st = LazySegmentTree(op, e, mapping, composition, im, A)

    ans = []
    for i, (l, r, q) in enumerate(LRQ, start=1):
        l -= 1
        st.apply(l, r, ser(q, i))
        ans.append(des(st.prod(0, N))[0])
    return ans


def main():
    N, Q = read_int_n()
    LRQ = [read_int_n() for _ in range(Q)]
    print(*slv(N, Q, LRQ), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class LazySegmentTree:


    __slots__ = ["n", "original_size", "log", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]


    def __init__(self, length_or_list, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
        self.me = monoid_identity
        self.oe = operator_identity
        self.fmm = func_monoid_monoid
        self.fmo = func_monoid_operator
        self.foo = func_operator_operator

        if isinstance(length_or_list, int):
            self.original_size = length_or_list
            self.log = (self.original_size - 1).bit_length()
            self.n = 1 << self.log
            self.data = [self.me] * (self.n * 2)
            self.lazy = [self.oe] * (self.n * 2)
        elif isinstance(length_or_list, list):
            self.original_size = len(length_or_list)
            self.log = (self.original_size - 1).bit_length()
            self.n = 1 << self.log
            self.data = [self.me] * self.n + length_or_list + [self.me] * (self.n - self.original_size)
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
            self.lazy = [self.oe] * (self.n * 2)
        else:
            raise TypeError(f"The argument 'length_or_list' must be an integer or a list, not {type(length_or_list).__name__}")
            

    def replace(self, index, value):
        if index < 0:
            index += self.original_size
        if not (0 <= index < self.original_size):
            raise IndexError("LazySegmentTree index out of range")

        index += self.n

        # propagation
        for shift in range(self.log, 0, -1):
            i = index >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # update
        self.data[index] = value
        self.lazy[index] = self.oe

        # recalculation
        i = index
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe


    def __getitem__(self, index):
        if index < 0:
            index += self.original_size
        if not (0 <= index < self.original_size):
            raise IndexError("LazySegmentTree index out of range")

        index += self.n

        # propagation
        for shift in range(self.log, 0, -1):
            i = index >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        return self.data[index]


    def effect_single(self, index, operator):
        if index < 0:
            index += self.original_size
        if not (0 <= index < self.original_size):
            raise IndexError("LazySegmentTree index out of range")

        index += self.n

        # propagation
        for shift in range(self.log, 0, -1):
            i = index >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # update
        self.data[index] = self.fmo(self.data[index], operator)

        # recalculation
        i = index
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe


    def effect(self, l, r, operator):
        if l < 0:
            l += self.original_size
        if r < 0:
            r += self.original_size
        if not 0 <= l <= r <= self.original_size:
            raise IndexError("LazySegmentTree index out of range")

        if l == r:
            return

        l += self.n
        r += self.n

        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2
        
        # propagation
        for shift in range(self.log, 0, -1):
            i = l >> shift
            if i << shift != l:
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
            i = r >> shift
            if i << shift != r:
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe

        # effect
        while l < r:
            if l % 2:
                self.lazy[l] = self.foo(self.lazy[l], operator)
                l += 1
            if r % 2:
                r -= 1
                self.lazy[r] = self.foo(self.lazy[r], operator)
            l //= 2
            r //= 2

        # recalculation
        i = l0
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
        i = r0
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
            
        
    def folded(self, l, r):
        if l < 0:
            l += self.original_size
        if r < 0:
            r += self.original_size
        if not 0 <= l <= r <= self.original_size:
            raise IndexError("LazySegmentTree index out of range")

        if l == r:
            return self.me 

        l += self.n
        r += self.n

        # propagation
        for shift in range(self.log, 0, -1):
            i = l >> shift
            if i << shift != l:
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
            i = r >> shift
            if i << shift != r:
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe

        # fold
        left_folded = self.me
        right_folded = self.me
        while l < r:
            if l % 2:
                left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
            l //= 2
            r //= 2
        return self.fmm(left_folded, right_folded)


    def all_folded(self):
        return self.data[1]

    
    def max_right(self, l, f):
        if l < 0:
            l += self.original_size
        if not (0 <= l <= self.original_size):
            raise IndexError("LazySegmentTree index out of range")
        assert f(self.me)

        if l == self.original_size:
            return self.original_size

        l += self.n

        # propagation
        for shift in range(self.log, 0, -1):
            i = l >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        left_folded = self.me
        while True:
            while l % 2 == 0:
                l //= 2
            if not f(self.fmm(left_folded, self.data[l])):
                while l < self.n:
                    i = l
                    self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                    self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                    self.data[i] = self.fmo(self.data[i], self.lazy[i])
                    self.lazy[i] = self.oe
                    l *= 2
                    if f(self.fmm(left_folded, self.data[l])):
                        left_folded = self.fmm(left_folded, self.data[l])
                        l += 1
                return l - self.n
            left_folded = self.fmm(left_folded, self.data[l])
            l += 1
            if l == l & -l:
                break
        return self.original_size

    def min_left(self, r, f):
        if r < 0:
            r += self.original_size
        if not (0 <= r <= self.original_size):
            raise IndexError("LazySegmentTree index out of range")
        assert f(self.me)

        if r == 0:
            return 0
        
        r += self.n

        # propagation
        for shift in range(self.log, 0, -1):
            i = r >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        right_folded = self.me
        while True:
            r -= 1
            while (r > 1 and r % 2):
                r //= 2
            if not f(self.fmm(self.data[r], right_folded)):
                while r < self.n:
                    i = r
                    self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                    self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                    self.data[i] = self.fmo(self.data[i], self.lazy[i])
                    self.lazy[i] = self.oe
                    r = 2 * r + 1
                    if f(self.fmm(self.data[r], right_folded)):
                        right_folded = self.fmm(self.data[r], right_folded)
                        r -= 1
                return r + 1 - self.n
            right_folded = self.fmm(self.data[r], right_folded)
            if r == r & -r:
                break
        return 0


MOD = 998244353
mask32 = (1 << 32) - 1


import sys
input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read



N, Q = map(int, input().split())


pw = [1]
for _ in range(N + 2):
    pw.append(pw[-1] * 10 % MOD)


# 値 << 32 + 長さ
def fmm(m1, m2):
    v1 = m1 >> 32
    l1 = m1 & mask32
    v2 = m2 >> 32
    l2 = m2 & mask32
    v = (v1 * pw[l2] + v2) % MOD
    l = l1 + l2
    return (v << 32) + l

inv9 = pow(9, MOD - 2, MOD)
def fmo(m, o):
    if o == -1:
        return m
    else:
        l = m & mask32
        v = o * (pw[l] - 1) * inv9 % MOD
        return (v << 32) + l

def foo(o1, o2):
    if o2 == -1:
        return o1
    else:
        return o2

lst = LazySegmentTree([(1 << 32) + 1] * N, 0, -1, fmm, fmo, foo)

LRDs = map(int, read().split())
for L, R, D in zip(LRDs, LRDs, LRDs):
    lst.effect(L - 1, R, D)
    print(lst.all_folded() >> 32)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()

# ライブラリ参照https://atcoder.jp/contests/practice2/submissions/16579094


class LazySegmentTree():
    def __init__(self, init, unitX, unitA, f, g, h):
        self.f = f  # (X, X) -> X
        self.g = g  # (X, A, size) -> X
        self.h = h  # (A, A) -> A
        self.unitX = unitX
        self.unitA = unitA
        self.f = f
        if type(init) == int:
            self.n = init
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            # self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * \
                len(init) + [0] * (self.n - len(init))
            for i in range(self.n-1, 0, -1):
                self.X[i] = self.f(self.X[i*2], self.X[i*2 | 1])

        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2 | 1]

        self.A = [unitA] * (self.n * 2)

    def update(self, i, x):
        i += self.n
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.f(self.X[i*2], self.X[i*2 | 1])
            i >>= 1

    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])

    def calc_above(self, i):
        i >>= 1
        while i:
            self.X[i] = self.f(self.calc(i*2), self.calc(i*2 | 1))
            i >>= 1

    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2 | 1] = self.h(self.A[i*2 | 1], self.A[i])
        self.A[i] = self.unitA

    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)

    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)

    def getrange(self, l, r):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)

        al = self.unitX
        ar = self.unitX
        while l < r:
            if l & 1:
                al = self.f(al, self.calc(l))
                l += 1
            if r & 1:
                r -= 1
                ar = self.f(self.calc(r), ar)
            l >>= 1
            r >>= 1
        return self.f(al, ar)

    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)

    def operate_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l < r:
            if l & 1:
                self.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1

        self.calc_above(l0)
        self.calc_above(r0)

    # Find r s.t. calc(l, ..., r-1) = True and calc(l, ..., r) = False
    def max_right(self, l, z):
        if l >= self.n:
            return self.n
        l += self.n
        s = self.unitX
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not z(self.f(s, self.calc(l))):
                while l < self.n:
                    l *= 2
                    if z(self.f(s, self.calc(l))):
                        s = self.f(s, self.calc(l))
                        l += 1
                return l - self.n
            s = self.f(s, self.calc(l))
            l += 1
            if l & -l == l:
                break
        return self.n

    # Find l s.t. calc(l, ..., r-1) = True and calc(l-1, ..., r-1) = False
    def min_left(self, r, z):
        if r <= 0:
            return 0
        r += self.n
        s = self.unitX
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.f(self.calc(r), s)):
                while r < self.n:
                    r = r * 2 + 1
                    if z(self.f(self.calc(r), s)):
                        s = self.f(self.calc(r), s)
                        r -= 1
                return r + 1 - self.n
            s = self.f(self.calc(r), s)
            if r & -r == r:
                break
        return 0


def main():
    P = 998244353
    def f(x, y): return ((x[0] + y[0]) % P, x[1]+y[1])
    def g(x, a, s): return ((x[1]*a) % P, x[1]) if a != 10**10 else x
    def h(a, b): return b if b != 10**10 else a
    unitX = (0, 0)
    unitA = 10**10
    N, Q = map(int, input().split())
    A = [(1, 1)]
    for _ in range(N-1):
        now = A[-1][0]
        A.append(((now*10) % P, (now*10) % P))
    st = LazySegmentTree(A[::-1], unitX, unitA, f, g, h)
    #print(st.getrange(0, N))

    for _ in range(Q):
        l, r, d = map(int, input().split())
        st.operate_range(l-1, r, d)
        print(st.getrange(0, N)[0])


if __name__ == '__main__':
    main()