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: Wrong Answer

Solution code:
class LazySegmentTree:
    # 0-indexed
    # 2^m
    # ref. https://yukicoder.me/submissions/470340
    def __init__(self, length, op=min, e=lambda: 0, act=lambda f, x: f if f != 0 else x, composition=lambda f, g: g, idf=lambda: 0):
        """
        :param length: length of initial values
        :param op: operator, op(x, y) -> z
        :param e: function that return identity element for op
        """
        self.op = op
        self.e = e
        self.act = act
        self.composition = composition
        self.n = 1
        self.idf = idf
        while self.n < length:
            self.n *= 2  # pow2
        self.dat_v = [self.e()] * (2 * self.n - 1)
        self.dat_f = [self.idf()] * (2 * self.n - 1)

    def initialize(self, x_list):
        """
        initialize data
        :param x_list: initial values fot list
        :return:
        """
        assert len(x_list) <= self.n
        # update base
        # ith -> n - 1 + i
        for i, x in enumerate(x_list):
            self.dat_v[self.n - 1 + i] = x
        # upper values
        for i in range(self.n - 2, -1, -1):
            self.dat_v[i] = self.op(self.dat_v[2 * i + 1], self.dat_v[2 * i + 2])

    def _eval_at(self, i):
        return self.act(self.dat_f[i], self.dat_v[i])

    def _propagate_at(self, i):
        self.dat_v[i] = self._eval_at(i)
        self.dat_f[i * 2 + 1] = self.composition(self.dat_f[i * 2 + 1], self.dat_f[i])
        self.dat_f[i * 2 + 2] = self.composition(self.dat_f[i * 2 + 2], self.dat_f[i])
        self.dat_f[i] = self.idf()

    def _propagate_above(self, i):
        history = []
        while i > 0:
            i = (i - 1) // 2
            history.append(i)
        for j in reversed(history):
            self._propagate_at(j)

    def _re_calculate_above(self, i):
        while i > 0:
            i = (i - 1) // 2
            self.dat_v[i] = self.op(self._eval_at(2 * i + 1), self._eval_at(2 * i + 2))

    def operate_range(self, p, q, f):
        """
        apply operator f for [p, q)
        :param p: int
        :param q: int
        :param f: operator
        :return: None
        """
        if p >= q:
            return None
        p0 = p + self.n - 1
        q0 = q + self.n - 2
        # propagate from top
        self._propagate_above(p0)
        self._propagate_above(q0)
        # compose f
        while q0 - p0 > 1:
            if p0 & 1 == 0:
                self.dat_f[p0] = self.composition(self.dat_f[p0], f)
            if q0 & 1 == 1:
                self.dat_f[q0] = self.composition(self.dat_f[q0], f)
                q0 -= 1
            p0 = p0 // 2
            q0 = (q0 - 1) // 2
        if p0 == q0:
            self.dat_f[p0] = self.composition(self.dat_f[p0], f)
        else:
            self.dat_f[p0] = self.composition(self.dat_f[p0], f)
            self.dat_f[q0] = self.composition(self.dat_f[q0], f)
        # re-calculate above
        self._re_calculate_above(p + self.n - 1)
        self._re_calculate_above(q + self.n - 2)

    def set_val(self, k, v):
        """
        update k-th(0-indexed) value with v
        :param k: index to set(0-indexed)
        :param v: value to set
        :return: None
        """
        k += self.n - 1
        self.dat_v[k] = v
        self.dat_f[k] = self.idf()
        self._re_calculate_above(k)

    def query(self, p, q):
        """
        :param p: int
        :param q: int
        :return: "minimum" value in [p, q)
        """
        if q <= p:
            return self.e()
        p0 = p + self.n - 1
        q0 = q + self.n - 2
        self._propagate_above(p0)
        self._propagate_above(q0)
        vl = self.e()
        vr = self.e()
        while q0 - p0 > 1:
            if p0 & 1 == 0:
                vl = self.op(vl, self._eval_at(p0))
            if q0 & 1 == 1:
                vr = self.op(self._eval_at(q0), vr)
                q0 -= 1
            p0 = p0 // 2
            q0 = (q0 - 1) // 2
        if p0 == q0:
            res = self.op(self.op(vl, self._eval_at(p0)), vr)
        else:
            res = self.op(self.op(vl, self._eval_at(p0)), self.op(self._eval_at(q0), vr))
        return res


MOD = 998244353
MOD_INV_9 = pow(9, MOD - 2, MOD)


def op_con(x, y):
    if y[1] == 0:
        return x
    else:
        return (x[0] * y[1] + y[0]) % MOD, (x[1] * y[1]) % MOD


