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:
from typing import Callable, List, TypeVar

S = TypeVar("S")  # 作用付きモノイドの型
F = TypeVar("F")  # 写像の型


class LazySegmentTree:
    """
    Lazy Segment Tree from https://atcoder.jp/contests/practice2/submissions/16775176
    References:
        https://tumoiyorozu.github.io/single-file-ac-library/document_ja/lazysegtree.html
        https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp
    """

    __slots__ = ["e", "op", "id", "mapping", "composition", "_n", "_log", "_size", "tree", "lazy"]

    def __init__(self,
                 a: List[S],
                 e: S,
                 op: Callable[[S, S], S],
                 id_: F,
                 mapping: Callable[[F, S], S],
                 composition: Callable[[F, F], F]) -> None:
        self.e = e
        self.op = op
        self.id = id_
        self.mapping = mapping
        self.composition = composition

        self._n = len(a)
        self._log = (self._n - 1).bit_length()
        self._size = 1 << self._log

        self.tree = [e] * self._size + a + [e] * (self._size - self._n)
        for i in range(self._size - 1, 0, -1):
            self._update(i)

        self.lazy = [id_] * self._size

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def _apply_all(self, k: int, f: F) -> None:
        self.tree[k] = self.mapping(f, self.tree[k])
        if k < self._size:
            self.lazy[k] = self.composition(f, self.lazy[k])

    def _push(self, k: int) -> None:
        self._apply_all(2 * k, self.lazy[k])
        self._apply_all(2 * k + 1, self.lazy[k])
        self.lazy[k] = self.id

    def set(self, k: int, x: S) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        self.tree[k] = x
        for i in range(1, self._log + 1):
            self._update(k >> i)

    def get(self, k: int) -> S:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n

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

    def prod(self, l: int, r: int) -> S:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n

        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, smr = self.e, self.e
        while l < r:
            if l & 1:
                sml = self.op(sml, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.tree[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def prod_all(self) -> S:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]

    def apply(self, k: int, f: F) -> None:
        """Apply a[p] = op_st(a[p], x) in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        self.tree[k] = self.mapping(f, self.tree[k])
        for i in range(1, self._log + 1):
            self._update(k >> i)

    def apply_range(self, l: int, r: int, f: F) -> None:
        """Apply a[i] = op_st(a[i], x) for all i = l..r-1 in O(log n)."""
        assert 0 <= l <= r <= self._n

        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)

        l_tmp, r_tmp = l, r
        while l < r:
            if l & 1:
                self._apply_all(l, f)
                l += 1
            if r & 1:
                r -= 1
                self._apply_all(r, f)
            l >>= 1
            r >>= 1
        l, r = l_tmp, r_tmp

        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)


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

mod = 998244353

base = [None] * N
base[N-1] = (1, 1)

for i in range(N-2, -1, -1):
    b = (base[i+1][1] * 10) % mod
    base[i] = (b, b)


def op(l, r):
    return [l[0]+r[0], l[1]+r[1]]


def mapping(l, r):
    if l == -1:
        return r
    return [l*r[1], r[1]]


def composition(l, r):
    if l == -1:
        return r
    return l


seg = LazySegmentTree(base, [0, 0], op, -1, mapping, composition)

for i in range(Q):
    L, R, D = map(int, input().split())
    seg.apply_range(L-1, R, D)
    print(seg.prod_all()[0] % mod)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
def binary(n):
    return bin(n)[2:]
def bjy(a, x, n): # a^x mod n
    if x==0:
      return 1
    x = [int(b) for b in binary(x)]
    y = a
    for i in range(1, len(x)):
        y = (y**2) % n
        if x[i] == 1:
            y = (y * a) % n
    return y
  
  #####segfunc#####
def segfunc(x, y):
    return(x+y)
#################

#####ide_ele#####
ide_ele =0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res
tab=[]
mod=998244353
out=0
for i in range(n):
  jy=bjy(10,i,mod)
  tab.append(jy)
  out+=jy
  out%=mod
num=[1]*n
seg=SegTree(tab,segfunc,ide_ele)
for i in range(q):
  l,r,d=map(int,input().split())
  l-=1
  r-=1
  for j in range(l,r+1):
    seg.update(n-j-1,tab[n-j-1]*d)
    num[j]=d
  out=(seg.query(0,n))
  out%=mod

  print(out)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp

INF = inf
MOD = 998244353

n, q = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()]for j in range(q)]    # nは行数

tmp = "1" * n
res = []

for i in range(q):
    l, r, d = A[i]
    tmp = tmp[:l - 1] + str(d) * (r - l + 1) + tmp[r:]
    res.append(int(tmp) % MOD)

res = "\n".join([str(r) for r in res])
print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    # N: 処理する区間の長さ
    INF = 2**31-1
    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [0]*(2*N0)
    lazy = [None]*(2*N0)
    mod = 998244353

    modv = [0]*N0*2
    modv[N0+N-2] = 1

    for i in range(N-1):
        modv[N0+N-3-i] = (modv[N0+N-2-i]*10) % mod
    # print(modv)
    for i in range(N0-2, -1, -1):
        modv[i] = (modv[2*i+1] + modv[2*i+2]) % mod

    def gindex(l, r):
        L = (l + N0) >> 1
        R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1
            R >>= 1

    # 遅延伝搬処理

    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if v is None:
                continue
            lazy[2*i-1] = lazy[2*i] = v
            # data[2*i-1] = data[2*i] = v * modv[2*i-1] % mod
            data[2*i-1] = v*modv[2*i-1] % mod
            data[2*i] = v*modv[2*i] % mod
            # print(data)
            lazy[i-1] = None

    # 区間[l, r)をxに更新

    # print(modv)

    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)

        L = N0 + l
        R = N0 + r
        v = x
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] = v
                data[R-1] = v * modv[R-1] % mod
            if L & 1:
                lazy[L-1] = v
                data[L-1] = v * modv[L-1] % mod
                L += 1
            L >>= 1
            R >>= 1
        for i in ids:
            data[i-1] = (data[2*i-1] + data[2*i]) % mod

    # 区間[l, r)内の合計を求める

    def query(l, r):
        propagates(*gindex(l, r))
        # print(data)
        L = N0 + l
        R = N0 + r

        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s += data[R-1]
            if L & 1:
                s += data[L-1]
                L += 1
            L >>= 1
            R >>= 1
            s %= mod
        return s

    update(0, N, 1)

    for i in range(Q):
        l, r, d = map(int, input().split())
        update(l-1, r, d)
        print((query(0, N) % mod))


main()

Submission status: Time Limit Exceeded

Solution code:
A = input().split()
N = int(A[0])
Q = int(A[1])
B = list()
C = '1'
for i in range(N):
  B.append(C)
B2 = B
for i in range(Q):
  B = B2
  X = input().split()
  L = int(X[0])
  R = int(X[1])
  D = X[2]
  Y = list()
  for i in range(L-1,R):
    Y.append(D)
  B[L-1:R]=Y
  s = int(''.join(B))
  print(s % 998244353)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

Ref = [[0 for _ in range(100)] for _ in range(10)]
pow_2_lv = [pow(2,lv) for lv in range(30)]
for i in range(1,10):
  Ref[i][0] = i
  for s in range(1,30):
    Ref[i][s] += Ref[i][s-1] * (pow(10, pow(2, s-1), MOD) + 1) % MOD
#print(Ref)  
#####segfunc#####
def segfunc(x, y):
    return [(x[0] * pow(10, y[1], MOD) + y[0]) % MOD, x[1] + y[1]]
#################

#####ide_ele#####
ide_ele = [0,0]
#################

class LazySegmentTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(l, r, x): 区間[l, r)をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        num: n以上の最小の2のべき乗
        data: 値配列(1-index)
        lazy: 遅延配列(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.data[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])

    def gindex(self, l, r):
            """
            伝搬する対象の区間を求める
            lm: 伝搬する必要のある最大の左閉区間
            rm: 伝搬する必要のある最大の右開区間
            """
            l += self.num
            r += self.num
            lm = l >> (l & -l).bit_length()
            rm = r >> (r & -r).bit_length()

            while r > l:
                if l <= lm:
                    yield l
                if r <= rm:
                    yield r
                r >>= 1
                l >>= 1
            while l:
                yield l
                l >>= 1

    def propagates(self, *ids):
        """
        遅延伝搬処理
        ids: 伝搬する対象の区間 
        """
        for i in reversed(ids):
            v = self.lazy[i]
            if v == ide_ele:
                continue
            lv = self.num.bit_length() - (2*i).bit_length() 
            upd = Ref[v[0]%10][lv]
            #print(v[0]%10, lv)
            self.lazy[2 * i] = [upd, pow_2_lv[lv]]
            self.lazy[2 * i + 1] = [upd, pow_2_lv[lv]]
            self.data[2 * i] = [upd, pow_2_lv[lv]]
            self.data[2 * i + 1] = [upd, pow_2_lv[lv]]
            self.lazy[i] = ide_ele

    def update(self, l, r, x):
        """
        区間[l, r)の値をxに更新
        l, r: index(0-index)
        x: update value
        """
        *ids, = self.gindex(l, r)
        #print(l, r, " ids = ", ids)
        self.propagates(*ids)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                lv = self.num.bit_length() - l.bit_length() 
                #print(l, lv)
                upd = Ref[x[0]][lv]
                self.lazy[l] = [upd, pow_2_lv[lv]]
                self.data[l] = [upd, pow_2_lv[lv]]
                l += 1
            if r & 1:
                lv = self.num.bit_length() - (r-1).bit_length()
                upd = Ref[x[0]][lv]
                #print(r, lv)
                self.lazy[r - 1] = [upd, pow_2_lv[lv]]
                self.data[r - 1] = [upd, pow_2_lv[lv]]
            r >>= 1
            l >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])


    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(self.data[l], res)
                l += 1
            if r & 1:
                res = self.segfunc(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res
  
N, Q = map(int,input().split())
lst = LazySegmentTree([[1, 1] for _ in range(N)], segfunc, ide_ele)
#print(lst.data)
for _ in range(Q):
  L, R, D = map(int,input().split())
  L -= 1
  R -= 1
  lst.update(L, R+1, [D,1])
  print(lst.data[1][0])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    # N: 処理する区間の長さ
    INF = 2**31-1
    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [0]*(2*N0)
    lazy = [None]*(2*N0)
    mod = 998244353

    modv = [0]*N0*2
    modv[N0+N-2] = 1

    for i in range(N-1):
        modv[N0+N-3-i] = (modv[N0+N-2-i]*10) % mod
    # print(modv)
    for i in range(N0-2, -1, -1):
        modv[i] = (modv[2*i+1] + modv[2*i+2]) % mod

    def gindex(l, r):
        L = (l + N0) >> 1
        R = (r + N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        for i in range(LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1
            R >>= 1

    # 遅延伝搬処理

    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if v is None:
                continue
            lazy[2*i-1] = lazy[2*i] = v
            #data[2*i-1] = data[2*i] = v * modv[2*i-1] % mod
            data[2*i-1] = v*modv[2*i-1] % mod
            data[2*i] = v*modv[2*i] % mod
            # print(data)
            lazy[i-1] = None

    # 区間[l, r)をxに更新

    # print(modv)

    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)

        L = N0 + l
        R = N0 + r
        v = x
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] = v
                data[R-1] = v * modv[R-1] % mod
            if L & 1:
                lazy[L-1] = v
                data[L-1] = v * modv[L-1] % mod
                L += 1
            L >>= 1
            R >>= 1
        for i in ids:
            data[i-1] = (data[2*i-1] + data[2*i]) % mod

    # 区間[l, r)内の合計を求める

    def query(l, r):
        propagates(*gindex(l, r))
        # print(data)
        L = N0 + l
        R = N0 + r

        s = 0
        while L < R:
            if R & 1:
                R -= 1
                s += data[R-1]
            if L & 1:
                s += data[L-1]
                L += 1
            L >>= 1
            R >>= 1
            s %= mod
        return s

    update(0, N, 1)

    for i in range(Q):
        l, r, d = map(int, input().split())
        update(l-1, r, d)
        print(query(0, N) % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
N, Q = map(int, input().split())
# N: 処理する区間の長さ
INF = 2**31-1
LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [None]*(2*N0)
mod = 998244353

modv = [0]*N0*2
modv[N0+N-2] = 1

for i in range(N-1):
    modv[N0+N-3-i] = (modv[N0+N-2-i]*10) % mod
# print(modv)
for i in range(N0-2, -1, -1):
    modv[i] = (modv[2*i+1] + modv[2*i+2]) % mod


def gindex(l, r):
    L = (l + N0) >> 1
    R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1
        R >>= 1

# 遅延伝搬処理


def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = lazy[2*i] = v
        #data[2*i-1] = data[2*i] = v * modv[2*i-1] % mod
        data[2*i-1] = v*modv[2*i-1] % mod
        data[2*i] = v*modv[2*i] % mod
        # print(data)
        lazy[i-1] = None

# 区間[l, r)をxに更新


# print(modv)


def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l
    R = N0 + r
    v = x
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = v
            data[R-1] = v * modv[R-1] % mod
        if L & 1:
            lazy[L-1] = v
            data[L-1] = v * modv[L-1] % mod
            L += 1
        L >>= 1
        R >>= 1
    for i in ids:
        data[i-1] = (data[2*i-1] + data[2*i]) % mod

# 区間[l, r)内の合計を求める


def query(l, r):
    propagates(*gindex(l, r))
    # print(data)
    L = N0 + l
    R = N0 + r

    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s += data[R-1]
        if L & 1:
            s += data[L-1]
            L += 1
        L >>= 1
        R >>= 1
        s %= mod
    return s


update(0, N, 1)

for i in range(Q):
    l, r, d = map(int, input().split())
    update(l-1, r, d)
    print(query(0, N) % mod)

Submission status: Time Limit Exceeded

Solution code:
from typing import Callable, List, TypeVar

S = TypeVar("S")  # 作用付きモノイドの型
F = TypeVar("F")  # 写像の型


class LazySegmentTree:
    """
    Lazy Segment Tree from https://atcoder.jp/contests/practice2/submissions/16775176
    References:
        https://tumoiyorozu.github.io/single-file-ac-library/document_ja/lazysegtree.html
        https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp
    """

    __slots__ = ["e", "op", "id", "mapping", "composition", "_n", "_log", "_size", "tree", "lazy"]

    def __init__(self,
                 a: List[S],
                 e: S,
                 op: Callable[[S, S], S],
                 id_: F,
                 mapping: Callable[[F, S], S],
                 composition: Callable[[F, F], F]) -> None:
        self.e = e
        self.op = op
        self.id = id_
        self.mapping = mapping
        self.composition = composition

        self._n = len(a)
        self._log = (self._n - 1).bit_length()
        self._size = 1 << self._log

        self.tree = [e] * self._size + a + [e] * (self._size - self._n)
        for i in range(self._size - 1, 0, -1):
            self._update(i)

        self.lazy = [id_] * self._size

    def _update(self, k: int) -> None:
        """Update the value of a[k]."""
        self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1])

    def _apply_all(self, k: int, f: F) -> None:
        self.tree[k] = self.mapping(f, self.tree[k])
        if k < self._size:
            self.lazy[k] = self.composition(f, self.lazy[k])

    def _push(self, k: int) -> None:
        self._apply_all(2 * k, self.lazy[k])
        self._apply_all(2 * k + 1, self.lazy[k])
        self.lazy[k] = self.id

    def set(self, k: int, x: S) -> None:
        """Assign x to a[k] in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        self.tree[k] = x
        for i in range(1, self._log + 1):
            self._update(k >> i)

    def get(self, k: int) -> S:
        """Return a[k] in O(1)."""
        assert 0 <= k < self._n

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

    def prod(self, l: int, r: int) -> S:
        """Return op(a[l], ..., a[r - 1]). Return e, if l == r.
        Complexity: O(log n)
        """
        assert 0 <= l <= r <= self._n

        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, smr = self.e, self.e
        while l < r:
            if l & 1:
                sml = self.op(sml, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.tree[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def prod_all(self) -> S:
        """Return op(a[0], ..., a[n - 1]. Return e if n == 0.
        Complexity: O(1)
        """
        return self.tree[1]

    def apply(self, k: int, f: F) -> None:
        """Apply a[p] = op_st(a[p], x) in O(log n)."""
        assert 0 <= k < self._n

        k += self._size
        for i in range(self._log, 0, -1):
            self._push(k >> i)
        self.tree[k] = self.mapping(f, self.tree[k])
        for i in range(1, self._log + 1):
            self._update(k >> i)

    def apply_range(self, l: int, r: int, f: F) -> None:
        """Apply a[i] = op_st(a[i], x) for all i = l..r-1 in O(log n)."""
        assert 0 <= l <= r <= self._n

        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)

        l_tmp, r_tmp = l, r
        while l < r:
            if l & 1:
                self._apply_all(l, f)
                l += 1
            if r & 1:
                r -= 1
                self._apply_all(r, f)
            l >>= 1
            r >>= 1
        l, r = l_tmp, r_tmp

        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)


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

mod = 998244353

base = [None] * N
base[N-1] = (1, 1)

for i in range(N-2, -1, -1):
    b = (base[i+1][1] * 10) % mod
    base[i] = (b, b)


def op(l, r):
    return [(l[0]+r[0]) % mod, (l[1]+r[1]) % mod]


def mapping(l, r):
    if l == -1:
        return r
    return [l*r[1], r[1]]


def composition(l, r):
    if l == -1:
        return r
    return l


seg = LazySegmentTree(base, [0, 0], op, -1, mapping, composition)

for i in range(Q):
    L, R, D = map(int, input().split())
    seg.apply_range(L-1, R, D)
    print(seg.prod_all()[0])

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
# N: 処理する区間の長さ
INF = 2**31-1
LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [None]*(2*N0)
mod = 998244353

modv = [0]*N0*2
modv[N0+N-2] = 1

for i in range(N-1):
    modv[N0+N-3-i] = (modv[N0+N-2-i]*10) % mod
# print(modv)
for i in range(N0-2, -1, -1):
    modv[i] = (modv[2*i+1] + modv[2*i+2]) % mod


def gindex(l, r):
    L = (l + N0) >> 1
    R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1
        R >>= 1

# 遅延伝搬処理


def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = lazy[2*i] = v
        #data[2*i-1] = data[2*i] = v * modv[2*i-1] % mod
        data[2*i-1] = v*modv[2*i-1] % mod
        data[2*i] = v*modv[2*i] % mod
        # print(data)
        lazy[i-1] = None

# 区間[l, r)をxに更新


# print(modv)


def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l
    R = N0 + r
    v = x
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = v
            data[R-1] = v * modv[R-1] % mod
        if L & 1:
            lazy[L-1] = v
            data[L-1] = v * modv[L-1] % mod
            L += 1
        L >>= 1
        R >>= 1
    for i in ids:
        data[i-1] = (data[2*i-1] + data[2*i]) % mod

# 区間[l, r)内の合計を求める


def query(l, r):
    propagates(*gindex(l, r))
    # print(data)
    L = N0 + l
    R = N0 + r

    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s += data[R-1]
        if L & 1:
            s += data[L-1]
            L += 1
        L >>= 1
        R >>= 1
        s %= mod
    return s


update(0, N, 1)

for i in range(Q):
    l, r, d = map(int, input().split())
    update(l-1, r, d)
    print(query(0, N) % mod)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
# N: 処理する区間の長さ
INF = 2**31-1
LV = (N-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [None]*(2*N0)
mod = 998244353

modv = [0]*N0*2
modv[N0+N-2] = 1

for i in range(N-1):
    modv[N0+N-3-i] = (modv[N0+N-2-i]*10) % mod
# print(modv)
for i in range(N0-2, -1, -1):
    modv[i] = (modv[2*i+1] + modv[2*i+2]) % mod


def gindex(l, r):
    L = (l + N0) >> 1
    R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1
        R >>= 1

# 遅延伝搬処理


def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = lazy[2*i] = v
        #data[2*i-1] = data[2*i] = v * modv[2*i-1] % mod
        data[2*i-1] = v*modv[2*i-1] % mod
        data[2*i] = v*modv[2*i] % mod
        # print(data)
        lazy[i-1] = None

# 区間[l, r)をxに更新


# print(modv)


def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l
    R = N0 + r
    v = x
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = v
            data[R-1] = v * modv[R-1] % mod
        if L & 1:
            lazy[L-1] = v
            data[L-1] = v * modv[L-1] % mod
            L += 1
        L >>= 1
        R >>= 1
    for i in ids:
        data[i-1] = (data[2*i-1] + data[2*i]) % mod

# 区間[l, r)内の合計を求める


def query(l, r):
    propagates(*gindex(l, r))
    # print(data)
    L = N0 + l
    R = N0 + r

    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s += data[R-1]
        if L & 1:
            s += data[L-1]
            L += 1
        L >>= 1
        R >>= 1
    return s


update(0, N, 1)

for i in range(Q):
    l, r, d = map(int, input().split())
    update(l-1, r, d)
    print(query(0, N) % mod)