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 = lambda: sys.stdin.readline().rstrip()

class SegmentTree():
    def __init__(self, init, unitX, unitA, f, g, h):
        self.f = f # (X, X) -> X
        self.g = g # (X, A, size) -> X
        self.h = h # (A, A) -> A
        self.unitX = unitX
        self.unitA = unitA
        self.f = f
        if type(init) == int:
            self.n = init
            self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            self.n = 1 << (self.n - 1).bit_length()
            self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
            for i in range(self.n-1, 0, -1):
                self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
    
        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2|1]
        
        self.A = [unitA] * (self.n * 2)
        
    def update(self, i, x):
        i += self.n
        self.propagate_above(i)
        self.X[i] = x
        self.A[i] = unitA
        self.calc_above(i)
    
    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])
    
    def calc_above(self, i):
        i >>= 1
        while i:
            self.X[i] = self.f(self.calc(i*2), self.calc(i*2|1))
            i >>= 1
    
    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2|1] = self.h(self.A[i*2|1], self.A[i])
        self.A[i] = self.unitA
        
    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)
    
    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)
    
    def getrange(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)
        
        al = self.unitX
        ar = self.unitX
        while l < r:
            if l & 1:
                al = self.f(al, self.calc(l))
                l += 1
            if r & 1:
                r -= 1
                ar = self.f(self.calc(r), ar)
            l >>= 1
            r >>= 1
        return self.f(al, ar)
    
    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)
    
    def operate_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l < r:
            if l & 1:
                self.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1
        
        self.calc_above(l0)
        self.calc_above(r0)
    
    def check(self, randX, randA, maxs, rep):
        from random import randrange
        for _ in range(rep):
            x = randX()
            y = randX()
            z = randX()
            a = randA()
            b = randA()
            c = randA()
            s = randrange(1, maxs + 1)
            t = randrange(1, maxs + 1)
            err = 0
            if not f(x, unitX) == f(unitX, x) == x:
                err = 1
                print("!!!!! unitX Error !!!!!")
                print("unitX =", unitX)
                print("x =", x)
                print("f(x, unitX) =", f(x, unitX))
                print("f(unitX, x) =", f(unitX, x))
            
            if not h(a, unitA) == h(unitA, a) == a:
                err = 1
                print("!!!!! unitA Error !!!!!")
                print("unitA =", unitA)
                print("a =", a)
                print("f(a, unitA) =", f(a, unitA))
                print("f(unitA, a) =", f(unitA, a))
                
            if not f(f(x, y), z) == f(x, f(y, z)):
                err = 1
                print("!!!!! Associativity Error X !!!!!")
                print("x, y, z, f(x, y), f(y, x) =", x, y, z, f(x, y), f(y, x))
                print("f(f(x, y), z) =", f(f(x, y), z))
                print("f(x, f(y, z)) =", f(x, f(y, z)))
            
            if not h(h(a, b), c) == h(a, h(b, c)):
                err = 1
                print("!!!!! Associativity Error A !!!!!")
                print("a, b, c, h(a, b), h(b, c) =", a, b, c, h(a, b), h(b, c))
                print("h(h(a, b), c) =", h(h(a, b), c))
                print("h(a, h(b, c)) =", h(a, h(b, c)))
            
            if not g(x, unitA, s) == x:
                err = 1
                print("!!!!! Identity Error !!!!!")
                print("unitA, x, s =", unitA, x, s)
                print("g(x, unitA, s) =", g(x, unitA, s))
            
            if not g(g(x, a, s), b, s) == g(x, h(a, b), s):
                err = 1
                print("!!!!! Act Error 1 !!!!!")
                print("x, a, b, s, g(x, a, s), h(a, b) =", x, a, b, s, g(x, a, s), h(a, b))
                print("g(g(x, a, s), b, s) =", g(g(x, a, s), b, s))
                print("g(x, h(a, b), s)    =", g(x, h(a, b), s))
            
            if not g(f(x, y), a, s + t) == f(g(x, a, s), g(y, a, t)):
                err = 1
                print("!!!!! Act Error 2 !!!!!")
                print("x, y, a, s, t, f(x, y), g(x, a, s), g(y, a, t) =", x, y, a, s, t, f(x, y), g(x, a, s), g(y, a, t))
                print("g(f(x, y), a, s + t)      =", g(f(x, y), a, s + t))
                print("f(g(x, a, s), g(y, a, t)) =", f(g(x, a, s), g(y, a, t)))
            
            if err:
                break
                assert f(x, unitX) == f(unitX, x) == x
                assert h(a, unitA) == h(unitA, a) == a
                assert f(f(x, y), z) == f(x, f(y, z))
                assert h(h(a, b), c) == h(a, h(b, c))
                assert g(x, unitA, s) == x
                assert g(g(x, a, s), b, s) == g(x, h(a, b), s)
                assert g(f(x, y), a, s + t) == f(g(x, a, s), g(y, a, t))
        else:
            pass
            print("Monoid Check OK!")
    
    def debug1(self):
        print("self.n =", self.n)
        deX = []
        deA = []
        deS = []
        a, b = self.n, self.n * 2
        while b:
            deX.append(self.X[a:b])
            deA.append(self.A[a:b])
            deS.append(self.size[a:b])
            a, b = a//2, a
        print("--- debug ---")
        for d in deX[::-1]:
            print(d)
        print("--- ---")
        for d in deA[::-1]:
            print(d)
        print("--- ---")
        for d in deS[::-1]:
            print(d)
        print("--- ---")
    
    def debug(self, k = 10):
        print("--- debug ---")
        print("point")
        for i in range(min(self.n - 1, k)):
            print(i, self.getvalue(i))
        print("prod")
        for i in range(min(self.n, k)):
            print(i, self.getrange(0, i))
        print("--- ---")


