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: Wrong Answer

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 = 1 << (n - 1).bit_length()
        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
        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


unitX = (0, 0, 0)
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)
sz =  1 << (n - 1).bit_length()

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

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


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: Wrong Answer

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 = 1 << (n - 1).bit_length()
        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
        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


unitX = (0, 0, 0)
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)
sz =  1 << (n - 1).bit_length()

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

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


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: Wrong Answer

Solution code:
def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7

import sys
import math
import collections
n,q = L()
lrd = NL(q)
b = [1]*n
for l,r,d in lrd:
    for i in range(n):
        if i >= l-1 and i<r:
            print(d,end="")
            b[i]= d
        else:
            print(b[i],end="")
    print()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split(" "))
A=[1 for i in range(n)]

for i in range(m):
  a,b,x=map(int,input().split(" "))
  A=A[:a-1]+[x for i in range(b-a+1)]+A[b:]
  g=0
  for j in range(8):
    g=g+pow(10,j)*A[7-j]
  print(g%998244353)

Submission status: Wrong Answer

Solution code:
d = input().split()
N = int(d[0])
Q = int(d[1])
S = "1" * N
for i in range(Q):
  n = input().split()
  L = int(n[0])
  R = int(n[1])
  D = n[2]
  S = S[:L-1] + D * (R-L+1) + S[R-1:]
S = int(S)
print(S%998244353)

Submission status: Wrong Answer

Solution code:
# class化。
import sys

input = sys.stdin.buffer.readline

mod = 998244353

max_n = 2 * pow(10, 5) + 10
pow_list = [1] * max_n
cum_pow = [0] * max_n
cum_pow[0] = 1
for i in range(1, max_n):
    pow_list[i] = pow_list[i - 1] * 10
    pow_list[i] %= mod
    cum_pow[i] += cum_pow[i - 1] + pow_list[i]
    cum_pow[i] %= mod
cum_pow = [0] + cum_pow


