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:
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]+list(accumulate(P))
# クエリ関数
ef = 0
def f(x, y):
    x0, x1 = divmod(x,off)
    y0, y1 = divmod(y,off)
    res = x0*P[y1]%MOD+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)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
import sys
input = sys.stdin.readline
from itertools import accumulate
from functools import reduce
N,Q = map(int,input().split())
LRD = [list(map(int,input().split())) for i in range(Q)]

#import random
#N,Q = 200000,200000
#LRD = []
#for i in range(Q):
    #l,r = sorted([random.randint(1,N), random.randint(1,N)])
    #d = random.randint(1,9)
    #LRD.append([l,r,d])

L = 2**((N-1).bit_length())
R = L-N
r1 = [1]
s1 = [1]
for i in range(L+1):
    r1.append((r1[-1]*10) % MOD)
    s1.append((s1[-1]*10+1) % MOD)

class LazySegmentTree2:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.L = 2**((N-1).bit_length())
        self.data = [default]*self.L + data + [default]*(self.L-N)
        self.dono = lambda x : x
        self.lazy = [self.dono for i in range(self.L * 2)]
        for i in range(self.L-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def upper(self,target):
        res = set()
        for t in target:
            t >>= 1
            while t:
                if t in res:
                    break
                res.add(t)
                t >>= 1
        return sorted(res)

    def update(self,u):
        if not self.lazy[u] == self.dono:
            if u < self.L:
                self.lazy[2*u] = self.lazy[u]
                self.lazy[2*u+1] = self.lazy[u]
            self.data[u] = self.lazy[u](self.data[u])
            self.lazy[u] = self.dono

    def set(self,i,j,f):
        i += self.L
        j += self.L
        target = []
        while j-i > 0:
            if i & 1:
                target.append(i)
                i += 1
            if j & 1:
                target.append(j-1)
                j -= 1
            i, j = i//2, j//2
        upper = self.upper(target)
        for u in upper:
            if not self.lazy[u] == self.dono:
                self.lazy[2*u] = self.lazy[u]
                self.lazy[2*u+1] = self.lazy[u]
                self.lazy[u] = self.dono
        for t in target:
            self.lazy[t] = f
        for u in upper[::-1]:
            self.update(2*u)
            self.update(2*u+1)
            self.data[u] = self.op(self.data[2*u], self.data[2*u+1])

    def get(self,i,j):
        i += self.L
        j += self.L
        rs = []
        ls = []
        rv = self.default
        lv = self.default
        while j-i > 0:
            if i & 1:
                self.update(i)
                rv = self.op(rv,self.data[i])
                rs.append(i)
                i += 1
            if j & 1:
                self.update(j-1)
                lv = self.op(self.data[j-1],lv)
                ls.append(j-1)
                j -= 1
            i, j = i//2, j//2
        upper = self.upper(rs+ls)
        [self.update(u) for u in upper]
        return self.op(rv, lv)


def op(x,y):
    return (x[0]*r1[y[1]] + y[0]) % MOD, x[1]+y[1]

ones = [(1,1)]*N
ones = [(0,1)]*R + ones
seg = LazySegmentTree2(ones, op, (0,0))

ans = []
for l,r,d in LRD:
    l,r = l+R,r+R
    seg.set(l-1,r,lambda x, d=d: (d*s1[x[1]-1],x[1]))
    ans.append(seg.data[1][0])
    #ans.append(seg.get(0,L)[0])

[print(a) for a in ans]

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
import sys
input = sys.stdin.readline
from itertools import accumulate
from functools import reduce
N,Q = map(int,input().split())
LRD = [list(map(int,input().split())) for i in range(Q)]

#import random
#N,Q = 200000,150000
#LRD = []
#for i in range(Q):
#    l,r = sorted([random.randint(1,N), random.randint(1,N)])
#    d = random.randint(1,9)
#    LRD.append([l,r,d])

class LazySegmentTree2:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.L = 2**((N-1).bit_length())
        self.data = [default]*self.L + data + [default]*(self.L-N)
        self.dono = lambda x : x
        self.lazy = [self.dono for i in range(self.L * 2)]
        for i in range(self.L-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def upper(self,target):
        res = set()
        for t in target:
            t >>= 1
            while t:
                if t in res:
                    break
                res.add(t)
                t >>= 1
        return sorted(res)

    def update(self,u):
        if not self.lazy[u] == self.dono:
            if u < self.L:
                self.lazy[2*u] = self.lazy[u]
                self.lazy[2*u+1] = self.lazy[u]
            self.data[u] = self.lazy[u](self.data[u])
            self.lazy[u] = self.dono

    def set(self,i,j,f):
        i += self.L
        j += self.L
        target = []
        while j-i > 0:
            if i & 1:
                target.append(i)
                i += 1
            if j & 1:
                target.append(j-1)
                j -= 1
            i, j = i//2, j//2
        upper = self.upper(target)
        for u in upper:
            if not self.lazy[u] == self.dono:
                self.lazy[2*u] = self.lazy[u]
                self.lazy[2*u+1] = self.lazy[u]
                self.lazy[u] = self.dono
        for t in target:
            if t < self.L:
                self.lazy[2*t] = f
                self.lazy[2*t+1] = f
            self.lazy[t] = self.dono 
            self.data[t] = f(self.data[t])
            #self.lazy[t] = f
            #self.update(t)
        for u in upper[::-1]:
            self.update(2*u)
            self.update(2*u+1)
            self.data[u] = self.op(self.data[2*u], self.data[2*u+1])

    def get(self,i,j):
        i += self.L
        j += self.L
        rs = []
        ls = []
        rv = self.default
        lv = self.default
        while j-i > 0:
            if i & 1:
                self.update(i)
                rv = self.op(rv,self.data[i])
                rs.append(i)
                i += 1
            if j & 1:
                self.update(j-1)
                lv = self.op(self.data[j-1],lv)
                ls.append(j-1)
                j -= 1
            i, j = i//2, j//2
        upper = self.upper(rs+ls)
        [self.update(u) for u in upper]
        return self.op(rv, lv)

L = 2**((N-1).bit_length())
R = L-N
ones = [(1,1)]*N
ones = [(0,1)]*R + ones

r1 = [1]
s1 = [1]
for i in range(L+1):
    r1.append((r1[-1]*10) % MOD)
    s1.append((s1[-1]*10+1) % MOD)

def op(x,y):
    d = x[1] + y[1]
    m = (x[0]*r1[y[1]] + y[0]) % MOD
    return m,d

seg = LazySegmentTree2(ones, op, (0,0))

ans = []
for l,r,d in LRD:
    l,r = l+R,r+R
    seg.set(l-1,r,lambda x, d=d: (d*s1[x[1]-1],x[1]))
    ans.append(seg.data[1][0])
    #ans.append(seg.get(0,L)[0])

[print(a) for a in ans]

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree():
    def __init__(self, array, f, g, h, ti, ei):
        self.f = f
        self.g = g
        self.h = h
        self.ti = ti
        self.ei = ei
        self.height = height = len(array).bit_length()
        self.n = n = 2**height
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        self.laz = [ei] * (2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])
 
    def reflect(self, k):
        # 遅延配列の値から真のノードの値を求める
        dat = self.dat
        ei = self.ei
        laz = self.laz
        g = self.g
        return self.dat[k] if laz[k] is ei else g(dat[k], laz[k])
 
    def evaluate(self, k):
        # 遅延配列を子ノードに伝播させる
        laz = self.laz
        ei = self.ei
        reflect = self.reflect
        dat = self.dat
        h = self.h
        if laz[k] is ei:
            return
        laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k])
        laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k])
        dat[k] = reflect(k)
        laz[k] = ei
 
    def thrust(self, k):
        height = self.height
        evaluate = self.evaluate
        for i in range(height, 0, -1):
            evaluate(k >> i)
 
    def recalc(self, k):
        dat = self.dat
        reflect = self.reflect
        f = self.f
        while k:
            k >>= 1
            dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1))
 
    def update(self, a, b, x):
        # 半開区間[a,b)の遅延配列の値をxに書き換える
        thrust = self.thrust
        n = self.n
        h = self.h
        laz = self.laz
        recalc = self.recalc
        a += n
        b += n - 1
        l = a
        r = b + 1
        thrust(a)
        thrust(b)
        while l < r:
            if l & 1:
                laz[l] = h(laz[l], x)
                l += 1
            if r & 1:
                r -= 1
                laz[r] = h(laz[r], x)
            l >>= 1
            r >>= 1
        recalc(a)
        recalc(b)
 
    def set_val(self, a, x):
        # aの値を変更する
        n = self.n
        thrust = self.thrust
        dat = self.dat
        laz = self.laz
        recalc = self.recalc
        ei = self.ei
        a += n
        thrust(a)
        dat[a] = x
        laz[a] = ei
        recalc(a)
 
    def query(self, a, b):
        # 半開区間[a,b)に対するクエリに答える
        f = self.f
        ti = self.ti
        n = self.n
        thrust = self.thrust
        reflect = self.reflect
        a += n
        b += n - 1
        thrust(a)
        thrust(b)
        l = a
        r = b + 1
        vl = vr = ti
        while l < r:
            if l & 1:
                vl = f(vl, reflect(l))
                l += 1
            if r & 1:
                r -= 1
                vr = f(reflect(r), vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)
    