def e_zero():
    return 0, 0


def act_change(f, x):
    if f == 0:
        return x
    else:
        return ((x[1] - 1) * MOD_INV_9 * f) % MOD, x[1]


def com_change(f, g):
    if g == 0:
        return f
    else:
        return g


def idf_change():
    return 0


def solve(n, q, lrd_list):

    lsq = LazySegmentTree(n, op_con, e_zero, act=act_change, composition=com_change, idf=idf_change)
    lsq.initialize([(1, 10)] * n)

    res = []

    for i in range(q):
        l, r, d = lrd_list[i]
        # find where
        lsq.operate_range(l - 1, r, d)
        res.append(lsq.query(0, n)[0])

    return res


def main():
    n, q = map(int, input().split())
    lrd_list = [tuple(map(int, input().split())) for _ in range(q)]
    res = solve(n, q, lrd_list)
    for r in res:
        print(r)


def test():
    assert solve(8, 5, [(3, 6, 2), (1, 4, 7), (3, 8, 3), (2, 2, 2), (4, 5, 1)]) == [11222211, 77772211, 77333333, 72333333, 72311333]
    assert solve(200000, 1, [(123, 456, 7)]) == [641437905]


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
class LazySegmentTree:
    # 0-indexed
    # 2^m
    # ref. https://yukicoder.me/submissions/470340
    def __init__(self, length, op=min, e=lambda: 0, act=lambda f, x: f if f != 0 else x, composition=lambda f, g: g, idf=lambda: 0):
        """
        :param length: length of initial values
        :param op: operator, op(x, y) -> z
        :param e: function that return identity element for op
        """
        self.op = op
        self.e = e
        self.act = act
        self.composition = composition
        self.n = 1
        self.idf = idf
        while self.n < length:
            self.n *= 2  # pow2
        self.dat_v = [self.e()] * (2 * self.n - 1)
        self.dat_f = [self.idf()] * (2 * self.n - 1)

    def initialize(self, x_list):
        """
        initialize data
        :param x_list: initial values fot list
        :return:
        """
        assert len(x_list) <= self.n
        # update base
        # ith -> n - 1 + i
        for i, x in enumerate(x_list):
            self.dat_v[self.n - 1 + i] = x
        # upper values
        for i in range(self.n - 2, -1, -1):
            self.dat_v[i] = self.op(self.dat_v[2 * i + 1], self.dat_v[2 * i + 2])

    def _eval_at(self, i):
        return self.act(self.dat_f[i], self.dat_v[i])

    def _propagate_at(self, i):
        self.dat_v[i] = self._eval_at(i)
        self.dat_f[i * 2 + 1] = self.composition(self.dat_f[i * 2 + 1], self.dat_f[i])
        self.dat_f[i * 2 + 2] = self.composition(self.dat_f[i * 2 + 2], self.dat_f[i])
        self.dat_f[i] = self.idf()

    def _propagate_above(self, i):
        history = []
        while i > 0:
            i = (i - 1) // 2
            history.append(i)
        for j in reversed(history):
            self._propagate_at(j)

    def _re_calculate_above(self, i):
        while i > 0:
            i = (i - 1) // 2
            self.dat_v[i] = self.op(self._eval_at(2 * i + 1), self._eval_at(2 * i + 2))

    def operate_range(self, p, q, f):
        """
        apply operator f for [p, q)
        :param p: int
        :param q: int
        :param f: operator
        :return: None
        """
        if p >= q:
            return None
        p0 = p + self.n - 1
        q0 = q + self.n - 2
        # propagate from top
        self._propagate_above(p0)
        self._propagate_above(q0)
        # compose f
        while q0 - p0 > 1:
            if p0 & 1 == 0:
                self.dat_f[p0] = self.composition(self.dat_f[p0], f)
            if q0 & 1 == 1:
                self.dat_f[q0] = self.composition(self.dat_f[q0], f)
                q0 -= 1
            p0 = p0 // 2
            q0 = (q0 - 1) // 2
        if p0 == q0:
            self.dat_f[p0] = self.composition(self.dat_f[p0], f)
        else:
            self.dat_f[p0] = self.composition(self.dat_f[p0], f)
            self.dat_f[q0] = self.composition(self.dat_f[q0], f)
        # re-calculate above
        self._re_calculate_above(p + self.n - 1)
        self._re_calculate_above(q + self.n - 2)

    def set_val(self, k, v):
        """
        update k-th(0-indexed) value with v
        :param k: index to set(0-indexed)
        :param v: value to set
        :return: None
        """
        k += self.n - 1
        self.dat_v[k] = v
        self.dat_f[k] = self.idf()
        self._re_calculate_above(k)

    def query(self, p, q):
        """
        :param p: int
        :param q: int
        :return: "minimum" value in [p, q)
        """
        if q <= p:
            return self.e()
        p0 = p + self.n - 1
        q0 = q + self.n - 2
        self._propagate_above(p0)
        self._propagate_above(q0)
        vl = self.e()
        vr = self.e()
        while q0 - p0 > 1:
            if p0 & 1 == 0:
                vl = self.op(vl, self._eval_at(p0))
            if q0 & 1 == 1:
                vr = self.op(self._eval_at(q0), vr)
                q0 -= 1
            p0 = p0 // 2
            q0 = (q0 - 1) // 2
        if p0 == q0:
            res = self.op(self.op(vl, self._eval_at(p0)), vr)
        else:
            res = self.op(self.op(vl, self._eval_at(p0)), self.op(self._eval_at(q0), vr))
        return res