# ↓和を使うときはこっちの方が少し高速
# from operator import add
# f = lambda a, b: (a[0] * b[0] % P, (a[1] * b[0] + b[1]) % P) # 1次関数の合成


P = 998244353
inv9 = 443664157
mm = (1 << 18) - 1

# f = lambda x, y: (x[0] + y[0], x[1] + y[1])
def f(x, y):
    # print("f", x, y)
    l1, su1 = x & mm, x >> 18
    l2, su2 = y & mm, y >> 18
    # return (l1, (su1 + su2 * pow(10, l2 - l1, P)) % P) if l2 >= l1 else (l2, (su2 + su1 * pow(10, l1 - l2, P)) % P)
    return (((su1 + su2) % P) << 18) + min(l1, l2)

# g = lambda x, a, s: (s, 0) if a == "A" else (0, s) if a == "B" else (x)
def g(x, a, s):
    # print("g", x, a, s)
    l, su = x & mm, x >> 18
    return (((pow(10, s, P) - 1) * inv9 % P * pow(10, l, P) * a % P) << 18) + l if a else x
    
h = lambda a, b: b if b else a

unitX = 0
unitA = 0
N, Q = map(int, input().split())
x = 1
X = []
for i in range(N):
    X.append((x << 18) + i)
    x = x * 10 % P

st = SegmentTree(X, unitX, unitA, f, g, h)

if False:
    from random import randrange
    randX = lambda: (randrange(-10, 11), randrange(-10, 11))
    randA = lambda: ["", "A", "B"][randrange(3)]
    maxs = 10
    rep = 1000
    st.check(randX, randA, maxs, rep)

for _ in range(Q):
    l, r, d = map(int, input().split())
    l, r = N - r, N - l + 1
    st.operate_range(l, r, d)
    print(st.X[1] >> 18)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
a = "1"*n
b = 998244353 
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)%b)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
LRD = [list(map(int, input().split())) for _ in range(Q)]

mod = 998244353

l = []
for i in range(1, 10):
    lt = []
    t = ''
    for j in range(10000):
        t += str(i)
        lt.append(t)
    l.append(lt)

S = ''
for i in range(N):
    S += '1'

for i in range(Q):
    Sn = S[:LRD[i][0] - 1] + l[LRD[i][2] - 1][LRD[i][1] - LRD[i][0]]
    sho = (LRD[i][1] - LRD[i][0] + 1) // 10000
    yo = (LRD[i][1] - LRD[i][0] + 1) % 10000
    for i in range(sho):
        if i == sho - 1:
            Sn += l[LRD[i][2] - 1][yo - 1]
        else:
            Sn += l[LRD[i][2] - 1][10000 - 1]
    Sn += S[LRD[i][1]:]
    S = Sn
    print(int(S) % mod)

Submission status: Time Limit Exceeded