def pow_k(x,n,p=10**9+7):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=(K*x)%p
        x=(x*x)%p
        n//=2
    return (K*x)%p

mod=998244353
inv9=pow_k(9,mod-2,mod)
def f(a, b):
    an,ah=divmod(a,H)
    bn,bh=divmod(b,H)
    return ((an*pow_k(10,bh,mod)+bn)%mod)*H + ah+bh
 
def g(a, b):
    ah=a%H
    return (((pow_k(10,ah,mod)-1)*inv9)%mod*b)*H + ah

h = lambda a, b: b
ti = 0
ei = 0

import sys
input = sys.stdin.readline
MI=lambda:map(int,input().split())
N,Q=MI()
H=10**9+7
lst=LazySegmentTree([1*H+1]*N,f=f,g=g,h=h,ti=ti,ei=ei)

for _ in [0]*Q:
    l,r,d=MI()
    lst.update(l-1,r,d)
    print(lst.query(0,N)//H)

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree():
    def __init__(self, array, f, g, h, ti, ei):
        self.f = f
        self.g = g
        self.h = h
        self.ti = ti
        self.ei = ei
        self.height = height = len(array).bit_length()
        self.n = n = 2**height
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        self.laz = [ei] * (2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])
 
    def reflect(self, k):
        # 遅延配列の値から真のノードの値を求める
        dat = self.dat
        ei = self.ei
        laz = self.laz
        g = self.g
        return self.dat[k] if laz[k] is ei else g(dat[k], laz[k])
 
    def evaluate(self, k):
        # 遅延配列を子ノードに伝播させる
        laz = self.laz
        ei = self.ei
        reflect = self.reflect
        dat = self.dat
        h = self.h
        if laz[k] is ei:
            return
        laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k])
        laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k])
        dat[k] = reflect(k)
        laz[k] = ei
 
    def thrust(self, k):
        height = self.height
        evaluate = self.evaluate
        for i in range(height, 0, -1):
            evaluate(k >> i)
 
    def recalc(self, k):
        dat = self.dat
        reflect = self.reflect
        f = self.f
        while k:
            k >>= 1
            dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1))
 
    def update(self, a, b, x):
        # 半開区間[a,b)の遅延配列の値をxに書き換える
        thrust = self.thrust
        n = self.n
        h = self.h
        laz = self.laz
        recalc = self.recalc
        a += n
        b += n - 1
        l = a
        r = b + 1
        thrust(a)
        thrust(b)
        while l < r:
            if l & 1:
                laz[l] = h(laz[l], x)
                l += 1
            if r & 1:
                r -= 1
                laz[r] = h(laz[r], x)
            l >>= 1
            r >>= 1
        recalc(a)
        recalc(b)
 
    def set_val(self, a, x):
        # aの値を変更する
        n = self.n
        thrust = self.thrust
        dat = self.dat
        laz = self.laz
        recalc = self.recalc
        ei = self.ei
        a += n
        thrust(a)
        dat[a] = x
        laz[a] = ei
        recalc(a)
 
    def query(self, a, b):
        # 半開区間[a,b)に対するクエリに答える
        f = self.f
        ti = self.ti
        n = self.n
        thrust = self.thrust
        reflect = self.reflect
        a += n
        b += n - 1
        thrust(a)
        thrust(b)
        l = a
        r = b + 1
        vl = vr = ti
        while l < r:
            if l & 1:
                vl = f(vl, reflect(l))
                l += 1
            if r & 1:
                r -= 1
                vr = f(reflect(r), vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)
    
