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:
# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

# You have to set up (f, data_default, lazy_default, lazy_processing, propagate, query(lres))

class LazySegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f, data_default, lazy_default):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [data_default] * (2*self.num_leaf)
        self.lazy = [lazy_default] * (2*self.num_leaf)
        self.f = f

    # You can use first_update before you use update.
    # a[i] = x
    # O(log(n))
    def first_update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    def gindex(self, l, r):
        lis = []
        l += self.num_leaf
        r += self.num_leaf
        lm = (l // (l & -l)) >> 1
        rm = (r // (r & -r)) >> 1
        while l < r:
            if l <= lm:
                lis.append(l)
            if r <= rm:
                lis.append(r)
            l >>= 1
            r >>= 1
        while l:
            lis.append(l)
            l >>= 1
        lis.reverse()
        return lis

    ### You have to set up
    def lazy_processing(self, i, x):
        self.data[i] = x * len(self.data[i])
        self.lazy[i] = x
    ###

    # from parent to children
    ### You have to set up
    def propagate(self, lis):
        for i in lis:
            if self.lazy[i] == None:
                continue
            self.lazy_processing(2*i, self.lazy[i])
            self.lazy_processing(2*i+1, self.lazy[i])
            self.lazy[i] = None
    ###

    # update a[l:r]
    def update(self, l, r, x):
        lis = self.gindex(l, r)

        # top-down propagation
        self.propagate(lis)

        l += self.num_leaf
        r += self.num_leaf - 1
        while l < r:
            if l & 1:
                self.lazy_processing(l, x)
                l += 1
            if not r & 1:
                self.lazy_processing(r, x)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            self.lazy_processing(l, x)

        # bottom-up propagation
        lis.reverse()
        for i in lis:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])

    # return f(a[l:r])
    def query(self, l, r):
        # top-down propagation
        self.propagate(self.gindex(l, r))

        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res


from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    mod = 998244353
    n, q = map(int, input().split())

    lst = LazySegmentTree(n, f=lambda x, y: ''.join((x, y)), data_default='', lazy_default=None)

    for i in range(n):
        lst.first_update(i, '1')

    for _ in range(q):
        l, r, d = input().split()
        lst.update(int(l)-1, int(r), d)
        print(int(lst.data[1]) % mod)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, q = map(int, input().split())
    s = "1" * n
    mod = 998244353
    ans = int(s) % mod

    for _ in range(q):
        left, right, d = map(int, input().split())
        left, right = left - 1, right - 1
        t = s[:left] + str(d) * (right - left + 1) + s[right + 1:]
        b = int(t) - int(s)
        ans = (ans + b % mod) % mod
        s = t
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 998244353


def set_depth(depth):
    global DEPTH, SEGTREE_SIZE, NONLEAF_SIZE
    DEPTH = depth
    SEGTREE_SIZE = 1 << DEPTH
    NONLEAF_SIZE = 1 << (DEPTH - 1)


def set_width(width):
    set_depth((width - 1).bit_length() + 1)


def get_size(pos):
    ret = pos.bit_length()
    return (1 << (DEPTH - ret))


def up(pos):
    pos += SEGTREE_SIZE // 2
    return pos // (pos & -pos)


def up_propagate(table, pos, binop):
    while pos > 1:
        pos >>= 1
        size = get_size(pos) // 2
        table[pos] = binop(
            table[pos * 2],
            table[pos * 2 + 1],
            size
        )


def full_up(table, binop):
    for pos in range(NONLEAF_SIZE - 1, 0, -1):
        size = get_size(pos) // 2
        table[pos] = binop(
            table[2 * pos],
            table[2 * pos + 1],
            size)


def force_down_propagate(
    action_table, value_table, pos,
    action_composite, action_force, action_unity
):
    max_level = pos.bit_length() - 1
    size = NONLEAF_SIZE
    for level in range(max_level):
        size //= 2
        i = pos >> (max_level - level)
        action = action_table[i]
        if action != action_unity:
            action_table[i * 2] = action_composite(
                action, action_table[i * 2])
            action_table[i * 2 + 1] = action_composite(
                action, action_table[i * 2 + 1])
            # old_action = action_table[i * 2]
            # if old_action == action_unity:
            #     action_table[i * 2] = action
            # else:
            #     b1, c1 = old_action
            #     b2, c2 = action
            #     action_table[i * 2] = (b1 * b2, b2 * c1 + c2)

            # old_action = action_table[i * 2 + 1]
            # if old_action == action_unity:
            #     action_table[i * 2 + 1] = action
            # else:
            #     b1, c1 = old_action
            #     b2, c2 = action
            #     action_table[i * 2 + 1] = (b1 * b2, b2 * c1 + c2)

            action_table[i] = action_unity

            value_table[i * 2] = action_force(
                action, value_table[i * 2], size)
            value_table[i * 2 + 1] = action_force(
                action, value_table[i * 2 + 1], size)
            # b, c = action
            # value = value_table[i * 2]
            # value_table[i * 2] = (value * b + c * size) % MOD
            # value = value_table[i * 2 + 1]
            # value_table[i * 2 + 1] = (value * b + c * size) % MOD