Solution code:
n, q=input().split()
q=int(q)
n='1'*int(n)
for i in range(0,q):
    a,b,c=input().split()
    a=int(a)
    b=int(b)
    x=b-a+1
    n = n[:a-1]+ (c*x) + n[b:]
    print(int(n)%998244353)

Submission status: Time Limit Exceeded

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

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

mod=998244353

seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
seg_height=1+N.bit_length() # Segment treeの高さ
SEG=[0 for i in range(2*seg_el)] # 区間の和
LAZY=[0 for i in range(2*seg_el)]


POW10=[pow(10,i,mod) for i in range(N+1)]
gyaku=pow(9,mod-2,mod)

def seg_function(x,y):
    return (x+y)%mod
    
for i in range(N): # Aを対応する箇所へupdate
    SEG[i+seg_el]=POW10[i]
        
for i in range(seg_el-1,0,-1): # 親の部分もupdate
    SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])

def lazy_change(ind,b):
    kousuu = 1<< (seg_height - (ind.bit_length()))
    tyousei = (ind - (1<<((ind.bit_length())-1)))*kousuu

    #print(ind,tyousei,kousuu)
    SEG[ind] = POW10[tyousei] * b * (POW10[kousuu]-1) * gyaku %mod

def lazy_compose(ind,b):
    LAZY[ind]=b

def indexes(L,R): # 遅延伝搬すべきノードのリストを下から上の順に返す. （つまり, updateやgetvaluesで見るノードより上にあるノードたち）
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST
        

def changes(l,r,b0): # 区間[l,r)更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=0:
            b=LAZY[ind]
            
            lazy_change(ind<<1,b)
            lazy_change(1+(ind<<1),b)
            
            lazy_compose(ind<<1,b)
            lazy_compose(1+(ind<<1),b)
            
            LAZY[ind]=0

    #print(SEG)
    
    while L!=R:
        if L > R:
            lazy_change(L,b0)
            lazy_compose(L,b0)
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            lazy_change(R,b0)
            lazy_compose(R,b0)
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=seg_function(SEG[ind<<1],SEG[1+(ind<<1)])
        