def pow_k(x,n,p=10**9+7):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=(K*x)%p
        x=(x*x)%p
        n//=2
    return (K*x)%p

mod=998244353
inv9=pow_k(9,mod-2,mod)
def f(a, b):
    an,ah=a
    bn,bh=b
    return ((an*pow_k(10,bh,mod)+bn)%mod,ah+bh)
 
def g(a, b):
    an,ah=a
    return (((pow_k(10,ah,mod)-1)*inv9)%mod*b,ah)

h = lambda a, b: b
ti = (0,0)
ei = 0

import sys
input = sys.stdin.readline
MI=lambda:map(int,input().split())
N,Q=MI()
lst=LazySegmentTree([(1,1)]*N,f=f,g=g,h=h,ti=ti,ei=ei)

for _ in [0]*Q:
    l,r,d=MI()
    lst.update(l-1,r,d)
    print(lst.query(0,N)[0])

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree():
    def __init__(self, array, f, g, h, ti, ei):
        self.f = f
        self.g = g
        self.h = h
        self.ti = ti
        self.ei = ei
        self.height = height = len(array).bit_length()
        self.n = n = 2**height
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        self.laz = [ei] * (2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])
 
    def reflect(self, k):
        # 遅延配列の値から真のノードの値を求める
        dat = self.dat
        ei = self.ei
        laz = self.laz
        g = self.g
        return self.dat[k] if laz[k] is ei else g(dat[k], laz[k])
 
    def evaluate(self, k):
        # 遅延配列を子ノードに伝播させる
        laz = self.laz
        ei = self.ei
        reflect = self.reflect
        dat = self.dat
        h = self.h
        if laz[k] is ei:
            return
        laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k])
        laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k])
        dat[k] = reflect(k)
        laz[k] = ei
 
    def thrust(self, k):
        height = self.height
        evaluate = self.evaluate
        for i in range(height, 0, -1):
            evaluate(k >> i)
 
    def recalc(self, k):
        dat = self.dat
        reflect = self.reflect
        f = self.f
        while k:
            k >>= 1
            dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1))
 
    def update(self, a, b, x):
        # 半開区間[a,b)の遅延配列の値をxに書き換える
        thrust = self.thrust
        n = self.n
        h = self.h
        laz = self.laz
        recalc = self.recalc
        a += n
        b += n - 1
        l = a
        r = b + 1
        thrust(a)
        thrust(b)
        while l < r:
            if l & 1:
                laz[l] = h(laz[l], x)
                l += 1
            if r & 1:
                r -= 1
                laz[r] = h(laz[r], x)
            l >>= 1
            r >>= 1
        recalc(a)
        recalc(b)
 
    def set_val(self, a, x):
        # aの値を変更する
        n = self.n
        thrust = self.thrust
        dat = self.dat
        laz = self.laz
        recalc = self.recalc
        ei = self.ei
        a += n
        thrust(a)
        dat[a] = x
        laz[a] = ei
        recalc(a)
 
    def query(self, a, b):
        # 半開区間[a,b)に対するクエリに答える
        f = self.f
        ti = self.ti
        n = self.n
        thrust = self.thrust
        reflect = self.reflect
        a += n
        b += n - 1
        thrust(a)
        thrust(b)
        l = a
        r = b + 1
        vl = vr = ti
        while l < r:
            if l & 1:
                vl = f(vl, reflect(l))
                l += 1
            if r & 1:
                r -= 1
                vr = f(reflect(r), vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)
    