def force_range_update(
    value_table, action_table, left, right,
    action, action_force, action_composite, action_unity
):
    """
    action_force: action, value, cell_size => new_value
    action_composite: new_action, old_action => composite_action
    """
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    while left < right:
        if left & 1:
            value_table[left] = action_force(
                action, value_table[left], get_size(left))
            action_table[left] = action_composite(action, action_table[left])
            left += 1
        if right & 1:
            right -= 1
            value_table[right] = action_force(
                action, value_table[right], get_size(right))
            action_table[right] = action_composite(action, action_table[right])

        left //= 2
        right //= 2


def range_reduce(table, left, right, binop, unity):
    ret_left = unity
    ret_right = unity
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    right_size = 0
    while left < right:
        if left & 1:
            size = get_size(left)
            ret_left = binop(ret_left, table[left], size)
            # debug("size, ret_left", size, ret_left)
            left += 1
        if right & 1:
            right -= 1
            ret_right = binop(table[right], ret_right, right_size)
            right_size += get_size(right)
            # debug("right_size, ret_right", right_size, ret_right)
        left //= 2
        right //= 2
    return binop(ret_left, ret_right, right_size)


def lazy_range_update(
        action_table, value_table, start, end,
        action, action_composite, action_force, action_unity, value_binop):
    "update [start, end)"
    L = up(start)
    R = up(end)
    force_down_propagate(
        action_table, value_table, L,
        action_composite, action_force, action_unity)
    force_down_propagate(
        action_table, value_table, R,
        action_composite, action_force, action_unity)

    force_range_update(
        value_table, action_table, start, end,
        action, action_force, action_composite, action_unity)
    up_propagate(value_table, L, value_binop)
    up_propagate(value_table, R, value_binop)


def lazy_range_reduce(
    action_table, value_table, start, end,
    action_composite, action_force, action_unity,
    value_binop, value_unity
):
    "reduce [start, end)"
    force_down_propagate(
        action_table, value_table, up(start),
        action_composite, action_force,  action_unity)
    force_down_propagate(
        action_table, value_table, up(end),
        action_composite, action_force, action_unity)

    return range_reduce(value_table, start, end, value_binop, value_unity)


def debug(*x):
    print(*x, file=sys.stderr)


def main():
    # parse input
    N, Q = map(int, input().split())
    set_width(N + 1)

    value_unity = 0
    value_table = [value_unity] * SEGTREE_SIZE
    value_table[NONLEAF_SIZE:NONLEAF_SIZE + N] = [1] * N

    action_unity = None
    action_table = [action_unity] * SEGTREE_SIZE

    def action_force(action, value, size):
        if action == action_unity:
            return value
        return int(str(action) * size)

    def action_composite(new_action, old_action):
        if new_action == action_unity:
            return old_action
        return new_action

    def value_binop(a, b, size):
        # debug("a, b, size", a, b, size)
        return (a * (10 ** size) + b) % MOD
    full_up(value_table, value_binop)

    ret = lazy_range_reduce(
        action_table, value_table, 0, N, action_composite, action_force, action_unity,
        value_binop, value_unity)

    for _q in range(Q):
        l, r, d = map(int, input().split())
        lazy_range_update(
            action_table, value_table, l - 1, r, d,
            action_composite, action_force, action_unity, value_binop)

        ret = lazy_range_reduce(
            action_table, value_table, 0, N, action_composite, action_force, action_unity,
            value_binop, value_unity)
        print(ret)


# tests
T1 = """
8 5
3 6 2
1 4 7
3 8 3
2 2 2
4 5 1
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
11222211
77772211
77333333
72333333
72311333
"""

T2 = """
200000 1
123 456 7
"""
_TEST_T2 = """
>>> as_input(T2)
>>> main()
641437905
"""

