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: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import typing
import sys
def main(N, Q, LRD):
    tree = LazySegTree(
        op=lambda x, y: (x[0] * y[1] + y[0], x[1] * y[1]),
        e=(Mint(0), Mint(1)),
        mapping=lambda f, s: s if f == 0 else ((s[1] - 1) // 9 * f, s[1]),
        composition=lambda f, g: g if f == 0 else f,
        id_=0,
        v=[(Mint(1), Mint(10))] * N)

    for l, r, d in LRD:
        l -= 1
        tree.apply(l, r, d)
        print(tree.all_prod()[0])

def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1

    return x

def _bsf(n: int) -> int:
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2

    return x

class LazySegTree:
    def __init__(
            self,
            op: typing.Callable[[typing.Any, typing.Any], typing.Any],
            e: typing.Any,
            mapping: typing.Callable[[typing.Any, typing.Any], typing.Any],
            composition: typing.Callable[[typing.Any, typing.Any], typing.Any],
            id_: typing.Any,
            v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e
        self._mapping = mapping
        self._composition = composition
        self._id = id_

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = _ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)
        self._lz = [self._id] * self._size
        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        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 get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        return self._d[p]

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n

        if left == right:
            return self._e

        left += self._size
        right += self._size

        for i in range(self._log, 0, -1):
            if ((left >> i) << i) != left:
                self._push(left >> i)
            if ((right >> i) << i) != right:
                self._push(right >> i)

        sml = self._e
        smr = self._e
        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1

        return self._op(sml, smr)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    def apply(self, left: int, right: typing.Optional[int] = None,
              f: typing.Optional[typing.Any] = None):
        assert f is not None

        if right is None:
            p = left
            assert 0 <= left < self._n

            p += self._size
            for i in range(self._log, 0, -1):
                self._push(p >> i)
            self._d[p] = self._mapping(f, self._d[p])
            for i in range(1, self._log + 1):
                self._update(p >> i)
        else:
            assert 0 <= left <= right <= self._n
            if left == right:
                return

            left += self._size
            right += self._size

            for i in range(self._log, 0, -1):
                if ((left >> i) << i) != left:
                    self._push(left >> i)
                if ((right >> i) << i) != right:
                    self._push((right - 1) >> i)

            l2 = left
            r2 = right
            while left < right:
                if left & 1:
                    self._all_apply(left, f)
                    left += 1
                if right & 1:
                    right -= 1
                    self._all_apply(right, f)
                left >>= 1
                right >>= 1
            left = l2
            right = r2

            for i in range(1, self._log + 1):
                if ((left >> i) << i) != left:
                    self._update(left >> i)
                if ((right >> i) << i) != right:
                    self._update((right - 1) >> i)

    def max_right(
            self, left: int, g: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert g(self._e)

        if left == self._n:
            return self._n

        left += self._size
        for i in range(self._log, 0, -1):
            self._push(left >> i)

        sm = self._e
        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not g(self._op(sm, self._d[left])):
                while left < self._size:
                    self._push(left)
                    left *= 2
                    if g(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1

        return self._n

    def min_left(self, right: int, g: typing.Any) -> int:
        assert 0 <= right <= self._n
        assert g(self._e)

        if right == 0:
            return 0

        right += self._size
        for i in range(self._log, 0, -1):
            self._push((right - 1) >> i)

        sm = self._e
        first = True
        while first or (right & -right) != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not g(self._op(self._d[right], sm)):
                while right < self._size:
                    self._push(right)
                    right = 2 * right + 1
                    if g(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)

        return 0

    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

    def _all_apply(self, k: int, f: typing.Any) -> None:
        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: int) -> None:
        self._all_apply(2 * k, self._lz[k])
        self._all_apply(2 * k + 1, self._lz[k])
        self._lz[k] = self._id

MOD = 998244353
class Mint:
    __slots__ = ('value')

    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    LRD = [tuple(map(int, input().split())) for _ in range(Q)]
    main(N, Q, LRD)

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import typing
import sys
MOD = 998244353
def main(N, Q, LRD):
    tree = LazySegTree(
        op=lambda x, y: ((x[0] * y[1] + y[0]) % MOD, x[1] * y[1]),
        e=(0, 1),
        mapping=lambda f, s: s if f == 0 else ((s[1] - 1) // 9 * f, s[1]),
        composition=lambda f, g: g if f == 0 else f,
        id_=0,
        v=[(1, 10)] * N)

    for l, r, d in LRD:
        l -= 1
        tree.apply(l, r, d)
        print(tree.all_prod()[0])

def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1

    return x

def _bsf(n: int) -> int:
    x = 0
    while n % 2 == 0:
        x += 1
        n //= 2

    return x

class LazySegTree:
    def __init__(
            self,
            op: typing.Callable[[typing.Any, typing.Any], typing.Any],
            e: typing.Any,
            mapping: typing.Callable[[typing.Any, typing.Any], typing.Any],
            composition: typing.Callable[[typing.Any, typing.Any], typing.Any],
            id_: typing.Any,
            v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e
        self._mapping = mapping
        self._composition = composition
        self._id = id_

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = _ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)
        self._lz = [self._id] * self._size
        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        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 get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

        p += self._size
        for i in range(self._log, 0, -1):
            self._push(p >> i)
        return self._d[p]

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n

        if left == right:
            return self._e

        left += self._size
        right += self._size

        for i in range(self._log, 0, -1):
            if ((left >> i) << i) != left:
                self._push(left >> i)
            if ((right >> i) << i) != right:
                self._push(right >> i)

        sml = self._e
        smr = self._e
        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1

        return self._op(sml, smr)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    def apply(self, left: int, right: typing.Optional[int] = None,
              f: typing.Optional[typing.Any] = None):
        assert f is not None

        if right is None:
            p = left
            assert 0 <= left < self._n

            p += self._size
            for i in range(self._log, 0, -1):
                self._push(p >> i)
            self._d[p] = self._mapping(f, self._d[p])
            for i in range(1, self._log + 1):
                self._update(p >> i)
        else:
            assert 0 <= left <= right <= self._n
            if left == right:
                return

            left += self._size
            right += self._size

            for i in range(self._log, 0, -1):
                if ((left >> i) << i) != left:
                    self._push(left >> i)
                if ((right >> i) << i) != right:
                    self._push((right - 1) >> i)

            l2 = left
            r2 = right
            while left < right:
                if left & 1:
                    self._all_apply(left, f)
                    left += 1
                if right & 1:
                    right -= 1
                    self._all_apply(right, f)
                left >>= 1
                right >>= 1
            left = l2
            right = r2

            for i in range(1, self._log + 1):
                if ((left >> i) << i) != left:
                    self._update(left >> i)
                if ((right >> i) << i) != right:
                    self._update((right - 1) >> i)

    def max_right(
            self, left: int, g: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert g(self._e)

        if left == self._n:
            return self._n

        left += self._size
        for i in range(self._log, 0, -1):
            self._push(left >> i)

        sm = self._e
        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not g(self._op(sm, self._d[left])):
                while left < self._size:
                    self._push(left)
                    left *= 2
                    if g(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1

        return self._n

    def min_left(self, right: int, g: typing.Any) -> int:
        assert 0 <= right <= self._n
        assert g(self._e)

        if right == 0:
            return 0

        right += self._size
        for i in range(self._log, 0, -1):
            self._push((right - 1) >> i)

        sm = self._e
        first = True
        while first or (right & -right) != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not g(self._op(self._d[right], sm)):
                while right < self._size:
                    self._push(right)
                    right = 2 * right + 1
                    if g(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)

        return 0

    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

    def _all_apply(self, k: int, f: typing.Any) -> None:
        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: int) -> None:
        self._all_apply(2 * k, self._lz[k])
        self._all_apply(2 * k + 1, self._lz[k])
        self._lz[k] = self._id

if __name__ == '__main__':
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    LRD = [tuple(map(int, input().split())) for _ in range(Q)]
    main(N, Q, LRD)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,Q = MI()
mod = 998244353
power = [1]  # power[i] = 10**i
for i in range(N):
    power.append((power[-1]*10) % mod)
t = pow(9,mod-2,mod)  # 9 の逆数


class LazySegTree():  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self,N,X_func,A_func,operate,X_unit,A_unit):
        self.N = N
        self.X_func = X_func
        self.A_func = A_func
        self.operate = operate
        self.X_unit = X_unit
        self.A_unit = A_unit
        self.X = [self.X_unit]*(2*self.N)
        self.A = [self.A_unit]*(2*self.N)
        self.size = [0]*(2*self.N)

    def build(self,init_value):  # 初期値を[N,2N)に格納
        for i in range(self.N):
            self.X[self.N+i] = init_value[i]
            self.size[self.N+i] = 1
        for i in range(self.N-1,0,-1):
            self.X[i] = self.X_func(self.X[i << 1],self.X[i << 1 | 1])
            self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]

    def update(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.X_func(self.X[i << 1],self.X[i << 1 | 1])
            i >>= 1

    def eval_at(self,i):  # i番目で作用を施した値を返す
        return self.operate(self.X[i],self.A[i],self.size[i])

    def eval_above(self,i):  # i番目より上の値を再計算する
        i >>= 1
        while i:
            self.X[i] = self.X_func(self.eval_at(i << 1),self.eval_at(i << 1 | 1))
            i >>= 1

    def propagate_at(self,i):  # i番目で作用を施し、1つ下に作用の情報を伝える
        self.X[i] = self.operate(self.X[i],self.A[i],self.size[i])
        self.A[i << 1] = self.A_func(self.A[i << 1],self.A[i])
        self.A[i << 1 | 1] = self.A_func(self.A[i << 1 | 1], self.A[i])
        self.A[i] = self.A_unit

    def propagate_above(self,i):  # i番目より上で作用を施す
        H = i.bit_length()
        for h in range(H,0,-1):
            self.propagate_at(i >> h)

    def fold(self,L,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_func(vL,self.eval_at(L))
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_func(self.eval_at(R),vR)
            L >>= 1
            R >>= 1
        return self.X_func(vL,vR)

    def operate_range(self,L,R,x):  # [L,R)にxを作用
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        while L < R:
            if L & 1:
                self.A[L] = self.A_func(self.A[L],x)
                L += 1
            if R & 1:
                R -= 1
                self.A[R] = self.A_func(self.A[R],x)
            L >>= 1
            R >>= 1
        self.eval_above(L0)
        self.eval_above(R0)


def X_func(x,y):
    x1,x2 = x
    y1,y2 = y
    return ((x1*power[y2]+y1) % mod,x2+y2)


def A_func(a,b):
    a1,a2 = a
    b1,b2 = b
    return ((a1*b1) % mod,(a2*b1+b2) % mod)


def operate(x,a,r):  # 右作用
    x1,x2 = x
    a1,a2 = a
    return (a1*x1+(a2*(power[x2]-1)*t) % mod,x2)


LST = LazySegTree(N,X_func,A_func,operate,(0,0),(1,0))
LST.build([(1,1)]*N)

for _ in range(Q):
    l,r,d = MI()
    LST.operate_range(l-1,r,(0,d))
    print(LST.fold(0,N)[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,Q = MI()
mod = 998244353


class LazySegTree():  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self,N,X_func,A_func,operate,X_unit,A_unit):
        self.N = N
        self.X_func = X_func
        self.A_func = A_func
        self.operate = operate
        self.X_unit = X_unit
        self.A_unit = A_unit
        self.X = [self.X_unit]*(2*self.N)
        self.A = [self.A_unit]*(2*self.N)
        self.size = [0]*(2*self.N)

    def build(self,init_value):  # 初期値を[N,2N)に格納
        for i in range(self.N):
            self.X[self.N+i] = init_value[i]
            self.size[self.N+i] = 1
        for i in range(self.N-1,0,-1):
            self.X[i] = self.X_func(self.X[i << 1],self.X[i << 1 | 1])
            self.size[i] = self.size[i << 1] + self.size[i << 1 | 1]

    def update(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.X[i] = x
        i >>= 1
        while i:
            self.X[i] = self.X_func(self.X[i << 1],self.X[i << 1 | 1])
            i >>= 1

    def eval_at(self,i):  # i番目で作用を施した値を返す
        return self.operate(self.X[i],self.A[i],self.size[i])

    def eval_above(self,i):  # i番目より上の値を再計算する
        i >>= 1
        while i:
            self.X[i] = self.X_func(self.eval_at(i << 1),self.eval_at(i << 1 | 1))
            i >>= 1

    def propagate_at(self,i):  # i番目で作用を施し、1つ下に作用の情報を伝える
        self.X[i] = self.operate(self.X[i],self.A[i],self.size[i])
        self.A[i << 1] = self.A_func(self.A[i << 1],self.A[i])
        self.A[i << 1 | 1] = self.A_func(self.A[i << 1 | 1], self.A[i])
        self.A[i] = self.A_unit

    def propagate_above(self,i):  # i番目より上で作用を施す
        H = i.bit_length()
        for h in range(H,0,-1):
            self.propagate_at(i >> h)

    def fold(self,L,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_func(vL,self.eval_at(L))
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_func(self.eval_at(R),vR)
            L >>= 1
            R >>= 1
        return self.X_func(vL,vR)

    def operate_range(self,L,R,x):  # [L,R)にxを作用
        L += self.N
        R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.propagate_above(L0)
        self.propagate_above(R0)
        while L < R:
            if L & 1:
                self.A[L] = self.A_func(self.A[L],x)
                L += 1
            if R & 1:
                R -= 1
                self.A[R] = self.A_func(self.A[R],x)
            L >>= 1
            R >>= 1
        self.eval_above(L0)
        self.eval_above(R0)


def X_func(x,y):
    x1,x2 = x
    y1,y2 = y
    return ((x1*pow(10,y2,mod)+y1) % mod,x2+y2)


def A_func(a,b):
    a1,a2 = a
    b1,b2 = b
    return (a1*b1,a2*b1+b2)


def operate(x,a,r):  # 右作用
    x1,x2 = x
    a1,a2 = a
    return (a1*x1+(a2*(pow(10,r,mod)-1)*pow(9,mod-2,mod)) % mod,x2)


LST = LazySegTree(N,X_func,A_func,operate,(0,0),(1,0))
LST.build([(1,1)]*N)

for _ in range(Q):
    l,r,d = MI()
    LST.operate_range(l-1,r,(0,d))
    print(LST.fold(0,N)[0])

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = '1' * N
for i in range(Q):
    l, r, d = map(int, input().split())
    S = S[0:l - 1] + str(d) * (r - l + 1) + S[r:]
    ans = int(S) % 998244353
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
INF = float("inf")


class lazySegTree(object):
	def __init__(self, N):
		self.N = N
		self.LV = (N-1).bit_length()
		self.N0 = 2**self.LV
		self.data = [0]*(2*self.N0) #桁の値を管理(lazy*size)
		self.lazy = [0]*(2*self.N0) #桁の文字を管理
		self.size = [1]*(2*self.N0) #桁の和を管理(10^n)(更新しない)
		for i in range(self.N):
			self.size[self.N0-1+i] = pow(10, self.N-i-1, mod)
		for i in range(self.N0-2, -1, -1):
			self.size[i] = (self.size[2*i+1] + self.size[2*i+2])%mod
	# 遅延セグ木の初期化
	def initialize(self):
		for i in range(self.N):
			self.data[self.N0-1+i] = pow(10, self.N-i-1, mod)
		for i in range(self.N0-2, -1, -1):
			self.data[i] = (self.data[2*i+1] + self.data[2*i+2])%mod

  # 遅延伝播を行うindexを生成
	def gindex(self, l, r):
		L = l + self.N0
		L >>= 1
		R = r + self.N0
		R >>= 1
		if l & 1:
			lc = 0
		else:
			lc = (L & -L).bit_length()
		if r & 1:
			rc = 0
		else:
			rc = (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1 
			R >>= 1

	# 遅延伝搬処理
	def propagates(self, *ids):
		for i in reversed(ids):
			v = self.lazy[i - 1]
			if not v:
				continue
			self.lazy[2*i-1] = v
			self.lazy[2*i] = v
			self.data[2*i-1] = v * self.size[2*i-1]
			self.data[2*i] = v * self.size[2*i]
			self.lazy[i-1] = 0

	def update(self, l, r, x):
		*ids, = self.gindex(l, r+1)
		self.propagates(*ids)
		L = self.N0 + l
		R = self.N0 + r + 1
		while L < R:
			if R & 1:
				R -= 1
				self.lazy[R-1] = x #桁の文字を更新
				self.data[R-1] = x * self.size[R-1] #桁の値を更新
			if L & 1:
				self.lazy[L-1] = x
				self.data[L-1] = x * self.size[L-1]
				L += 1
			L >>= 1
			R >>= 1
		for i in ids:
			self.data[i-1] = (self.data[2*i-1] + self.data[2*i])%mod

	# 区間[l, r]内のdataの和を求める
	def query(self, l, r):
		self.propagates(*self.gindex(l, r+1))
		L = self.N0 + l
		R = self.N0 + r + 1
		s = 0
		while L < R:
			if R & 1:
				R -= 1
				s = (s + self.data[R-1])%mod
			if L & 1:
				s = (s + self.data[L-1])%mod
				L += 1
			L >>= 1
			R >>= 1
		return s

N, Q = map(int, input().split())
lSeg = lazySegTree(N)
lSeg.initialize()

for i in range(Q):
	L, R, D = map(int, input().split())
	L -= 1
	R -= 1
	lSeg.update(L, R, D)
	ans = lSeg.query(0, N-1)
	ans %= mod
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
mod = 998244353
INF = float("inf")


class lazySegTree(object):
	def __init__(self, N):
		self.N = N
		self.LV = (N-1).bit_length()
		self.N0 = 2**self.LV
		self.data = [0]*(2*self.N0) #桁の値を管理(lazy*size)
		self.lazy = [0]*(2*self.N0) #桁の文字を管理
		self.size = [1]*(2*self.N0) #桁の和を管理(10^n)(更新しない)
		for i in range(self.N):
			self.size[self.N0-1+i] = pow(10, self.N-i-1, mod)
		for i in range(self.N0-2, -1, -1):
			self.size[i] = (self.size[2*i+1] + self.size[2*i+2])%mod
	# 遅延セグ木の初期化
	def initialize(self):
		for i in range(self.N):
			self.data[self.N0-1+i] = pow(10, self.N-i-1, mod)
		for i in range(self.N0-2, -1, -1):
			self.data[i] = (self.data[2*i+1] + self.data[2*i+2])%mod

  # 遅延伝播を行うindexを生成
	def gindex(self, l, r):
		L = l + self.N0
		L >>= 1
		R = r + self.N0
		R >>= 1
		if l & 1:
			lc = 0
		else:
			lc = (L & -L).bit_length()
		if r & 1:
			rc = 0
		else:
			rc = (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1 
			R >>= 1

	# 遅延伝搬処理
	def propagates(self, *ids):
		for i in reversed(ids):
			v = self.lazy[i - 1]
			if not v:
				continue
			self.lazy[2*i-1] = v
			self.lazy[2*i] = v
			self.data[2*i-1] = v * self.size[2*i-1]
			self.data[2*i] = v * self.size[2*i]
			self.lazy[i-1] = 0

	def update(self, l, r, x):
		*ids, = self.gindex(l, r+1)
		self.propagates(*ids)
		L = self.N0 + l
		R = self.N0 + r + 1
		while L < R:
			if R & 1:
				R -= 1
				self.lazy[R-1] = x #桁の文字を更新
				self.data[R-1] = x * self.size[R-1] #桁の値を更新
			if L & 1:
				self.lazy[L-1] = x
				self.data[L-1] = x * self.size[L-1]
				L += 1
			L >>= 1
			R >>= 1
		for i in ids:
			self.data[i-1] = (self.data[2*i-1] + self.data[2*i])%mod

	# 区間[l, r]内のdataの和を求める
	def query(self, l, r):
		self.propagates(*self.gindex(l, r+1))
		L = self.N0 + l
		R = self.N0 + r + 1
		s = 0
		while L < R:
			if R & 1:
				R -= 1
				s = (s + self.data[R-1])%mod
			if L & 1:
				s = (s + self.data[L-1])%mod
				L += 1
			L >>= 1
			R >>= 1
			s %= mod
		return s

N, Q = map(int, input().split())
lSeg = lazySegTree(N)
lSeg.initialize()

for i in range(Q):
  L, R, D = map(int, input().split())
  L -= 1
  R -= 1
  lSeg.update(L, R, D)
  ans = lSeg.query(0, N-1)
  print(ans)