MOD = 998244353
MOD_INV_9 = pow(9, MOD - 2, MOD)


def op_con(x, y):
    if y == (0, 0):
        return x
    else:
        return (x[0] * y[1] + y[0]) % MOD, (x[1] * y[1]) % MOD


def e_zero():
    return 0, 0


def act_change(f, x):
    if f == 0:
        return x
    else:
        return ((x[1] - 1) * MOD_INV_9 * f) % MOD, x[1]


def com_change(f, g):
    if g == 0:
        return f
    else:
        return g


def idf_change():
    return 0


def solve(n, q, lrd_list):

    lsq = LazySegmentTree(n, op_con, e_zero, act=act_change, composition=com_change, idf=idf_change)
    lsq.initialize([(1, 10)] * n)

    res = []

    for i in range(q):
        l, r, d = lrd_list[i]
        # find where
        lsq.operate_range(l - 1, r, d)
        res.append(lsq.query(0, n)[0])

    return res


def main():
    n, q = map(int, input().split())
    lrd_list = [tuple(map(int, input().split())) for _ in range(q)]
    res = solve(n, q, lrd_list)
    for r in res:
        print(r)


def test():
    assert solve(8, 5, [(3, 6, 2), (1, 4, 7), (3, 8, 3), (2, 2, 2), (4, 5, 1)]) == [11222211, 77772211, 77333333, 72333333, 72311333]
    assert solve(200000, 1, [(123, 456, 7)]) == [641437905]


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

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) * (2**30 + 1)) for i in range(N)][::-1]
def f(a, b):
    qa, ra = divmod(a, 2**30)
    qb, rb = divmod(b, 2**30)
    return ((qa + qb) % mod) * 2**30 + (ra + rb) % mod

def g(a, b):
    qa, ra = divmod(a, 2**30)
    return ((qa * b) % mod) * 2**30 + ra


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

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) // 2**30]
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

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

    
class LazySegmentTree():
    def __init__(self, n, op, e, mapping, composition, id):
        self.n = n
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.id = id
        self.log = (n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [e] * (2 * self.size)
        self.lz = [id] * (self.size)
 
    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])
 
    def all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])
 
    def push(self, k):
        self.all_apply(2 * k, self.lz[k])
        self.all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.id
 
    def build(self, arr):
        #assert len(arr) == self.n
        for i, a in enumerate(arr):
            self.d[self.size + i] = a
        for i in range(1, self.size)[::-1]:
            self.update(i)
 
    def set(self, p, x):
        #assert 0 <= p < self.n
        p += self.size
        for i in range(1, self.log + 1)[::-1]:
            self.push(p >> i)
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)
 
    def get(self, p):
        #assert 0 <= p < self.n
        p += self.size
        for i in range(1, self.log + 1):
            self.push(p >> i)
        return self.d[p]
 
    def prod(self, l, r):
        #assert 0 <= l <= r <= self.n
        if l == r: return self.e
        l += self.size
        r += self.size
        for i in range(1, self.log + 1)[::-1]:
            if ((l >> i) << i) != l: self.push(l >> i)
            if ((r >> i) << i) != r: self.push(r >> i)
        sml = smr = self.e
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)
 
    def all_prod(self):
        return self.d[1]
 
    def apply(self, p, f):
        #assert 0 <= p < self.n
        p += self.size
        for i in range(1, self.log + 1)[::-1]:
            self.push(p >> i)
        self.d[p] = self.mapping(f, self.d[p])
        for i in range(1, self.log + 1):
            self.update(p >> i)
 
    def range_apply(self, l, r, f):
        #assert 0 <= l <= r <= self.n
        if l == r: return
        l += self.size
        r += self.size
        for i in range(1, self.log + 1)[::-1]:
            if ((l >> i) << i) != l: self.push(l >> i)
            if ((r >> i) << i) != r: self.push((r - 1) >> i)
        l2 = l
        r2 = r
        while l < r:
            if l & 1:
                self.all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.all_apply(r, f)
            l >>= 1
            r >>= 1
        l = l2
        r = r2
        for i in range(1, self.log + 1):
            if ((l >> i) << i) != l: self.update(l >> i)
            if ((r >> i) << i) != r: self.update((r - 1) >> i)
 
    def max_right(self, l, g):
        #assert 0 <= l <= self.n
        #assert g(self.e)
        if l == self.n: return self.n
        l += self.size
        for i in range(1, self.log + 1)[::-1]:
            self.push(l >> i)
        sm = self.e
        while True:
            while l % 2 == 0: l >>= 1
            if not g(self.op(sm, self.d[l])):
                while l < self.size:
                    self.push(l)
                    l = 2 * l
                    if g(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) == l: return self.n
 
    def min_left(self, r, g):
        #assert 0 <= r <= self.n
        #assert g(self.e)
        if r == 0: return 0
        r += self.size
        for i in range(1, self.log + 1)[::-1]:
            self.push((r - 1) >> i)
        sm = self.e
        while True:
            r -= 1
            while r > 1 and r % 2: r >>= 1
            if not g(self.op(self.d[r], sm)):
                while r < self.size:
                    self.push(r)
                    r = 2 * r + 1
                    if g(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) == r: return 0