T3 = """
4 4
1 1 2
1 2 3
1 3 4
1 4 5
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
2111
3311
4441
5555
"""

T4 = """
4 4
4 4 2
3 4 3
2 4 4
1 4 5
1112
1133
1444
5555
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
1112
1133
1444
5555
"""

T5 = """
9 3
1 9 1
1 9 5
1 9 9
"""
TEST_T5 = """
>>> as_input(T5)
>>> main()
111111111
555555555
1755646
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())

s = ['1']*n

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

    s[l-1:r] = [str(d)]*(abs(r-l)+1)

    print(int(''.join(s))%998244353)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
lrd = [map(int, input().split()) for _ in range(q)]
l,r,d = [list(i) for i in zip(*lrd)]

s = '1'*n

for i in range(q):
  s = s[0:l[i]-1]+str(d[i])*(r[i]-l[i]+1)+s[r[i]:n]
  i += 1
  print(int(s)%998244353)

Submission status: Time Limit Exceeded

Solution code:
# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

# You have to set up (f, data_default, lazy_default, lazy_processing, propagate, query(lres))

class LazySegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f, data_default, lazy_default):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [data_default] * (2*self.num_leaf)
        self.lazy = [lazy_default] * (2*self.num_leaf)
        self.f = f

    # You can use first_update before you use update.
    # a[i] = x
    # O(log(n))
    def first_update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    def gindex(self, l, r):
        lis = []
        l += self.num_leaf
        r += self.num_leaf
        lm = (l // (l & -l)) >> 1
        rm = (r // (r & -r)) >> 1
        while l < r:
            if l <= lm:
                lis.append(l)
            if r <= rm:
                lis.append(r)
            l >>= 1
            r >>= 1
        while l:
            lis.append(l)
            l >>= 1
        lis.reverse()
        return lis

    ### You have to set up
    def lazy_processing(self, i, x):
        self.data[i] = x * len(self.data[i])
        self.lazy[i] = x
    ###

    # from parent to children
    ### You have to set up
    def propagate(self, lis):
        for i in lis:
            if self.lazy[i] == None:
                continue
            self.lazy_processing(2*i, self.lazy[i])
            self.lazy_processing(2*i+1, self.lazy[i])
            self.lazy[i] = None
    ###

    # update a[l:r]
    def update(self, l, r, x):
        lis = self.gindex(l, r)

        # top-down propagation
        self.propagate(lis)

        l += self.num_leaf
        r += self.num_leaf - 1
        while l < r:
            if l & 1:
                self.lazy_processing(l, x)
                l += 1
            if not r & 1:
                self.lazy_processing(r, x)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            self.lazy_processing(l, x)

        # bottom-up propagation
        lis.reverse()
        for i in lis:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])

    # return f(a[l:r])
    def query(self, l, r):
        # top-down propagation
        self.propagate(self.gindex(l, r))

        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res


from sys import stdin
def input():
    return stdin.readline().strip()

def main():
    mod = 998244353
    n, q = map(int, input().split())

    lst = LazySegmentTree(n, f=lambda x, y: x + y, data_default='', lazy_default=None)

    for i in range(n):
        lst.first_update(i, '1')

    for _ in range(q):
        l, r, d = input().split()
        lst.update(int(l)-1, int(r), d)
        print(int(lst.data[1]) % mod)

main()

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():
    def __init__(self, array, f, g, h, ti, ei):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
            T x T -> T
            T is dat
        g : func
            binary operation of the monoid
            T x E -> T
            T is dat, E is laz
        h : func
            binary operation of the monoid
            E x E -> T
            E is laz
        ti : T
            identity element of T
        ei : E
            identity element of E
        """
        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):  # set value at position [a, b) (0-indexed)
        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):
        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):  # result on interval [a, b) (0-indexed)
        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)


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

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

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
s = "1"*n
mod = 998244353
for _ in range(q):
    li, ri, di = input().split()
    li, ri = int(li), int(ri)
    s = s[:li-1] + di * (ri - li + 1) + s[ri:]
    print(int(s) % mod)

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 = []
t = ''
for i in range(20000):
    t += '1'
for i in range(1, 10):
    l.append(str(int(t) * i))

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

