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:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class LazySegmentTree:
        
        __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]
    
        def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
            self.me = monoid_identity
            self.oe = operator_identity
            self.fmm = func_monoid_monoid
            self.fmo = func_monoid_operator
            self.foo = func_operator_operator
    
            self.n = len(monoid_data)
            self.data = monoid_data * 2
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
            self.lazy = [self.oe] * (self.n * 2)
            
    
        def replace(self, index, value):
            index += self.n
    
            # propagation
            for shift in range(index.bit_length()-1, 0, -1):
                i = index >> shift
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            # update
            self.data[index] = value
            self.lazy[index] = self.oe
    
            # recalculation
            i = index
            while i > 1:
                i //= 2
                self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
                self.lazy[i] = self.oe
    
    
        def effect(self, l, r, operator):
            l += self.n
            r += self.n
            
            # preparing indices
            indices = []
            l0 = (l // (l & -l))     // 2
            r0 = (r // (r & -r) - 1) // 2
            while r0 > l0:
                indices.append(r0)
                r0 //= 2
            while l0 > r0:
                indices.append(l0)
                l0 //= 2
            while l0 and l0 != r0:
                indices.append(r0)
                r0 //= 2
                if l0 == r0:
                    break
                indices.append(l0)
                l0 //= 2
            while r0:
                indices.append(r0)
                r0 //= 2
    
            # propagation
            for i in reversed(indices):
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            # effect
            while l < r:
                if l % 2:
                    self.lazy[l] = self.foo(self.lazy[l], operator)
                    l += 1
                if r % 2:
                    r -= 1
                    self.lazy[r] = self.foo(self.lazy[r], operator)
                l //= 2
                r //= 2
    
            # recalculation
            for i in indices:
                self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
                self.lazy[i] = self.oe
                
            
        def folded(self, l, r):
            l += self.n
            r += self.n
    
            # preparing indices
            indices = []
            l0 = (l // (l & -l))     // 2
            r0 = (r // (r & -r) - 1) // 2
            while r0 > l0:
                indices.append(r0)
                r0 //= 2
            while l0 > r0:
                indices.append(l0)
                l0 //= 2
            while l0 and l0 != r0:
                indices.append(r0)
                r0 //= 2
                if l0 == r0:
                    break
                indices.append(l0)
                l0 //= 2
            while r0:
                indices.append(r0)
                r0 //= 2
            
            # propagation
            for i in reversed(indices):
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            # fold
            left_folded = self.me
            right_folded = self.me
            while l < r:
                if l % 2:
                    left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                    l += 1
                if r % 2:
                    r -= 1
                    right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
                l //= 2
                r //= 2
            return self.fmm(left_folded, right_folded)


    mod=998244353
    N,Q=MI()
    
    POW=[1]
    for _ in range(N+5):
        a=POW[-1]
        a*=10
        a%=mod
        POW.append(a)
        
    inv9=pow(9,mod-2,mod)#9でわる
        
    MM=32
    mask=(1<<MM)-1
    # (数，今見てる数の桁数)を1つにまとめる
    def enc(a,d):
        return (a<<MM) + d
    
    def dec(v):
        a=v>>MM
        d=v&mask
        return a,d
    
    mide=enc(1,1)
    monoid_data=[mide]*N

        
    monoid_ide=0#0を足したいからこれで
    ope_ide=0
    
    def fmm(m1,m2):
        # print(m1,m2)
        a1,d1=dec(m1)
        a2,d2=dec(m2)
        
        # print(a1,d1,a2,d2)
        
        temp=a1*POW[d2]+a2
        
        return enc(temp%mod,d1+d2)#桁数は足せば良い
    
    def fmo(m1,o1):
        if o1:
            # o1がd1桁だけ続くものを返したい
            a1,d1=dec(m1)
            
            temp=((POW[d1]-1)*inv9)%mod#1がd1桁
            return enc(o1*temp,d1)
        else:
            return m1
    
    def foo(o1,o2):
        if o2:
            return o2
        else:
            return o1
    
    Lseg=LazySegmentTree(monoid_data,monoid_ide,ope_ide,fmm,fmo,foo)
    
    for _ in range(Q):
        # print("---")
        l,r,d=MI()
        l-=1
        r-=1
        Lseg.effect(l,r+1,d)
        ans=Lseg.folded(0,N)
        a,d=dec(ans)
        print(a)
    
    
    

        



main()

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class LazySegmentTree:
        
        __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]
    
        def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
            self.me = monoid_identity
            self.oe = operator_identity
            self.fmm = func_monoid_monoid
            self.fmo = func_monoid_operator
            self.foo = func_operator_operator
    
            self.n = len(monoid_data)
            self.data = monoid_data * 2
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
            self.lazy = [self.oe] * (self.n * 2)
            
    
        def replace(self, index, value):
            index += self.n
    
            # propagation
            for shift in range(index.bit_length()-1, 0, -1):
                i = index >> shift
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            # update
            self.data[index] = value
            self.lazy[index] = self.oe
    
            # recalculation
            i = index
            while i > 1:
                i //= 2
                self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
                self.lazy[i] = self.oe
    
    
        def effect(self, l, r, operator):
            l += self.n
            r += self.n
            
            # preparing indices
            indices = []
            l0 = (l // (l & -l))     // 2
            r0 = (r // (r & -r) - 1) // 2
            while r0 > l0:
                indices.append(r0)
                r0 //= 2
            while l0 > r0:
                indices.append(l0)
                l0 //= 2
            while l0 and l0 != r0:
                indices.append(r0)
                r0 //= 2
                if l0 == r0:
                    break
                indices.append(l0)
                l0 //= 2
            while r0:
                indices.append(r0)
                r0 //= 2
    
            # propagation
            for i in reversed(indices):
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            # effect
            while l < r:
                if l % 2:
                    self.lazy[l] = self.foo(self.lazy[l], operator)
                    l += 1
                if r % 2:
                    r -= 1
                    self.lazy[r] = self.foo(self.lazy[r], operator)
                l //= 2
                r //= 2
    
            # recalculation
            for i in indices:
                self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
                self.lazy[i] = self.oe
                
            
        def folded(self, l, r):
            l += self.n
            r += self.n
    
            # preparing indices
            indices = []
            l0 = (l // (l & -l))     // 2
            r0 = (r // (r & -r) - 1) // 2
            while r0 > l0:
                indices.append(r0)
                r0 //= 2
            while l0 > r0:
                indices.append(l0)
                l0 //= 2
            while l0 and l0 != r0:
                indices.append(r0)
                r0 //= 2
                if l0 == r0:
                    break
                indices.append(l0)
                l0 //= 2
            while r0:
                indices.append(r0)
                r0 //= 2
            
            # propagation
            for i in reversed(indices):
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            # fold
            left_folded = self.me
            right_folded = self.me
            while l < r:
                if l % 2:
                    left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                    l += 1
                if r % 2:
                    r -= 1
                    right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
                l //= 2
                r //= 2
            return self.fmm(left_folded, right_folded)


    mod=998244353
    N,Q=MI()
    
    POW=[1]
    for _ in range(N+5):
        a=POW[-1]
        a*=10
        a%=mod
        POW.append(a)
        
    inv9=pow(9,mod-2,mod)#9でわる
        
        
    # (数，今見てる数の桁数)
    monoid_data=[[1,1]for _ in range(N)]

        
    monoid_ide=[0,0]#0を足したいからこれで
    ope_ide=0
    
    def fmm(m1,m2):
        # print(m1,m2)
        a1,d1=m1
        a2,d2=m2
        
        temp=a1*POW[d2]+a2
        
        return [temp%mod,d1+d2]#桁数は足せば良い
    
    def fmo(m1,o1):
        if o1:
            # o1がd1桁だけ続くものを返したい
            a1,d1=m1
            
            temp=((POW[d1]-1)*inv9)%mod#1がd1桁
            return [o1*temp,d1]
        else:
            return m1
    
    def foo(o1,o2):
        if o2:
            return o2
        else:
            return o1
    
    Lseg=LazySegmentTree(monoid_data,monoid_ide,ope_ide,fmm,fmo,foo)
    
    for _ in range(Q):
        # print("---")
        l,r,d=MI()
        l-=1
        r-=1
        Lseg.effect(l,r+1,d)
        ans=Lseg.folded(0,N)
        print(ans[0])
    
    
    

        



main()

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class LazySegmentTree:
        
        __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]
    
        def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
            self.me = monoid_identity
            self.oe = operator_identity
            self.fmm = func_monoid_monoid
            self.fmo = func_monoid_operator
            self.foo = func_operator_operator
    
            self.n = len(monoid_data)
            self.data = monoid_data * 2
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
            self.lazy = [self.oe] * (self.n * 2)
            
    
        def replace(self, index, value):
            index += self.n
    
            # propagation
            for shift in range(index.bit_length()-1, 0, -1):
                i = index >> shift
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            # update
            self.data[index] = value
            self.lazy[index] = self.oe
    
            # recalculation
            i = index
            while i > 1:
                i //= 2
                self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
                self.lazy[i] = self.oe
    
    
        def effect(self, l, r, operator):
            l += self.n
            r += self.n
            
            # preparing indices
            indices = []
            l0 = (l // (l & -l))     // 2
            r0 = (r // (r & -r) - 1) // 2
            while r0 > l0:
                indices.append(r0)
                r0 //= 2
            while l0 > r0:
                indices.append(l0)
                l0 //= 2
            while l0 and l0 != r0:
                indices.append(r0)
                r0 //= 2
                if l0 == r0:
                    break
                indices.append(l0)
                l0 //= 2
            while r0:
                indices.append(r0)
                r0 //= 2
    
            # propagation
            for i in reversed(indices):
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            # effect
            while l < r:
                if l % 2:
                    self.lazy[l] = self.foo(self.lazy[l], operator)
                    l += 1
                if r % 2:
                    r -= 1
                    self.lazy[r] = self.foo(self.lazy[r], operator)
                l //= 2
                r //= 2
    
            # recalculation
            for i in indices:
                self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
                self.lazy[i] = self.oe
                
            
        def folded(self, l, r):
            l += self.n
            r += self.n
    
            # preparing indices
            indices = []
            l0 = (l // (l & -l))     // 2
            r0 = (r // (r & -r) - 1) // 2
            while r0 > l0:
                indices.append(r0)
                r0 //= 2
            while l0 > r0:
                indices.append(l0)
                l0 //= 2
            while l0 and l0 != r0:
                indices.append(r0)
                r0 //= 2
                if l0 == r0:
                    break
                indices.append(l0)
                l0 //= 2
            while r0:
                indices.append(r0)
                r0 //= 2
            
            # propagation
            for i in reversed(indices):
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            # fold
            left_folded = self.me
            right_folded = self.me
            while l < r:
                if l % 2:
                    left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                    l += 1
                if r % 2:
                    r -= 1
                    right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
                l //= 2
                r //= 2
            return self.fmm(left_folded, right_folded)


    mod=998244353
    N,Q=MI()
    
    POW=[1]
    for _ in range(N*10+5):
        a=POW[-1]
        a*=10
        a%=mod
        POW.append(a)
        
    inv9=pow(9,mod-2,mod)#9でわる
        
        
    # (数，今見てる数の桁数)
    monoid_data=[[1,1]for _ in range(N)]

        
    monoid_ide=[0,0]#0を足したいからこれで
    ope_ide=0
    
    def fmm(m1,m2):
        # print(m1,m2)
        a1,d1=m1
        a2,d2=m2
        
        temp=a1*POW[d2]+a2
        
        return [temp%mod,d1+d2]#桁数は足せば良い
    
    def fmo(m1,o1):
        if o1:
            # o1がd1桁だけ続くものを返したい
            a1,d1=m1
            
            temp=((POW[d1]-1)*inv9)%mod#1がd1桁
            return [o1*temp,d1]
        else:
            return m1
    
    def foo(o1,o2):
        if o2:
            return o2
        else:
            return o1
    
    Lseg=LazySegmentTree(monoid_data,monoid_ide,ope_ide,fmm,fmo,foo)
    
    for _ in range(Q):
        # print("---")
        l,r,d=MI()
        l-=1
        r-=1
        Lseg.effect(l,r+1,d)
        ans=Lseg.folded(0,N)
        print(ans[0])
    
    
    

        



main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
import math
# from itertools import product, accumulate, combinations, product
#import bisect
# import numpy as np
# from copy import deepcopy
#from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())


class lazy_segtree:
    '''init_val : i-indexed (init_val[0] = self.bin[1])'''
    def __init__(self, n, mod, init = 0, init_val=None):
        self.n = n
        self.init = init
        self.k = math.ceil(math.log2(n))
        self.add_val = 1 << self.k
        self.lazy = [INF] * (1 << (self.k + 1))
        self.bins = [self.init] * (1 << (self.k + 1))
        if init_val != None:
            self.update_set(init_val)
        self.mod = mod

        self.build()
        self.bases = self.bins.copy()

    def __getitem__(self, idx):  # return idx-value
        return self.bins[idx]

    def __setitem__(self, idx, val):
        self.bins[idx] = val

    def update_set(self, vals):
        for idx, i in enumerate(range(self.add_val, self.add_val * 2)):
            if len(vals) > idx:
                self[i] = vals[idx]
            else:continue

    def _func(self, k):
        def f(x):
            return k
        return f

    def fx(self, l, r):
        return (l + r) % self.mod

    def build(self):
        '''cliculate segtree (after update_set)'''
        for i in range(self.add_val - 1, 0 , -1):
            self[i] = self.fx(self[2*i], self[2*i+1])

    def eval(self, idx):
        '''update lazies'''
        if self.lazy[idx] == INF:
            return
        if idx < self.add_val:
            self.lazy[idx * 2 + 1] = self.lazy[idx]
            self.lazy[idx * 2] = self.lazy[idx]
        self[idx] = self.lazy[idx] * self.bases[idx]
        self.lazy[idx] = INF

    def update(self, a, b, x):
        '''[a, b) -> f_x(.)'''
        self._update(a, b, x, 1, 0, self.add_val)

    def _update(self, a, b, x, k, l, r):
        '''update, Recursive from head'''
        self.eval(k)
        if a <= l and b >= r:
            self.lazy[k] = self._func(x)(self.lazy[k])
            self.eval(k)
        elif a < r and l < b:
            self._update(a, b, x, 2 * k, l, (l + r) // 2)
            self._update(a, b, x, 2 * k + 1, (l + r) // 2, r)
            self[k] = self.fx(self[2 * k], self[2 * k + 1])


    def query(self, a, b):
        '''区間値[a, b)'''
        return self.query_sub(a, b, 1, 0, self.add_val)

    def query_sub(self, a, b, k, l, r):
        '''self.bin[k] = [l, r) 内での[a,b]の区間値'''
        self.eval(k)
        if r <= a or b <= l:
            return INF
        elif a <= l and b >= r:
            return self[k]
        else:
            vl = self.query_sub(a, b, k * 2, l, (l+r) // 2)
            vr = self.query_sub(a, b, k * 2 + 1, (l+r) // 2, r)
            return self.fx(vl, vr)

def get_powmod(x, k, mod):
    ret = [1]
    v = 1
    for i in range(k):
        v *= x
        v %= mod
        ret.append(v)
    return ret

def run():
    N, Q = mapline()
    A = get_powmod(10, N-1, mod)[::-1]
    #print(A)
    lst = lazy_segtree(N, mod, init_val = A)
    #print(lst.bins)
    for _ in range(Q):
        l, r, d = mapline()
        l -= 1
        r -= 1
        lst.update(l, r + 1, d)
        #print(lst.lazy)
        print(lst[1])

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
class LazySegmentTree():
    def __init__(self, n, op, e, mapping, composition, id):
        self.n = n
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.id = id
        self.log = (n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [e] * (2 * self.size)
        self.lz = [id] * (self.size)

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

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

    def push(self, k):
        self.all_apply(2 * k, self.lz[k])
        self.all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.id

    def build(self, arr):
        #assert len(arr) == self.n
        for i, a in enumerate(arr):
            self.d[self.size + i] = a
        for i in range(1, self.size)[::-1]:
            self.update(i)

    def set(self, p, x):
        #assert 0 <= p < self.n
        p += self.size
        for i in range(1, self.log + 1)[::-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):
        #assert 0 <= p < self.n
        p += self.size
        for i in range(1, self.log + 1):
            self.push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        #assert 0 <= l <= r <= self.n
        if l == r: return self.e
        l += self.size
        r += self.size
        for i in range(1, self.log + 1)[::-1]:
            if ((l >> i) << i) != l: self.push(l >> i)
            if ((r >> i) << i) != r: self.push(r >> i)
        sml = smr = self.e
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.d[1]

    def apply(self, p, f):
        #assert 0 <= p < self.n
        p += self.size
        for i in range(1, self.log + 1)[::-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)

    def range_apply(self, l, r, f):
        #assert 0 <= l <= r <= self.n
        if l == r: return
        l += self.size
        r += self.size
        for i in range(1, self.log + 1)[::-1]:
            if ((l >> i) << i) != l: self.push(l >> i)
            if ((r >> i) << i) != r: self.push((r - 1) >> i)
        l2 = l
        r2 = r
        while l < r:
            if l & 1:
                self.all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.all_apply(r, f)
            l >>= 1
            r >>= 1
        l = l2
        r = r2
        for i in range(1, self.log + 1):
            if ((l >> i) << i) != l: self.update(l >> i)
            if ((r >> i) << i) != r: self.update((r - 1) >> i)

    def max_right(self, l, g):
        #assert 0 <= l <= self.n
        #assert g(self.e)
        if l == self.n: return self.n
        l += self.size
        for i in range(1, self.log + 1)[::-1]:
            self.push(l >> i)
        sm = self.e
        while True:
            while l % 2 == 0: l >>= 1
            if not g(self.op(sm, self.d[l])):
                while l < self.size:
                    self.push(l)
                    l = 2 * l
                    if g(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) == l: return self.n

    def min_left(self, r, g):
        #assert 0 <= r <= self.n
        #assert g(self.e)
        if r == 0: return 0
        r += self.size
        for i in range(1, self.log + 1)[::-1]:
            self.push((r - 1) >> i)
        sm = self.e
        while True:
            r -= 1
            while r > 1 and r % 2: r >>= 1
            if not g(self.op(self.d[r], sm)):
                while r < self.size:
                    self.push(r)
                    r = 2 * r + 1
                    if g(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) == r: return 0

mod = 998244353
N,Q = map(int,input().split())
O = [1]*(N+1)
c=kk=1
for i in range(1, N+1):
    O[i] = c%mod
    kk=kk*10%mod
    c=(c+kk)%mod

def op(x, y):
    return ((pow(10, y[1], mod)*x[0] + y[0]) % mod, x[1]+y[1])

def mapping(p, x):
    if p:
        return (O[x[1]] * p % mod, x[1])
    return x

def composition(p, q):
    if p == 0: return q
    return p

res = [(1, 1)]*N
LST = LazySegmentTree(N,op,(0, 0),mapping,composition,0)
LST.build(res)
for _ in range(Q):
    l,r,D = map(int,input().split())
    LST.range_apply(l-1,r,D)
    print(LST.all_prod()[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
N,Q=map(int, sys.stdin.readline().split())
LRD=[ map(int, sys.stdin.readline().split()) for _ in range(Q) ]
L=[]
n=0
for i in range(N):
    n+=10**i
    L.append(n)

mod=998244353

for l,r,d in LRD:
    t=(n/10**(N-r))%(10**(r-l+1))*10**(N-r)
    n-=t
    n+=d*L[r-l]*10**(N-r)
    print n%mod