mod = 998244353
 
def op(x, y):
    xv, xr = divmod(x,1<<31)
    yv, yr = divmod(y,1<<31)
    return ((xv + yv)%mod << 31) + (xr + yr)%mod
def mapping(p, x):
    xv, xr = divmod(x,1<<31)
    if p != -1:
        return ((p*xr%mod) << 31) + xr
    else:
        return x
def composition(p,q):
    if p == -1:
        return q
    return p

n,q = map(int,input().split())
LST = LazySegmentTree(n,op,0,mapping,composition,-1)

def build_exp(n, b):
    res = [0] * (n + 1)
    res[0] = 1
    for i in range(n):
        res[i + 1] = res[i] * b % mod
    return res
 
exp = build_exp(n-1, 10)

#print(res)
LST.build(exp[::-1])
#print(LST.all_prod()>>31)
for _ in range(q):
    l,r,D = map(int,input().split())
    LST.range_apply(l-1,r,D)
    print((LST.all_prod()>>31)%mod)

Submission status: Wrong Answer

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

    
class LazySegmentTree():
    def __init__(self, n, op, e, mapping, composition, id):
        self.n = n
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.id = id
        self.log = (n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [e] * (2 * self.size)
        self.lz = [id] * (self.size)
 
    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])
 
    def all_apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])
 
    def push(self, k):
        self.all_apply(2 * k, self.lz[k])
        self.all_apply(2 * k + 1, self.lz[k])
        self.lz[k] = self.id
 
    def build(self, arr):
        #assert len(arr) == self.n
        for i, a in enumerate(arr):
            self.d[self.size + i] = a
        for i in range(1, self.size)[::-1]:
            self.update(i)
 
    def set(self, p, x):
        #assert 0 <= p < self.n
        p += self.size
        for i in range(1, self.log + 1)[::-1]:
            self.push(p >> i)
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)
 
    def get(self, p):
        #assert 0 <= p < self.n
        p += self.size
        for i in range(1, self.log + 1):
            self.push(p >> i)
        return self.d[p]
 
    def prod(self, l, r):
        #assert 0 <= l <= r <= self.n
        if l == r: return self.e
        l += self.size
        r += self.size
        for i in range(1, self.log + 1)[::-1]:
            if ((l >> i) << i) != l: self.push(l >> i)
            if ((r >> i) << i) != r: self.push(r >> i)
        sml = smr = self.e
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)
 
    def all_prod(self):
        return self.d[1]
 
    def apply(self, p, f):
        #assert 0 <= p < self.n
        p += self.size
        for i in range(1, self.log + 1)[::-1]:
            self.push(p >> i)
        self.d[p] = self.mapping(f, self.d[p])
        for i in range(1, self.log + 1):
            self.update(p >> i)
 
    def range_apply(self, l, r, f):
        #assert 0 <= l <= r <= self.n
        if l == r: return
        l += self.size
        r += self.size
        for i in range(1, self.log + 1)[::-1]:
            if ((l >> i) << i) != l: self.push(l >> i)
            if ((r >> i) << i) != r: self.push((r - 1) >> i)
        l2 = l
        r2 = r
        while l < r:
            if l & 1:
                self.all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self.all_apply(r, f)
            l >>= 1
            r >>= 1
        l = l2
        r = r2
        for i in range(1, self.log + 1):
            if ((l >> i) << i) != l: self.update(l >> i)
            if ((r >> i) << i) != r: self.update((r - 1) >> i)
 
    def max_right(self, l, g):
        #assert 0 <= l <= self.n
        #assert g(self.e)
        if l == self.n: return self.n
        l += self.size
        for i in range(1, self.log + 1)[::-1]:
            self.push(l >> i)
        sm = self.e
        while True:
            while l % 2 == 0: l >>= 1
            if not g(self.op(sm, self.d[l])):
                while l < self.size:
                    self.push(l)
                    l = 2 * l
                    if g(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) == l: return self.n
 
    def min_left(self, r, g):
        #assert 0 <= r <= self.n
        #assert g(self.e)
        if r == 0: return 0
        r += self.size
        for i in range(1, self.log + 1)[::-1]:
            self.push((r - 1) >> i)
        sm = self.e
        while True:
            r -= 1
            while r > 1 and r % 2: r >>= 1
            if not g(self.op(self.d[r], sm)):
                while r < self.size:
                    self.push(r)
                    r = 2 * r + 1
                    if g(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) == r: return 0