def pow_k(x,n,p=10**9+7):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=(K*x)%p
        x=(x*x)%p
        n//=2
    return (K*x)%p

mod=998244353
def f(a, b):
    an,ah=a
    bn,bh=b
    return ((an*pow_k(10,bh,mod)+bn)%mod,ah+bh)
 
def g(a, b):
    an,ah=a
    b*((pow_k(10,4,mod)-1)*443664157)%mod
    return (b*int('1'*ah),ah)

h = lambda a, b: b
ti = (0,0)
ei = 0

import sys
input = sys.stdin.readline
MI=lambda:map(int,input().split())
N,Q=MI()
lst=LazySegmentTree([(1,1)]*N,f=f,g=g,h=h,ti=ti,ei=ei)

for _ in [0]*Q:
    l,r,d=MI()
    lst.update(l-1,r,d)
    print(lst.query(0,N)[0])

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree():
    def __init__(self, array, f, g, h, ti, ei):
        self.f = f
        self.g = g
        self.h = h
        self.ti = ti
        self.ei = ei
        self.height = height = len(array).bit_length()
        self.n = n = 2**height
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        self.laz = [ei] * (2 * n)
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])
 
    def reflect(self, k):
        # 遅延配列の値から真のノードの値を求める
        dat = self.dat
        ei = self.ei
        laz = self.laz
        g = self.g
        return self.dat[k] if laz[k] is ei else g(dat[k], laz[k])
 
    def evaluate(self, k):
        # 遅延配列を子ノードに伝播させる
        laz = self.laz
        ei = self.ei
        reflect = self.reflect
        dat = self.dat
        h = self.h
        if laz[k] is ei:
            return
        laz[(k << 1) | 0] = h(laz[(k << 1) | 0], laz[k])
        laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k])
        dat[k] = reflect(k)
        laz[k] = ei
 
    def thrust(self, k):
        height = self.height
        evaluate = self.evaluate
        for i in range(height, 0, -1):
            evaluate(k >> i)
 
    def recalc(self, k):
        dat = self.dat
        reflect = self.reflect
        f = self.f
        while k:
            k >>= 1
            dat[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1))
 
    def update(self, a, b, x):
        # 開区間[a,b)の遅延配列の値をxに書き換える
        thrust = self.thrust
        n = self.n
        h = self.h
        laz = self.laz
        recalc = self.recalc
        a += n
        b += n - 1
        l = a
        r = b + 1
        thrust(a)
        thrust(b)
        while l < r:
            if l & 1:
                laz[l] = h(laz[l], x)
                l += 1
            if r & 1:
                r -= 1
                laz[r] = h(laz[r], x)
            l >>= 1
            r >>= 1
        recalc(a)
        recalc(b)
 
    def set_val(self, a, x):
        # aの値を変更する
        n = self.n
        thrust = self.thrust
        dat = self.dat
        laz = self.laz
        recalc = self.recalc
        ei = self.ei
        a += n
        thrust(a)
        dat[a] = x
        laz[a] = ei
        recalc(a)
 
    def query(self, a, b):
        # 開区間[a,b)に対するクエリに答える
        f = self.f
        ti = self.ti
        n = self.n
        thrust = self.thrust
        reflect = self.reflect
        a += n
        b += n - 1
        thrust(a)
        thrust(b)
        l = a
        r = b + 1
        vl = vr = ti
        while l < r:
            if l & 1:
                vl = f(vl, reflect(l))
                l += 1
            if r & 1:
                r -= 1
                vr = f(reflect(r), vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)
    
def pow_k(x,n,p=10**9+7):
    if n==0:
        return 1
    K=1
    while n>1:
        if n%2!=0:
            K=(K*x)%p
        x=(x*x)%p
        n//=2
    return (K*x)%p

mod=998244353
def f(a, b):
    an,ah=a
    bn,bh=b
    return ((an*pow_k(10,bh,mod)+bn)%mod,ah+bh)
 
def g(a, b):
    an,ah=a
    return (b*int('1'*ah),ah)

h = lambda a, b: b
ti = (0,0)
ei = 0

import sys
input = sys.stdin.readline
MI=lambda:map(int,input().split())
N,Q=MI()
lst=LazySegmentTree([(1,1)]*N,f=f,g=g,h=h,ti=ti,ei=ei)

for _ in [0]*Q:
    l,r,d=MI()
    lst.update(l-1,r,d)
    print(lst.query(0,N)[0])