Problem:


Score : 500 points

Problem Statement

You have a string S of length N.
Initially, all characters in S are 1s.

You will perform queries Q times.
In the i-th query, you are given two integers L_i, R_i and a character D_i (which is a digit).
Then, you must replace all characters from the L_i-th to the R_i-th (inclusive) with D_i.

After each query, read the string S as a decimal integer, and print its value modulo 998,244,353.

Constraints

1 \leq N, Q \leq 200,000

1 \leq L_i \leq R_i \leq N

1 \leq D_i \leq 9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
L_1 R_1 D_1
:
L_Q R_Q D_Q

Output

Print Q lines.
In the i-th line print the value of S after the i-th query, modulo 998,244,353.

Sample Input 1

8 5
3 6 2
1 4 7
3 8 3
2 2 2
4 5 1

Sample Output 1

11222211
77772211
77333333
72333333
72311333

Sample Input 2

200000 1
123 456 7

Sample Output 2

641437905

Don't forget to take the modulo.



Sample input:
8 5
3 6 2
1 4 7
3 8 3
2 2 2
4 5 1


Sample output:
11222211
77772211
77333333
72333333
72311333

Submission status: Time Limit Exceeded

Solution code:
from typing import Callable, List, TypeVar

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


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

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

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

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

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

        self.lazy = [id_] * self._size

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

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

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

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

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

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

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

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

        if l == r:
            return self.e

        l += self._size
        r += self._size
        for i in range(self._log, 0, -1):
            if ((l >> i) << i) != l:
                self._push(l >> i)
            if ((r >> i) << i) != r:
                self._push(r >> i)

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

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

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

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

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

        if l == r:
            return

        l += self._size
        r += self._size
        for i in range(self._log, 0, -1):
            if ((l >> i) << i) != l:
                self._push(l >> i)
            if ((r >> i) << i) != r:
                self._push((r - 1) >> i)

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

        for i in range(1, self._log + 1):
            if ((l >> i) << i) != l:
                self._update(l >> i)
            if ((r >> i) << i) != r:
                self._update((r - 1) >> i)


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

mod = 998244353

base = [-1] * N
base[0] = 1

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


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


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


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


base.reverse()