mod = 998244353

 
def op(x, y):
    x_val = x >> 33
    y_val = y >> 33
    dg = (x - (x_val<<33)) + (y - (y_val<<33))

    if x_val + y_val >= mod:
        val = x_val + y_val - mod
    else:
        val = x_val + y_val

    if dg >= mod:
        dg -= mod
    
    return (val<<33) + dg

def mapping(p, x):
    if p == -1:
        return x
    dg = x - ((x>>33)<<33)
    return (p*dg%mod) + dg
    
 
def composition(p, q):
    if p == -1:
        return q
    return p

n,q = map(int,input().split())
res = [0]*n
LST = LazySegmentTree(n,op,0,mapping,composition,-1)

v = 0
ten = 1
for i in range(n):
    res[i] = (ten<<33) + ten
    ten = ten*10%mod

print(res)
LST.build(res[::-1])
print(LST.all_prod()>>33)
for _ in range(q):
    l,r,D = map(int,input().split())
    LST.range_apply(l-1,r,D)
    print((LST.all_prod()>>33)%mod)

Submission status: Wrong Answer

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

ans = "1" * n

for i in range(q):
    l, r, d = map(int, input().split())
    t = str(d)*(r-l+1)
    ans = ans[0:l-1] + t + ans[r:]

    ans = str(int(ans)%mod)
print(ans)

Submission status: Wrong Answer

Solution code:
class LazySegmentTree():
  def __init__(self, n, op, e, mapping, composition, id):
    self.n = n
    self.op = op
    self.e = e
    self.mapping = mapping
    self.composition = composition
    self.id = id
    self.log = (n - 1).bit_length()
    self.size = 1 << self.log
    self.data = [(e,e)] * (2 * self.size)
    self.lazy = [id] * (self.size)

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

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

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

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

  def set(self, p, x):
    #assert 0 <= p < self.n
    p += self.size
    for i in range(self.log,0,-1):
      self.push(p >> i)
    self.data[p] = x
    for i in range(1, self.log + 1):
      self.update(p >> i)

  def get(self, p):
    #assert 0 <= p < self.n
    p += self.size
    for i in range(1, self.log + 1):
      self.push(p >> i)
    return self.data[p]

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

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

  def apply(self, p, f):
    #assert 0 <= p < self.n
    p += self.size
    for i in range(1, self.log + 1)[::-1]:
      self.push(p >> i)
    self.data[p] = self.mapping(f, self.data[p])
    for i in range(1, self.log + 1):
      self.update(p >> i)

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

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

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

import sys
input = sys.stdin.buffer.readline

INF = 10**18
MOD = 998244353

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

def op(x, y):
  xv, xr = x
  yv, yr = y
  return (xv + yv) % MOD, (xr + yr) % MOD

def mapping(p, x): #pが更新後の値, xが更新する前の値
  xv, xr = x
  if p != INF:
    return p * xr % MOD, xr
  return x

def composition(p, q):
  if p != INF:
    return p
  return q

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

arr = [(e,e) for e in lis]

e = 0
id = INF

lst = LazySegmentTree(N, op, e, mapping, composition, id)
lst.build(arr)

ans = [0]*Q

for _ in range(Q):
  l, r, d = map(int, input().split())
  lst.range_apply(l - 1, r, d)
  v = lst.all_prod()
  ans.append(v[0])


print(*ans, sep='\n')