for i in range(Q):
    Sn = S[:LRD[i][0] - 1]
    t = l[LRD[i][2] - 1]
    while len(t) < LRD[i][1] - LRD[i][0] + 1:
        t += t
    Sn += t[:LRD[i][1] - LRD[i][0] + 1]
    Sn += S[LRD[i][1]:]
    S = Sn
    print(int(S) % mod)

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree:
    """
    op: 区間取得クエリでreduceする際に使う演算子
    apply: 更新則の適用
    comp: 更新則の合成
    
    range_query: reduce(op, (apply(x,m) for x,m in zip(X,M)))
    
    満たすべき性質:
    
    集合X (要素)
    op[+]: X,X -> X
    (X, op)はモノイド
    
    集合M (更新則)
    comp[*]: M,M -> M
    (M, compose)はモノイド
    
    apply[f(x,m,n)]: X,M,Z+ -> X
    (Z+は区間長)
    
    f(x,e_M,n) = x
    f(x,m*n,p) = f(f(x,m,p),n,p)
    f(x,m,p)+f(y,m,q) = f(x+y,m,p+q)
    
    参考: https://algo-logic.info/segment-tree/#toc_id_3
    """
    @classmethod
    def all_identity(cls, op, op_e, comp, comp_e, apply, size):
        size = 1 << (size-1).bit_length()
        return cls(
            op,
            op_e,
            comp,
            comp_e,
            apply,
            [op_e]*(2*size),
            [comp_e]*size
        )

    @classmethod
    def from_initial_data(cls, op, op_e, comp, comp_e, apply, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [op_e]*(2*size)
        temp[size:size+len(data)] = data

        for i in reversed(range(size)):
            temp[i] = op(temp[2*i],temp[2*i+1])
        return cls(
            op,
            op_e,
            comp,
            comp_e,
            apply,
            temp,
            [comp_e]*size
        )

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, op, op_e, comp, comp_e, apply, data, lazy):
        self.op = op
        self.op_e = op_e
        self.comp = comp
        self.comp_e = comp_e
        self.apply = apply
        self.data = data
        self.lazy = lazy
        self.size = len(self.data)//2
        self.depth = self.size.bit_length()-1
        self._l_indices = [0]*self.depth
        self._r_indices = [0]*self.depth
    
    def _update_indices(self, i, l):
        m = i//(i&-i)
        i >>= 1
        for k in range(self.depth):
            l[k] = i if i < m else 0
            i >>= 1
    
    
    def _propagate_top_down(self):
        data = self.data
        lazy = self.lazy
        apply = self.apply
        comp = self.comp
        comp_e = self.comp_e
        k = self.size >> 1
        
        for i,j in zip(reversed(self._l_indices), reversed(self._r_indices)):
            if i > 0:
                temp = lazy[i]
                if temp != comp_e:
                    lazy[i] = comp_e
                    a = i << 1
                    b = a | 1
                    data[a] = apply(data[a], temp, k)
                    data[b] = apply(data[b], temp, k)
                    if k > 1:
                        lazy[a] = comp(lazy[a], temp)
                        lazy[b] = comp(lazy[b], temp)
            if i < j:
                temp = lazy[j]
                if temp != comp_e:
                    lazy[j] = comp_e
                    a = j << 1
                    b = a | 1
                    data[a] = apply(data[a], temp, k)
                    data[b] = apply(data[b], temp, k)
                    if k > 1:
                        lazy[a] = comp(lazy[a], temp)
                        lazy[b] = comp(lazy[b], temp)
            k >>= 1
            
    def _propagate_bottom_up(self):
        data = self.data
        op = self.op
        for i,j in zip(self._l_indices, self._r_indices):
            if i < j:
                data[j] = op(data[j<<1],data[j<<1|1])
            if i > 0:
                data[i] = op(data[i<<1],data[i<<1|1])
    
    def update_interval(self, l, r, m):
        lazy = self.lazy
        data = self.data
        comp = self.comp
        apply = self.apply
        
        l += self.size
        r += self.size
        self._update_indices(l, self._l_indices)
        self._update_indices(r, self._r_indices)
        self._propagate_top_down()
        k = 1
        while l < r:
            if l & 1:
                data[l] = apply(data[l],m,k)
                if k > 1:
                    lazy[l] = comp(lazy[l],m)
                l += 1
            if r & 1:
                r -= 1
                data[r] = apply(data[r],m,k)
                if k > 1:
                    lazy[r] = comp(lazy[r],m)
            l >>= 1
            r >>= 1
            k <<= 1
        self._propagate_bottom_up()
    
    def get_interval(self, l, r):
        data = self.data
        op = self.op
        
        l += self.size
        r += self.size
        self._update_indices(l, self._l_indices)
        self._update_indices(r, self._r_indices)
        self._propagate_top_down()
        
        lx = self.op_e
        rx = self.op_e
        while l < r:
            if l & 1:
                lx = op(lx, data[l])
                l += 1
            if r & 1:
                r -= 1
                rx = op(data[r], rx)
            l >>= 1
            r >>= 1
        return op(lx,rx)

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