class LazySegmentTree:
    # funcはseg同士、calcはpoint計算
    def __init__(self, n, ele, lazy_ele, mod=mod):
        self.n = n
        self.ele = ele
        self.lazy_ele = lazy_ele
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)
        self.LAZY = [self.lazy_ele] * (2 * self.num)
        self.node = [1] * (2 * self.num)
        for i in reversed(range(1, self.num)):
            self.node[i] = self.node[2 * i] + self.node[2 * i + 1]

    # SEG同士の計算
    def func(self, a, b, b_idx):
        # print(a, b, a_idx, b_idx)
        node_num = self.node[b_idx]
        return (a * pow_list[node_num] + b) % mod

    # LAZYをSEGに作用
    def calc(self, idx):
        if self.LAZY[idx] == -1:
            return self.SEG[idx]
        node_num = self.node[idx]
        res = (self.LAZY[idx] * cum_pow[node_num]) % mod
        return res

    # LAZY同士の作用の蓄積
    def lazy_func(self, a, b):
        return b

    # 配列で初期化
    def initialize(self, A):
        for i, val in enumerate(A):
            i += self.num
            self.SEG[i] = val
        for i in reversed(range(1, self.num)):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1], 2 * i)

    # LAZYの値を1つ下に伝播して初期化
    def propagate_point(self, idx):
        self.SEG[idx] = self.calc(idx)
        # print(idx)
        if self.LAZY[idx] >= 0:
            self.LAZY[2 * idx] = self.lazy_func(self.LAZY[2 * idx], self.LAZY[idx])
            self.LAZY[2 * idx + 1] = self.lazy_func(
                self.LAZY[2 * idx + 1], self.LAZY[idx]
            )
            self.LAZY[idx] = lazy_ele

    # idx=1からidxの直上まで、伝播を行う
    def propagate_above(self, idx):
        height = idx.bit_length() - 1
        # print(idx, height)
        for h in reversed(range(1, height + 1)):
            self.propagate_point(idx >> h)

    # そのidxの直上の値を計算
    def recalc_above(self, idx):
        # print("ra", idx)
        while idx > 1:
            idx //= 2
            self.SEG[idx] = self.func(
                self.calc(2 * idx), self.calc(2 * idx + 1), 2 * idx,
            )

    # 1点更新
    def update_point(self, idx):
        idx += self.num
        while idx > 0:
            idx //= 2
            self.SEG[idx] = self.func(
                self.calc(self.SEG[2 * idx]), self.calc(self.SEG[2 * idx + 1]), 2 * idx,
            )

    # 範囲更新
    def update_range(self, left, right, mono):
        left += self.num
        right += self.num
        left_temp = left // (left & -left)
        right_temp = right // (right & -right) - 1
        self.propagate_above(left_temp)
        self.propagate_above(right_temp)
        while left < right:
            if left & 1:
                self.LAZY[left] = self.lazy_func(self.LAZY[left], mono)
                left += 1
            if right & 1:
                right -= 1
                self.LAZY[right] = self.lazy_func(self.LAZY[right], mono)
            left //= 2
            right //= 2
        self.recalc_above(left_temp)
        self.recalc_above(right_temp)

    # 範囲取得
    def get_range(self, left, right):
        left += self.num
        right += self.num
        self.propagate_above(left // (left & -left))
        self.propagate_above(right // (right & -right) - 1)
        res_left = self.ele
        res_right = self.ele
        while left < right:
            if left & 1:
                res_left = self.func(res_left, self.calc(left), left)
                left += 1
            if right & 1:
                right -= 1
                res_right = self.func(self.calc(right), res_right, right)
            left //= 2
            right //= 2
        return self.func(res_right, res_left, self.n // 2) % mod

    # def get_point(self, idx):
    #     a,b=self.LAZY[idx]>>32, self.LAZY[idx]&(1<<32-1)
    #     return a*self.SEG[idx]+b*self.node[idx]


ele = 0
lazy_ele = -1
n, q = map(int, input().split())
A = [1 for _ in range(n)]
LST = LazySegmentTree(n, ele, lazy_ele)
LST.initialize(A)


for _ in range(q):
    l, r, d = map(int, input().split())
    l -= 1

    LST.update_range(l, r, d)

    print(LST.get_range(0, n) % mod)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
S = ["1" for _ in range(N)]
MOD = 998244353
ans = []
for _ in range(Q):
    l, r, d = map(int, input().split())
    tmp1 = S[:l - 1]
    tmp1 = "".join(tmp1)
    tmp2 = [str(d) for _ in range(r - l + 1)]
    tmp2 = "".join(tmp2)
    tmp3 = S[r:]
    tmp3 = "".join(tmp3)

    tmp = int(tmp1 + tmp2 + tmp3) % MOD
    # S = S[:l-1] + str(d) * (r - l + 1) + S[r:]
    ans.append(tmp)

for i in range(Q):
    print(ans[i])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, q=(int(x) for x in input().split())

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
s='1'*n
print(s)
for _ in range(q):
    a,b,c= map(int, input().split())
    s=s[:a-1]+str(c)*(b-a+1)+s[b:]
l=int(s)
print(l%998244353)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
queries = []
for _ in range(q):
    queries.append(list(map(int, input().split())))

s = [1] * n
for query in queries:
    tmp = ""
    for i in range(query[0]-1):
        tmp += str(s[i])
    for j in range(query[0]-1, query[1]):
        tmp += str(query[2])
        s[j] = query[2]
    for k in range(query[1]-1, n):
        tmp += str(s[k])
    print(tmp)

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
S = [1]*N
MOD = 998244353

for i in range(Q):
    L, R, D = map(int, input().split())
    S[L-1:R] = [D]*(R-L+1)
print(int("".join(map(str, S)))%MOD)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, Q = map(int, input().split())
S = np.ones(N)
mod = 998244353
for i in range(Q):
    L, R, D = map(int, input().split())
    S[L-1:R] = D
    print(''.join((S%mod).astype(np.int).astype(str).tolist()))

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
S = str(1)*N
MOD = 998244353

for i in range(Q):
    L, R, D = map(int, input().split())
    s = list(S)
    s[L-1:R] = str(D)*(R-L+1)
    S = "".join(s)
print(int(S)%MOD)

Submission status: Wrong Answer

Solution code:
d = input().split()
N = int(d[0])
Q = int(d[1])
S = "1" * N
for i in range(Q):
  n = input().split()
  S = S[:int(n[0])-1] + n[2] * (int(n[1])-int(n[0])+1) + S[int(n[1])-1:]
S = int(S)
print(S%998244353)

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
a="1"*N
for _ in range(Q):
    L,R,D=map(int,input().split())
    a=a[:L-1]+str(D)*(R-L+1)+a[R:]
    print(int(a))

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree():

    def __init__(self, n, f, g, h, ef, eh):
        """
        :param n: 配列の要素数
        :param f: 取得半群の元同士の積を定義
        :param g: 更新半群の元 xh が配列上の実際の値にどのように作用するかを定義
        :param h: 更新半群の元同士の積を定義　（更新半群の元を xh と表記）
        :param x: 配列の各要素の値。treeの葉以外は xf(x1,x2,...)
        """
        self.n = n
        self.f = f
        self.g = lambda xh, x: g(xh, x) if xh != eh else x
        self.h = h
        self.ef = ef
        self.eh = eh
        l = (self.n - 1).bit_length()
        self.size = 1 << l
        self.tree = [self.ef] * (self.size << 1)
        self.lazy = [self.eh] * ((self.size << 1) + 1)
        self.plt_cnt = 0

    def built(self, array):
        """
        arrayを初期値とするセグメント木を構築
        """
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.f(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """
        i 番目の要素を x に更新する
        """
        i += self.size
        self.propagate_lazy(i)
        self.tree[i] = x
        self.lazy[i] = self.eh
        self.propagate_tree(i)

    def get(self, i):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        i += self.size
        self.propagate_lazy(i)
        return self.g(self.lazy[i], self.tree[i])

    def update_range(self, l, r, x):
        """
        半開区間 [l, r) の各々の要素 a に op(x, a)を作用させる （ 0-indexed ）　（ O(logN) ）
        """
        if l >= r:
            return
        l += self.size
        r += self.size
        l0 = l//(l&-l)
        r0 = r//(r&-r)
        self.propagate_lazy(l0)
        self.propagate_lazy(r0-1)
        while l < r:
            if r&1:
                r -= 1              # 半開区間なので先に引いてる
                self.lazy[r] = self.h(x, self.lazy[r])
            if l&1:
                self.lazy[l] = self.h(x, self.lazy[l])
                l += 1
            l >>= 1
            r >>= 1
        self.propagate_tree(l0)
        self.propagate_tree(r0-1)

    def get_range(self, l, r):
        """
        [l, r)への作用の結果を返す　(0-indexed)
        """
        l += self.size
        r += self.size
        self.propagate_lazy(l//(l&-l))
        self.propagate_lazy((r//(r&-r))-1)
        res_l = self.ef
        res_r = self.ef
        while l < r:
            if l & 1:
                res_l = self.f(res_l, self.g(self.lazy[l], self.tree[l]))
                l += 1
            if r & 1:
                r -= 1
                res_r = self.f(self.g(self.lazy[r], self.tree[r]), res_r)
            l >>= 1
            r >>= 1
        return self.f(res_l, res_r)

    def max_right(self, l, z):
        """
        以下の条件を両方満たす r を(いずれか一つ)返す
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        if l >= self.n: return self.n
        l += self.size
        s = self.ef
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
                while l < self.size:
                    l *= 2
                    if z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
                        s = self.f(s, self.g(self.lazy[l], self.tree[l]))
                        l += 1
                return l - self.size
            s = self.f(s, self.g(self.lazy[l], self.tree[l]))
            l += 1
            if l & -l == l: break
        return self.n

    def min_left(self, r, z):
        """
        以下の条件を両方満たす l を(いずれか一つ)返す
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        if r <= 0: return 0
        r += self.size
        s = self.ef
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                while r < self.size:
                    r = r * 2 + 1
                    if z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                        s = self.f(self.g(self.lazy[r], self.tree[r]), s)
                        r -= 1
                return r + 1 - self.size
            s = self.f(self.g(self.lazy[r], self.tree[r]), s)
            if r & -r == r: break
        return 0

    def propagate_lazy(self, i):
        """
        lazy の値をトップダウンで更新する　（ O(logN) ）
        """
        for k in range(i.bit_length()-1,0,-1):
            x = i>>k
            if self.lazy[x] == self.eh:
                continue
            laz = self.lazy[x]
            self.lazy[(x<<1)|1] = self.h(laz, self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(laz, self.lazy[x<<1])
            self.tree[x] = self.g(laz, self.tree[x])   # get_range ではボトムアップの伝搬を行わないため、この処理をしないと tree が更新されない
            self.lazy[x] = self.eh


    def propagate_tree(self, i):
        """
        tree の値をボトムアップで更新する　（ O(logN) ）
        """
        while i>1:
            i>>=1
            self.tree[i] = self.f(self.g(self.lazy[i<<1], self.tree[i<<1]), self.g(self.lazy[(i<<1)|1], self.tree[(i<<1)|1]))

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        for x in range(1, self.size):
            if self.lazy[x] == self.eh:
                continue
            self.lazy[(x<<1)|1] = self.h(self.lazy[x], self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(self.lazy[x], self.lazy[x<<1])
            self.tree[x] = self.g(self.lazy[x], self.tree[x])
            self.lazy[x] = self.eh
        for xh, x in zip(self.lazy[self.size:self.size+self.n], self.tree[self.size:self.size+self.n]):
            yield self.g(xh,x)

    def __str__(self):
        return str(list(self))

#########################################################################################################

from itertools import accumulate
import sys
input = sys.stdin.readline

MOD = 998244353
off = 10**10

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

P = [pow(10,p,MOD) for p in range(N+1)]
SP = [0]
for p in P:
    SP.append((SP[-1]+p)%MOD)
# クエリ関数
ef = 0
def f(x, y):
    x0, x1 = divmod(x,off)
    y0, y1 = divmod(y,off)
    res = x0*P[y1]+y0
    res %= MOD
    return (res*off) + x1+y1
# merge関数
eh = -1
def h(a,b):
    return a if a != eh else b
# 更新関数（g が局所的か要確認
def g(a, x):
    x1 = x%off
    res = a*SP[x1]%MOD
    return (res*off) + x1

st = LazySegmentTree(N, f, g, h, ef, eh)

st.built([(off) + 1]*N)
res = [""]*Q
for i in range(Q):
    L, R, D = map(int, input().split())
    st.update_range(L-1, R, D)
    res[i] = str((st.get_range(0,N)//off)%MOD)
print("\n".join(res))

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree():

    def __init__(self, n, f, g, h, ef, eh):
        """
        :param n: 配列の要素数
        :param f: 取得半群の元同士の積を定義
        :param g: 更新半群の元 xh が配列上の実際の値にどのように作用するかを定義
        :param h: 更新半群の元同士の積を定義　（更新半群の元を xh と表記）
        :param x: 配列の各要素の値。treeの葉以外は xf(x1,x2,...)
        """
        self.n = n
        self.f = f
        self.g = lambda xh, x: g(xh, x) if xh != eh else x
        self.h = h
        self.ef = ef
        self.eh = eh
        l = (self.n - 1).bit_length()
        self.size = 1 << l
        self.tree = [self.ef] * (self.size << 1)
        self.lazy = [self.eh] * ((self.size << 1) + 1)
        self.plt_cnt = 0

    def built(self, array):
        """
        arrayを初期値とするセグメント木を構築
        """
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.f(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """
        i 番目の要素を x に更新する
        """
        i += self.size
        self.propagate_lazy(i)
        self.tree[i] = x
        self.lazy[i] = self.eh
        self.propagate_tree(i)

    def get(self, i):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        i += self.size
        self.propagate_lazy(i)
        return self.g(self.lazy[i], self.tree[i])

    def update_range(self, l, r, x):
        """
        半開区間 [l, r) の各々の要素 a に op(x, a)を作用させる （ 0-indexed ）　（ O(logN) ）
        """
        if l >= r:
            return
        l += self.size
        r += self.size
        l0 = l//(l&-l)
        r0 = r//(r&-r)
        self.propagate_lazy(l0)
        self.propagate_lazy(r0-1)
        while l < r:
            if r&1:
                r -= 1              # 半開区間なので先に引いてる
                self.lazy[r] = self.h(x, self.lazy[r])
            if l&1:
                self.lazy[l] = self.h(x, self.lazy[l])
                l += 1
            l >>= 1
            r >>= 1
        self.propagate_tree(l0)
        self.propagate_tree(r0-1)

    def get_range(self, l, r):
        """
        [l, r)への作用の結果を返す　(0-indexed)
        """
        l += self.size
        r += self.size
        self.propagate_lazy(l//(l&-l))
        self.propagate_lazy((r//(r&-r))-1)
        res_l = self.ef
        res_r = self.ef
        while l < r:
            if l & 1:
                res_l = self.f(res_l, self.g(self.lazy[l], self.tree[l]))
                l += 1
            if r & 1:
                r -= 1
                res_r = self.f(self.g(self.lazy[r], self.tree[r]), res_r)
            l >>= 1
            r >>= 1
        return self.f(res_l, res_r)

    def max_right(self, l, z):
        """
        以下の条件を両方満たす r を(いずれか一つ)返す
            ・r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
        """
        if l >= self.n: return self.n
        l += self.size
        s = self.ef
        while 1:
            while l % 2 == 0:
                l >>= 1
            if not z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
                while l < self.size:
                    l *= 2
                    if z(self.f(s, self.g(self.lazy[l], self.tree[l]))):
                        s = self.f(s, self.g(self.lazy[l], self.tree[l]))
                        l += 1
                return l - self.size
            s = self.f(s, self.g(self.lazy[l], self.tree[l]))
            l += 1
            if l & -l == l: break
        return self.n

    def min_left(self, r, z):
        """
        以下の条件を両方満たす l を(いずれか一つ)返す
            ・l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
            ・l = 0 or f(op(a[l - 1], a[l], ..., a[r - 1])) = false
        """
        if r <= 0: return 0
        r += self.size
        s = self.ef
        while 1:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                while r < self.size:
                    r = r * 2 + 1
                    if z(self.f(self.g(self.lazy[r], self.tree[r]), s)):
                        s = self.f(self.g(self.lazy[r], self.tree[r]), s)
                        r -= 1
                return r + 1 - self.size
            s = self.f(self.g(self.lazy[r], self.tree[r]), s)
            if r & -r == r: break
        return 0

    def propagate_lazy(self, i):
        """
        lazy の値をトップダウンで更新する　（ O(logN) ）
        """
        for k in range(i.bit_length()-1,0,-1):
            x = i>>k
            if self.lazy[x] == self.eh:
                continue
            laz = self.lazy[x]
            self.lazy[(x<<1)|1] = self.h(laz, self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(laz, self.lazy[x<<1])
            self.tree[x] = self.g(laz, self.tree[x])   # get_range ではボトムアップの伝搬を行わないため、この処理をしないと tree が更新されない
            self.lazy[x] = self.eh


    def propagate_tree(self, i):
        """
        tree の値をボトムアップで更新する　（ O(logN) ）
        """
        while i>1:
            i>>=1
            self.tree[i] = self.f(self.g(self.lazy[i<<1], self.tree[i<<1]), self.g(self.lazy[(i<<1)|1], self.tree[(i<<1)|1]))

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        for x in range(1, self.size):
            if self.lazy[x] == self.eh:
                continue
            self.lazy[(x<<1)|1] = self.h(self.lazy[x], self.lazy[(x<<1)|1])
            self.lazy[x<<1] = self.h(self.lazy[x], self.lazy[x<<1])
            self.tree[x] = self.g(self.lazy[x], self.tree[x])
            self.lazy[x] = self.eh
        for xh, x in zip(self.lazy[self.size:self.size+self.n], self.tree[self.size:self.size+self.n]):
            yield self.g(xh,x)

    def __str__(self):
        return str(list(self))

#########################################################################################################

from itertools import accumulate
import sys
input = sys.stdin.readline

MOD = 998244353
off = 10**10

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

P = [pow(10,p,MOD) for p in range(N+1)]
SP = [0]
for p in P:
    SP.append((SP[-1]+p)%MOD)
# クエリ関数
ef = 0
def f(x, y):
    x0, x1 = divmod(x,off)
    y0, y1 = divmod(y,off)
    res = x0*P[y1]+y0
    res %= MOD
    return (res*off) + x1+y1
# merge関数
eh = -1
def h(a,b):
    return a if a != eh else b
# 更新関数（g が局所的か要確認
def g(a, x):
    x0, x1 = divmod(x,off)
    return a*SP[x1]%MOD*off + x1

st = LazySegmentTree(N, f, g, h, ef, eh)

st.built([(off) + 1]*N)
for _ in range(Q):
    L, R, D = map(int, input().split())
    st.update_range(L-1, R, D)
    print((st.get_range(0,N)//off)%MOD)