A = []
for i in range(N):
    A.append([base[i], base[i]])

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

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

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

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

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

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

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

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


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

        res = self.ide_ele

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

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
numb = [1]*n
for num in range(q):
  l,r,d = map(int,input().split())
  pr = "" 
  for i in range(n):
    if l-1 <= i and i < r :
      numb[i] = d
    pr += str(numb[i])
  print(int(pr)%998244353)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N,Q = map(int,input().split())
    squr = int(N**0.5)+1
    mod = 998244353
    """
    前処理
    """
    memo = [[0]*(N) for _ in range(10)]
    for i in range(10):
        for j in range(N):
            memo[i][j] = i*pow(10,N-j-1,mod)%mod

    memo2 = [[0]*(N) for _ in range(10)]
    for i in range(10):
        for j in range(N-2,-1,-1):
            memo2[i][j] += memo2[i][j+1]+memo[i][j]
            memo2[i][j] %= mod


    array = [memo[1][i] for i in range(N)]
    #bucket[i][0] => そのバケットの合計値
    #bucket[i][1] => そのバケットでの遅延評価値
    bucket = [[0,0] for _ in range(squr)]
    for i in range(N):
        belong = i//squr
        bucket[belong][0] += array[i]
        bucket[belong][1] %= mod

    for _ in range(Q):
        l,r,d = map(int,input().split())
        l -= 1
        r -= 1
        #lの所属している区間でbucketの遅延評価値のクリアを行う。
        LBelong = l//squr
        if bucket[LBelong][1] > 0:
            for i in range(LBelong*squr,(LBelong+1)*squr):
                array[i] = memo[bucket[LBelong][1]][i]
            bucket[LBelong][1] = 0

        #rの所属している区間でbucketの遅延評価値のクリアを行う。
        RBelong = r//squr
        if bucket[RBelong][1] > 0:
            for i in range(RBelong*squr,min((RBelong+1)*squr,N)):
                array[i] = memo[bucket[RBelong][1]][i]
            bucket[RBelong][1] = 0
        
        #クエリ区間の左端の余った部分を処理。
        while l//squr != l/squr and l <= r:
            #bucket更新
            bucket[l//squr][0] -= array[l]
            if bucket[l//squr][0] < 0:
                bucket[l//squr][0] += mod
            bucket[l//squr][0] += memo[d][l]
            bucket[l//squr][0] %= mod
            
            #array更新
            array[l] = memo[d][l]
            
            l += 1
        
        #クエリ区間の右端の余った部分を処理。
        while r != (r//squr+1)*squr-1 and l <= r:
            #bucket更新
            bucket[r//squr][0] -= array[r]
            if bucket[r//squr][0] < 0:
                bucket[r//squr][0] += mod
            bucket[r//squr][0] += memo[d][r]
            bucket[r//squr][0] %= mod
            
            #array更新
            array[r] = memo[d][r]
            
            r -= 1
        
        if l < r:
            bucketLeft = l//squr
            bucketRight = r//squr
            for belong in range(bucketLeft,bucketRight+1):
                belongLeft = belong*squr
                belongRight = belong*squr+squr-1
                if bucketRight != N-1:
                    tmp = memo2[d][belongLeft] - memo2[d][belongRight+1]
                else:
                    tmp = memo2[d][belongLeft]
                if tmp < 0:
                    tmp += mod
                bucket[belong][0] = tmp
                bucket[belong][1] = d
        ans = 0
        for i in range(squr):
            ans += bucket[i][0]
            ans %= mod
        print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
n, q = list(map(int, input().split()))
s = "1"*n
for i in range(q):
    L, R, D = list(map(int, input().split()))
    s = s[:(L-1)] + str(str(D)*(R-L+1)) + s[R:]
    print(int(s)%998244353)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
ls=[1]*n
N = 998244353
num = int('1'*n)%N
ans=[]
for _ in range(q):
    l,r,d= map(int, input().split())
    for i in range(l-1, r):
        num += N + ((d-ls[i]) * (10**(n-i-1)))%N
        ls[i]=d
    ans.append(num%N)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
squr = int(N**0.5)+1
mod = 998244353
"""
前処理
"""
memo = [[0]*(N) for _ in range(10)]
for i in range(10):
    for j in range(N):
        memo[i][j] = i*pow(10,N-j-1,mod)%mod

memo2 = [[0]*(N) for _ in range(10)]
for i in range(10):
    for j in range(N-2,-1,-1):
        memo2[i][j] += memo2[i][j+1]+memo[i][j]
        memo2[i][j] %= mod


array = [memo[1][i] for i in range(N)]
#bucket[i][0] => そのバケットの合計値
#bucket[i][1] => そのバケットでの遅延評価値
bucket = [[0,0] for _ in range(squr)]
for i in range(N):
    belong = i//squr
    bucket[belong][0] += array[i]
    bucket[belong][1] %= mod

for _ in range(Q):
    l,r,d = map(int,input().split())
    l -= 1
    r -= 1
    #lの所属している区間でbucketの遅延評価値のクリアを行う。
    LBelong = l//squr
    if bucket[LBelong][1] > 0:
        for i in range(LBelong*squr,(LBelong+1)*squr):
            array[i] = memo[bucket[LBelong][1]][i]
        bucket[LBelong][1] = 0

    #rの所属している区間でbucketの遅延評価値のクリアを行う。
    RBelong = r//squr
    if bucket[RBelong][1] > 0:
        for i in range(RBelong*squr,min((RBelong+1)*squr,N)):
            array[i] = memo[bucket[RBelong][1]][i]
        bucket[RBelong][1] = 0
    
    #クエリ区間の左端の余った部分を処理。
    while l//squr != l/squr and l <= r:
        #bucket更新
        bucket[l//squr][0] -= array[l]
        if bucket[l//squr][0] < 0:
            bucket[l//squr][0] += mod
        bucket[l//squr][0] += memo[d][l]
        bucket[l//squr][0] %= mod
        
        #array更新
        array[l] = memo[d][l]
        
        l += 1
    
    #クエリ区間の右端の余った部分を処理。
    while r != (r//squr+1)*squr-1 and l <= r:
        #bucket更新
        bucket[r//squr][0] -= array[r]
        if bucket[r//squr][0] < 0:
            bucket[r//squr][0] += mod
        bucket[r//squr][0] += memo[d][r]
        bucket[r//squr][0] %= mod
        
        #array更新
        array[r] = memo[d][r]
        
        r -= 1
    
    if l < r:
        bucketLeft = l//squr
        bucketRight = r//squr
        for belong in range(bucketLeft,bucketRight+1):
            belongLeft = belong*squr
            belongRight = belong*squr+squr-1
            if bucketRight != N-1:
                tmp = memo2[d][belongLeft] - memo2[d][belongRight+1]
            else:
                tmp = memo2[d][belongLeft]
            if tmp < 0:
                tmp += mod
            bucket[belong][0] = tmp
            bucket[belong][1] = d
    ans = 0
    for i in range(squr):
        ans += bucket[i][0]
        ans %= mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
# sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline
# readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class LazySegmentTree():
    def __init__(self, op, e, mapping, composition, im, init_array):
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.im = im

        l = len(init_array)

        def ceil_pow2(n):
            x = 0
            while (1 << x) < n:
                x += 1
            return x
        self.log = ceil_pow2(l)
        self.size = 1 << self.log
        self.d = [e() for _ in range(2*self.size)]
        self.lz = [im() for _ in range(self.size)]

        for i, a in enumerate(init_array):
            self.d[i+self.size] = a

        for i in range(self.size-1, 0, -1):
            self.__update(i)

    def set(self, p, x):
        p += self.size

        for i in range(self.log, 0, -1):
            self.__push(p >> i)

        self.d[p] = x

        for i in range(1, self.log+1):
            self.__update(p >> i)

    def __getitem__(self, p):
        p += self.size
        for i in range(self.log, 0, -1):
            self.__push(p >> i)
        return self.d[p]

    def prod(self, l, r):
        if l == r:
            return self.e()

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push(r >> i)

        sml = self.e()
        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 apply(self, l, r, f):
        if l == r:
            return

        l += self.size
        r += self.size

        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self.__push(l >> i)
            if ((r >> i) << i) != r:
                self.__push((r-1) >> i)

        l2, r2 = l, 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, r = l2, 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 __update(self, k):
        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.im()


M = 998244353


def e():
    # (v, b)
    return (0, 0)


def op(sl, sr):
    # print(sl, sr)
    return ((sl[0] + sr[0]) % M, (sl[1] + sr[1]) % M)


def mapping(fl, sr):
    if fl[0] == 0:
        return sr
    return ((sr[1]*fl[0]) % M, sr[1])


def composition(fl, fr):
    if fl[1] > fr[1]:
        return fl
    return fr


def im():
    return (0, -1)


@mt
def slv(N, Q, LRQ):
    # A = [(pow(10, N-i-1, M), pow(10, N-i-1, M)) for i in range(N)]
    A = []
    for i in range(N):
        v = pow(10, N-i-1, M)
        A.append((v, v))
    st = LazySegmentTree(op, e, mapping, composition, im, A)

    ans = []
    for i, (l, r, d) in enumerate(LRQ, start=1):
        l -= 1
        st.apply(l, r, (d, i))
        ans.append(st.prod(0, N)[0])
    return ans


def main():
    N, Q = read_int_n()
    LRQ = [read_int_n() for _ in range(Q)]
    print(*slv(N, Q, LRQ), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
numb = [1]*n
for num in range(q):
  l,r,d = map(int,input().split())
  for i in range(l-1,r):
    numb[i] = d
  pr = "" 
  for i in range(n):
    pr += str(numb[i])
  print(int(pr)%998244353)

Submission status: Time Limit Exceeded

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

A = "1" * N

for i in range(Q):
  l, r, d = map(int, input().split())
  a = (-int(A[l-1:r]) + int(str(d) * (r - l + 1))) * (10 ** (N - r))
  A = str(int(A) + a)
  out = int(A)  % 998244353
  print(out)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
s=['1']*n
mod=998244353
for i in range(q):
    start,end,v=map(int,input().split())
    for j in range(start-1,end):
        s[j]=str(v)
    print(int(''.join(s))%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class LazySegmentTree(object):
    def __init__(self, A, dot, unit, compose, identity, act):
        # A : array of monoid (M, dot, unit)
        # (S, compose, identity) : sub monoid of End(M)
        # compose : (f, g) -> fg (f, g in S)
        # act : (f, x) -> f(x) (f in S, x in M)
        logn = (len(A) - 1).bit_length()
        n = 1 << logn
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n, self._logn, self._tree, self._lazy = n, logn, tree, [identity] * (2 * n)
        self._dot, self._unit, self._compose, self._identity, self._act = dot, unit, compose, identity, act

    def _ascend(self, i):
        tree, lazy, dot, act = self._tree, self._lazy, self._dot, self._act
        while i > 1:
            i >>= 1
            tree[i] = act(lazy[i], dot(tree[i << 1], tree[i << 1 | 1]))

    def _descend(self, i):
        tree, lazy, identity, compose, act = self._tree, self._lazy, self._identity, self._compose, self._act
        for k in range(self._logn, 0, -1):
            p = i >> k
            f = lazy[p]
            tree[p << 1], lazy[p << 1] = act(f, tree[p << 1]), compose(f, lazy[p << 1])
            tree[p << 1 | 1], lazy[p << 1 | 1] = act(f, tree[p << 1 | 1]), compose(f, lazy[p << 1 | 1])
            lazy[p] = identity

    # A[i] <- f(A[i]) for all i in [l, r)
    def range_act(self, l, r, f):
        l += self._n
        r += self._n
        # propagation isn't necessary if S is commutative
        self._descend(l)
        self._descend(r - 1)
        l0, r0 = l, r
        tree, lazy, act, compose = self._tree, self._lazy, self._act, self._compose
        while l < r:
            if l & 1:
                tree[l], lazy[l] = act(f, tree[l]), compose(f, lazy[l])
                l += 1
            if r & 1:
                r -= 1
                tree[r], lazy[r] = act(f, tree[r]), compose(f, lazy[r])
            l >>= 1
            r >>= 1
        self._ascend(l0)
        self._ascend(r0 - 1)

    # calculate product of A[l:r]
    def sum(self, l, r):
        l += self._n
        r += self._n
        self._descend(l)
        self._descend(r - 1)
        l_val = r_val = self._unit
        tree, dot = self._tree, self._dot
        while l < r:
            if l & 1:
                l_val = dot(l_val, tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = dot(tree[r], r_val)
            l >>= 1
            r >>= 1
        return dot(l_val, r_val)

def resolve():
    n, q = map(int, input().split())
    dot = lambda a, b : ((a[0] * pow(10, b[1], MOD) + b[0]) % MOD, a[1] + b[1])
    compose = lambda f, g : f if f != 0 else g
    act = lambda f, a : (f * (pow(10, a[1], MOD) - 1) % MOD * pow(9, MOD - 2, MOD) % MOD, a[1]) if f != 0 else a

    tree = LazySegmentTree([(1, 1)] * n, dot, (0, 0), compose, 0, act)
    for _ in range(q):
        l, r, d = map(int, input().split())
        l -= 1
        tree.range_act(l, r, d)
        print(tree.sum(0, n)[0])
resolve()

Submission status: Time Limit Exceeded

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

S = '1' * n

for i in range(q):
  s = str(a[i][2])
  S = S[:a[i][0]-1] + s*(a[i][1]-a[i][0]+1) + S[a[i][1]:]
  print(int(S) % 998244353)

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

ans = 0
ans_str = ""
# m_kouho = ["" for _ in range(9)]
for i in range(N):
    ans += pow(10, i, MOD)
    ans %= MOD
    ans_str += "1"
    # for j in range(9):
    #     m_kouho[j] += str(j + 1)

acc = [0]*(N+1)
for i in range(1, N+1):
    acc[i] = acc[i-1] + pow(10, i-1, MOD)
    acc[i] %= MOD

# print(acc)

for q in LRD:
    l = q[0]
    r = q[1]
    d = q[2]

    ans_l_str = ans_str[0:l-1]
    ans_l = 0
    if ans_l_str != "":
        ans_l = ((int(ans_l_str) % MOD) * pow(10, N - (l - 1), MOD)) % MOD

    ans_r_str = ans_str[r:]
    ans_r = 0
    if ans_r_str != "":
        ans_r = int(ans_r_str) % MOD
    
    ans_m = d * (acc[N - l + 1] - acc[N - (r+1) + 1] + MOD) % MOD
    dig = r - l + 1

    ans_m_str = ""
    for _ in range(dig): ans_m_str += str(d)
    # print("acc", acc[N-l], acc[N - (r+1)], N-l, N-(r+1))
    ans = ans_l + ans_m + ans_r
    ans %= MOD
    ans_str = ans_l_str + ans_m_str + ans_r_str
    # print(ans_l)
    # print(ans_m)
    print(ans)
    # print()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
MOD = 998244353
di = [pow(10, N - i - 1, MOD) for i in range(N)]
S = "1"*N
ans = int(S) % MOD

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

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
 
ans_l = ["1"] * n
ans = 0
 
for i in range(q) :
  l,r,d = map(int,input().split())
  ans_l[l-1:r] = [str(d)]*(r-l+1)
  print(int("".join(ans_l)) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

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

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

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

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

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

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


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

        res = self.ide_ele

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