MOD = 998244353

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

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

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


# (sum, left_ind)

def compose(x,m):
    return x if m == 0 else m

def apply(x,m,l):
    if m == 0:
        return x
    _,left_ind = x
    return ((m*ones[l])%MOD, left_ind)
def op(a,b):
    x,i = a
    y,j = b
    return (x+y*power[j-i])%MOD, i

seg = LazySegmentTree.from_initial_data(
            op,
            (0,0), 
            compose,
            0,
            apply,
            [(1,i) for i in range(N)])

m = map(int,read().split())

for l,r,d in zip(m,m,m):
    l,r = N-r,N-l
    seg.update_interval(l,r+1,d)
    print(seg.get_interval(0,N)[0])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class LazySeg:
    def __init__(self, aa):
        n = 1 << (len(aa)-1).bit_length()
        tree = [0]*(2*n-1)
        lazy = [-1]*(2*n-1)
        tree[n-1:n-1+len(aa)] = aa
        for u in range(n-2, -1, -1):
            tree[u] = tree[u*2+1]+tree[u*2+2]
        self.tree = tree
        self.lazy = lazy
        self.n = n

    def prop(self, u, l, r):
        lazy = self.lazy
        v = lazy[u]
        if v==-1:return
        self.tree[u] = ((pow(10, r-l, md)-1)*inv9*v*pow(10, l, md))%md
        if l+1 < r:
            lazy[u*2+1] = lazy[u]
            lazy[u*2+2] = lazy[u]
        lazy[u] = -1
        self.lazy = lazy

    def update(self, l, r, a, u=0, tl=0, tr=-1):
        if tr == -1: tr = self.n
        self.prop(u,tl,tr)
        if r <= tl or tr <= l: return
        if l <= tl and tr <= r:
            self.lazy[u] = a
            self.prop(u,tl,tr)
            return
        tm = (tl+tr)//2
        self.update(l, r, a, u*2+1, tl, tm)
        self.update(l, r, a, u*2+2, tm, tr)
        self.tree[u]=(self.tree[u*2+1]+self.tree[u*2+2])%md

    def sum(self, l, r, u=0, tl=0, tr=-1):
        res = 0
        if tr == -1: tr = self.n
        if r <= tl or tr <= l: return 0
        self.prop(u, tl, tr)
        if l <= tl and tr <= r:return self.tree[u]
        tm = (tl+tr)//2
        res += self.sum(l, r, u*2+1, tl, tm)
        res += self.sum(l, r, u*2+2, tm, tr)
        res %= md
        return res

md = 998244353
inv9 = pow(9, md-2, md)
n,q=MI()
st=LazySeg([0]*n)
st.update(0,n,1)
for _ in range(q):
    l,r,d=MI()
    l,r=n-r,n-l
    st.update(l,r+1,d)
    print(st.sum(0,n))

Submission status: Time Limit Exceeded

Solution code:
# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# from time import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

# mod = int(1e9+7)
mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n,q = readInt()
    s = ['1' for i in range(n)]
    for i in range(q):
        l,r,d = readInt()
        s[l-1:r] = [str(d) for j in range(r-l+1)]
        x = int(''.join(s))
        print(x%mod)
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())

s = '1'*n

for i in range(q):
  l,r,d = map(int, input().split())
  ss = str(d) * (r-l+1)
  s = s[:l-1] + ss + s[r:]
  print(int(s) % 998244353)

Submission status: Time Limit Exceeded

Solution code:

def to_int(target, MOD):
    result = target[0]
    for i in range(1, len(target)):
        result *= 10
        result += target[i]
        result %= MOD

    return result


def main():
    N, Q = [int(x) for x in input().split()]
    MOD = 998244353
    S = [1] * N

    for _ in range(Q):
        l, r, d = [int(x) for x in input().split()]
        x = [d] * (r - l + 1)
        new_str = S[:l-1]
        new_str.extend(x)
        new_str.extend(S[r:])
        S = new_str

        print(to_int(S, MOD))


if __name__ == '__main__':
    main()