def getvalues(l,r):

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=0:
            b=LAZY[ind]
            
            lazy_change(ind<<1,b)
            lazy_change(1+(ind<<1),b)
            
            lazy_compose(ind<<1,b)
            lazy_compose(1+(ind<<1),b)
            
            LAZY[ind]=0
            
    ANSL=0
    ANSR=0

    while L!=R:
        if L > R:
            ANSL=seg_function(ANSL,SEG[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANSR=seg_function(SEG[R],ANSR)
            R//=(R & (-R))

    return seg_function(ANSL,ANSR)

for qu in range(Q):
    L,R,D=map(int,input().split())
    L,R=N-R+1,N-L+1
    #print(SEG)

    changes(L-1,R,D)
    sys.stdout.write(str(SEG[1])+"\n")

Submission status: Time Limit Exceeded

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 = n
        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] * (n + n)
        self.A = [unitA] * (n + 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
        self._propagate_above(l0)
        self._propagate_above(r0)
        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


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

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


lst = LazySegmentTree(n, unitX, unitA, X_f, A_f, XA_map) 
lst.build([(1, n - i - 1, 1) for i in range(n)])

# print([lst.fold(i, i + 1) for i in range(n)])
# print(lst.fold(0, n))
ans = []

for l, r, d in queries:
    l -= 1
    lst.apply_range(l, r, d)
    # print([lst.fold(i, i + 1) for i in range(n)])
    ans.append(lst.fold(0, n)[0])
    
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
n, q = list(map(int,input().split()))
s = list('1' * n)
array = [list(map(int, input().split())) for i in range(q)]

for ary in array:
    for i in range(ary[0] - 1, ary[1]):
        s[i] = str(ary[2])
    print(int("".join(s)) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())

x="1"*N
ans=[0 for _ in range(Q)]

for i in range(Q):
    L,R,D=map(int,input().split())
    D=str(D)
    l_x=list(x)
    l_x[L-1:R]=D*(R+1-L)
    x=''.join(l_x)
    ans[i]=int(x)%998244353

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N, Q, *LRD = [int(_) for _ in open(0).read().split()]
L, R, D = LRD[::3], LRD[1::3], LRD[2::3]
mod = 998244353


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)


#RSQ and RUQ
array = [(pow(10, i, mod), pow(10, i, mod), 1) for i in range(N)][::-1]
f = lambda a, b: ((a[0] + b[0]) % mod, (a[1] + b[1]) % mod, a[2] + b[2])
g = lambda a, b: (b * a[1] % mod, a[1], a[2]) if b else a
h = lambda a, b: b if b else a
ti = (0, 0, 0)
ei = 0

lst = LazySegmentTree(array, ti, ei, f, g, h)
ans = []
for l, r, d in zip(L, R, D):
    lst.effect(l - 1, r, d)
    ans += [lst.folded(0, N)[0]]
print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

l = input().split()
n = int(l[0])
q = int(l[1])
cur = "1"*n
md = int(998244353)
for i in range(q):
	temp =  input().split()
	fr = int(temp[0])-1
	to = int(temp[1])-1
	rep = str(temp[2])
	cur = (str(cur[:fr]) + str(rep*(to-fr+1)) + str(cur[to+1:]))
	val  = int(cur)%md
	print(val)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
LRD = [list(map(int, input().split())) for _ in range(Q)]

mod = 998244353

l = []
for i in range(1, 10):
    lt = []
    t = ''
    for j in range(2000):
        t += str(i)
        lt.append(t)
    l.append(lt)

S = ''
for i in range(N):
    S += '1'

for i in range(Q):
    Sn = S[:LRD[i][0] - 1] + l[LRD[i][2] - 1][LRD[i][1] - LRD[i][0]]
    sho = (LRD[i][1] - LRD[i][0] + 1) // 2000
    yo = (LRD[i][1] - LRD[i][0] + 1) % 2000
    for i in range(sho):
        if i == sho - 1:
            Sn += l[LRD[i][2] - 1][yo - 1]
        else:
            Sn += l[LRD[i][2] - 1][2000 - 1]
    Sn += S[LRD[i][1]:]
    S = Sn
    print(int(S) % mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

def get_ints():
    return map(int, input().strip().split())


def main():
    n, q = get_ints()
    s = "1" * n
    mod = 998244353

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

        s = s[0: l-1] + str(d) * (r-l+1) + s[r:]
        print(int(s) % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import copy

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    mod=998244353
    n,q=map(int, readline().rstrip().split())
    d = [0]*n

    #memo = [1]*n
    sm = 1
    d[0]=1
    for i in range(1,n):
        d[i]=(d[i-1]*10)%mod
        sm+=d[i]
        sm%=mod
    d1 = copy.copy(d)

    for i in range(q):
        l,r,x=map(int, readline().rstrip().split())
        l-=1
        r-=1
        for j in range(n-1-r,n-l):
            sm -= d[j]
            d[j] = d1[j]*x
            sm += d[j]
            sm %= mod
        print(sm)

    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
LRD = [list(map(int, input().split())) for _ in range(Q)]

mod = 998244353

l = []
for i in range(1, 10):
    lt = []
    t = ''
    for j in range(20000):
        t += str(i)
        lt.append(t)
    l.append(lt)

S = ''
for i in range(N):
    S += '1'

for i in range(Q):
    Sn = S[:LRD[i][0] - 1] + l[LRD[i][2] - 1][LRD[i][1] - LRD[i][0]]
    sho = (LRD[i][1] - LRD[i][0] + 1) // 20000
    yo = (LRD[i][1] - LRD[i][0] + 1) % 20000
    for i in range(sho):
        if i == sho - 1:
            Sn += l[LRD[i][2] - 1][yo - 1]
        else:
            Sn += l[LRD[i][2] - 1][20000 - 1]
    Sn += S[LRD[i][1]:]
    S = Sn
    print(int(S) % mod)

Submission status: Time Limit Exceeded

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 = n
        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] * (n + n)
        self.A = [unitA] * (n + 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
        self._propagate_above(l0)
        self._propagate_above(r0)
        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)
def X_f(x1, x2):
    return (x1[0] * pow(10, abs(x1[1] - x2[1]), MOD) + x2[0]) % MOD, x2[1], x1[2] + x2[2]

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


lst = LazySegmentTree(n, unitX, unitA, X_f, A_f, XA_map) 
lst.build([(1, n - i - 1, 1) for i in range(n)])

# print([lst.fold(i, i + 1) for i in range(n)])
# print(lst.fold(0, n))

for l, r, d in queries:
    l -= 1
    lst.apply_range(l, r, d)
    # print([lst.fold(i, i + 1) for i in range(n)])
    print(lst.fold(0, n)[0])