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: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

class LazySegmentTree:
  
  __slots__ = ["n", "seg", "x_unit", "m_unit", "f", "g", "h", "lazy"]

  def __init__(self, n, p, x_unit, m_unit, f, g, h):
    self.n = n
    self.seg = p*2
    self.x_unit = x_unit
    self.m_unit = m_unit
    self.f = f
    self.g = g
    self.h = h
    for i in range(self.n-1, 0, -1):
      self.seg[i] = self.f(self.seg[i<<1], self.seg[(i<<1)+1])
    self.lazy = [m_unit] * (self.n * 2)

  def update(self, l, r, x):
    l += self.n
    r += self.n
    ll = l // (l & -l)
    rr = r // (r & -r) - 1
    for shift in range(ll.bit_length()-1, 0, -1):
      i = ll >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1], self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    for shift in range(rr.bit_length()-1, 0, -1):
      i = rr >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1],   self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    while l < r:
      if l & 1:
        self.lazy[l] = self.h(self.lazy[l], x)
        l += 1
      if r & 1:
        r -= 1
        self.lazy[r] = self.h(self.lazy[r], x)
      l >>= 1
      r >>= 1
    while ll > 1:
      ll >>= 1
      self.seg[ll] = self.f(self.g(self.seg[ll << 1], self.lazy[ll << 1]), self.g(self.seg[(ll << 1)+1], self.lazy[(ll << 1)+1]))
      self.lazy[ll] = self.m_unit
    while rr > 1:
      rr >>= 1
      self.seg[rr] = self.f(self.g(self.seg[rr << 1], self.lazy[rr << 1]), self.g(self.seg[(rr << 1)+1], self.lazy[(rr << 1)+1]))
      self.lazy[rr] = self.m_unit

  def query(self, l, r):
    l += self.n
    r += self.n
    ll = l // (l & -l)
    rr = r // (r & -r) - 1
    for shift in range(ll.bit_length()-1, 0, -1):
      i = ll >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1], self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    for shift in range(rr.bit_length()-1, 0, -1):
      i = rr >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1],   self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    ans_l = ans_r = self.x_unit
    while l < r:
      if l & 1:
        ans_l = self.f(ans_l, self.g(self.seg[l], self.lazy[l]))
        l += 1
      if r & 1:
        r -= 1
        ans_r = self.f(self.g(self.seg[r], self.lazy[r]), ans_r)
      l >>= 1
      r >>= 1
    return self.f(ans_l, ans_r)

mod=998244353
n,q=map(int,input().split())
digit=[1]
for _ in range(n):
  digit.append(digit[-1]*10%mod)
inv9=pow(9,mod-2,mod)
def f(a,b):
  asum,alen=divmod(a,200001)
  bsum,blen=divmod(b,200001)
  return ((digit[blen]*asum+bsum)%mod)*200001+alen+blen
def g(x,y):
  if y is None:
    return x
  _,xlen=divmod(x,200001)
  return ((digit[xlen]-1)*inv9*y%mod)*200001+xlen
def h(x,y):
  if y is None:
    return x
  return y
seg=LazySegmentTree(n,[200002]*n,0,None,f,g,h)
for _ in range(q):
  l,r,d=map(int,input().split())
  seg.update(l-1,r,d)
  print(seg.query(0,n)//200001)

Submission status: Accepted

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)<<33) + 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: Accepted

Solution code:
# coding: utf-8
import sys

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

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


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

class BIT:
    # init_val[0] -> bins[1]
    def __init__(self, n, init=0, init_val=None):
        '''
        n : length of vals
        init : init_val in each bins
        init_val : if specified, update is performed
        ** applioed seqs -> seq[0] -> bins[1]
        '''
        self.n = n
        self.init = init
        self.k = n.bit_length()
        self.bins = [init] * (n+1)
        self.l2 = 2 ** self.k

        if init_val !=None:
            self.update_set(init_val)

    def update_set(self, vals):
        if len(vals) > self.n:
            raise ValueError('Length is too long!')
        for i, val in enumerate(vals):
            bi = i+1
            if bi & 1:
                self.bins[bi] = val
            else:
                ret = self.init
                most_sig = (bi & -bi)
                n_bit = bi - 1
                while n_bit:
                    v = n_bit & -n_bit
                    if most_sig  >= v:break
                    ret = self.compare(ret, self.bins[n_bit])
                    n_bit -= v
                self.bins[bi] = ret

    def compare(self, l, r):
        '''comparison-criteria'''
        return l+ r

    def minus(self, val):
        '''define the negative value for caliculations'''
        return -val

    def update(self, idx, by):
        '''idx : 0-started index'''
        while idx < len(self.bins):
            self.bins[idx] = self.compare(self.bins[idx], by)
            idx += (idx & -idx)

    def get_sum(self, idx):
        '''idx: 0-indexed'''
        ans = self.init
        #idx += 1
        while idx:
            ans = self.compare(ans, self.bins[idx])
            idx -= (idx & -idx)
        return ans

    def eval_between(self, l, r):
        ''' l, r : 0-indexed '''
        return self.compare(self.get_sum(r), self.get_sum(self.get_sum(l-1)))

    def lower_bound(self, SUM):
        '''return idx sum of which is less or equal to SUM'''
        if SUM <= 0:
            return 0
        l = 0
        r = self.l2
        while r > 0:
            if l+r <= self.n and self.bins[l+r] < SUM:
                SUM -= self.bins[l + r]
                l += r
            r >>= 1
        return l + 1

    def upper_bound(self, SUM):
        '''return idx sum of which is more than SUM'''
        l = 0
        r = self.l2
        #print(r,r,r,r,r)
        while r > 0:
            if l + r <= self.n and self.bins[l + r] <= SUM:
                SUM -= self.bins[l + r]
                l += r
            r >>= 1
        return l + 1

class std_map:
    '''
    std_map function with restricted value range.
    n : max val permitted for map
    init : val if key is not specified
    '''

    def __init__(self, n, init):
        self.size = n
        self.keys = set()
        self.bit = BIT(n + 1)# memory keys
        self.dic = [init] * (n + 1)# memory vals

    def __contains__(self, key):  # keyを持つか
        return key in self.keys

    def __getitem__(self, key):  # keyに対するvalueを返す
        return self.dic[key]

    def __setitem__(self, key, value):  # dic[key]をvalueで置き換える
        if not key in self.keys:
            self.bit.update(key, 1)
            self.keys.add(key)
        self.dic[key] = value

    def remove(self, key):  # keyをmapから取り除く
        self.keys.remove(key)
        self.bit.update(key, -1)

    def lower_bound(self, k):  # k以下の最大のkeyを返す
        return self.bit.lower_bound(self.bit.get_sum(k))

    def upper_bound(self, k):  # kより大きい最小のkeyを返す
        return self.bit.upper_bound(self.bit.get_sum(k))

    def kth_key(self, k):  # k番目に小さいkeyを返す
        return self.bit.lower_bound(k)

    def kth_value(self, k):  # k番目に小さいkeyに対するvalueを返す
        return self.dic[self.kth_key(k)]

    def prev_k(self, k):  # kの一つ前のkeyを返す
        idx = self.bit.get_sum(k)
        if idx == 0:
            return -1
        return self.bit.lower_bound(idx - 1)

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

def run():
    N, Q = mapline()
    m = std_map(N, init = -1)
    m[1] = (N, 1)
    powmod = pow_mod(10, N - 1, mod)
    summod = [0]
    t = 0
    for p in powmod:
        t += p
        summod.append(t)


    ans = summod[N]

    for i in range(Q):
        #print(m.keys)
        l, r, d = mapline()

        s = m.lower_bound(l-1)

        #print(s)
        if s > 0:
            rr, dd = m[s]
            if l <= rr:
                #print(rr - s + 1, N-rr)
                ans -= summod[rr - s + 1] * powmod[N-rr] * dd
                ans %= mod
                m[s] = (l-1, dd)
                ans += summod[l - s] * powmod[N -l + 1] * dd
                ans %=mod
                if r < rr:
                    m[l] = (r, d)
                    ans += summod[r - l + 1] * powmod[N - r] * d
                    ans %= mod
                    m[r+1] = (rr, dd)
                    ans += summod[rr - r] * powmod[N - rr] * dd
                    ans %= mod
                    print(ans)
                    continue

        k = l - 1
        while True:
            s = m.upper_bound(k)
            #print(k, s)
            #print(m.bit.bins)
            if s == N+1:break
            if s <= r:
                rr, dd = m[s]
                m.remove(s)
                ans -= summod[rr - s + 1] * powmod[N - rr] * dd
                ans %= mod
                if rr > r:
                    m[r+1] = (rr, dd)
                    ans += summod[rr - r] * powmod[N - rr] * dd
                    ans %= mod
                    break
                k = rr
            else:
                break
        m[l] = (r, d)
        ans += summod[r - l + 1] * powmod[N - r] * d
        ans %= mod
        print(ans)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import typing

def _ceil_pow2(n: int) -> int:
    x = 0
    while (1 << x) < n:
        x += 1
    return x


class LazySegTree:
    def __init__(
            self,
            op: typing.Callable[[typing.Any, typing.Any], typing.Any],
            e: typing.Any,
            mapping: typing.Callable[[typing.Any, typing.Any], typing.Any],
            composition: typing.Callable[[typing.Any, typing.Any], typing.Any],
            id_: typing.Any,
            v: typing.Union[int, typing.List[typing.Any]]) -> None:
        self._op = op
        self._e = e
        self._mapping = mapping
        self._composition = composition
        self._id = id_

        if isinstance(v, int):
            v = [e] * v

        self._n = len(v)
        self._log = _ceil_pow2(self._n)
        self._size = 1 << self._log
        self._d = [e] * (2 * self._size)
        self._lz = [self._id] * self._size
        for i in range(self._n):
            self._d[self._size + i] = v[i]
        for i in range(self._size - 1, 0, -1):
            self._update(i)

    def set(self, p: int, x: typing.Any) -> None:
        assert 0 <= p < self._n

        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 get(self, p: int) -> typing.Any:
        assert 0 <= p < self._n

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

    def prod(self, left: int, right: int) -> typing.Any:
        assert 0 <= left <= right <= self._n

        if left == right:
            return self._e

        left += self._size
        right += self._size

        for i in range(self._log, 0, -1):
            if ((left >> i) << i) != left:
                self._push(left >> i)
            if ((right >> i) << i) != right:
                self._push(right >> i)

        sml = self._e
        smr = self._e
        while left < right:
            if left & 1:
                sml = self._op(sml, self._d[left])
                left += 1
            if right & 1:
                right -= 1
                smr = self._op(self._d[right], smr)
            left >>= 1
            right >>= 1

        return self._op(sml, smr)

    def all_prod(self) -> typing.Any:
        return self._d[1]

    def apply(self, left: int, right: typing.Optional[int] = None,
              f: typing.Optional[typing.Any] = None):
        assert f is not None

        if right is None:
            p = left
            assert 0 <= left < self._n

            p += self._size
            for i in range(self._log, 0, -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)
        else:
            assert 0 <= left <= right <= self._n
            if left == right:
                return

            left += self._size
            right += self._size

            for i in range(self._log, 0, -1):
                if ((left >> i) << i) != left:
                    self._push(left >> i)
                if ((right >> i) << i) != right:
                    self._push((right - 1) >> i)

            l2 = left
            r2 = right
            while left < right:
                if left & 1:
                    self._all_apply(left, f)
                    left += 1
                if right & 1:
                    right -= 1
                    self._all_apply(right, f)
                left >>= 1
                right >>= 1
            left = l2
            right = r2

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

    def max_right(
            self, left: int, g: typing.Callable[[typing.Any], bool]) -> int:
        assert 0 <= left <= self._n
        assert g(self._e)

        if left == self._n:
            return self._n

        left += self._size
        for i in range(self._log, 0, -1):
            self._push(left >> i)

        sm = self._e
        first = True
        while first or (left & -left) != left:
            first = False
            while left % 2 == 0:
                left >>= 1
            if not g(self._op(sm, self._d[left])):
                while left < self._size:
                    self._push(left)
                    left *= 2
                    if g(self._op(sm, self._d[left])):
                        sm = self._op(sm, self._d[left])
                        left += 1
                return left - self._size
            sm = self._op(sm, self._d[left])
            left += 1

        return self._n

    def min_left(self, right: int, g: typing.Any) -> int:
        assert 0 <= right <= self._n
        assert g(self._e)

        if right == 0:
            return 0

        right += self._size
        for i in range(self._log, 0, -1):
            self._push((right - 1) >> i)

        sm = self._e
        first = True
        while first or (right & -right) != right:
            first = False
            right -= 1
            while right > 1 and right % 2:
                right >>= 1
            if not g(self._op(self._d[right], sm)):
                while right < self._size:
                    self._push(right)
                    right = 2 * right + 1
                    if g(self._op(self._d[right], sm)):
                        sm = self._op(self._d[right], sm)
                        right -= 1
                return right + 1 - self._size
            sm = self._op(self._d[right], sm)

        return 0

    def _update(self, k: int) -> None:
        self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])

    def _all_apply(self, k: int, f: typing.Any) -> None:
        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: int) -> None:
        self._all_apply(2 * k, self._lz[k])
        self._all_apply(2 * k + 1, self._lz[k])
        self._lz[k] = self._id


keta_to_mint10 = [0]*300001
keta_to_mint = [0]*300001
MOD = 998244353

def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u


def main():

    def op(a,b):
        return (a[0]*keta_to_mint10[b[1]] + b[0])%MOD, a[1]+b[1]

    e = 0,0

    f_id = 0
    id_ = f_id
    def mapping(f,x):
        if f == f_id:
            return x
        else:
            return (keta_to_mint[x[1]]*f)%MOD, x[1]

    def composition(f,g):
        if f == f_id: return g
        else: return f


    n,q = map(int, input().split())
    a = [(1,1)]*n
    keta_to_mint10[0] = 1
    mod9 = modinv(9,MOD)
    for i in range(1,200001):
        keta_to_mint10[i] = (keta_to_mint10[i-1]*10)%MOD
        keta_to_mint[i] = ((keta_to_mint10[i]-1)*mod9)%MOD


    seg = LazySegTree(op, e, mapping, composition, id_, a)

    for _ in range(q):
        l,r,d = map(int, input().split())
        seg.apply(l-1,r,d)
        ans = seg.all_prod()[0]
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/opt/ac-library
# cython: cdivision=True
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "<atcoder/lazysegtree>" namespace "atcoder":
    cdef cppclass lazy_segtree[S, OP, E, F, mapping, composition, id]:
        lazy_segtree(vector[S] v)
        void set(int p, S x)
        S get(int p)
        S prod(int l, int r)
        S all_prod()
        void apply(int p, F f)
        void apply(int l, int r, F f)
        int max_right[G](int l)
        int min_left[G](int r)
DEF mod = 998244353
cdef struct s_t:
    long v, s
ctypedef long f_t
cdef extern from *:
    ctypedef int op_t "myop"
    ctypedef int e_t "mye"
    ctypedef int m_t "mymapping"
    ctypedef int c_t "mycomposition"
    ctypedef int i_t "myid"
    ctypedef int g_t "myg"
    cdef s_t myop(s_t a, s_t b)
    cdef s_t mye()
    cdef s_t mymapping(f_t f, s_t x)
    cdef f_t mycomposition(f_t f, f_t g)
    cdef f_t myid()
    cdef bool myg(s_t k)
cdef s_t myop(s_t a, s_t b):
    return s_t((a.v * b.s + b.v) % mod, (a.s * b.s) % mod)
cdef s_t mye():
    return s_t(0, 1)
cdef f_t myid():
    return -1
cdef s_t mymapping(f_t f, s_t x):
    if f == myid(): return x
    return s_t((x.s - 1) * 443664157 * f % mod, x.s)
cdef f_t mycomposition(f_t f, f_t g):
    if f == myid(): return g
    return f
from libc.stdio cimport getchar, printf
cdef inline long read():
    cdef long b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: return c
        c = c * 10 + b
cdef main():
    cdef long n = read(), i, l, r, d
    cdef lazy_segtree[s_t, op_t, e_t, f_t, m_t, c_t, i_t] *seg = new lazy_segtree[s_t, op_t, e_t, f_t, m_t, c_t, i_t](vector[s_t](n, s_t(1, 10)))
    for i in range(read()):
        l, r, d = read(), read(), read()
        seg.apply(l - 1, r, d)
        printf('%ld\n', seg.all_prod().v)
main()
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/opt/ac-library
# cython: cdivision=True
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "<atcoder/lazysegtree>" namespace "atcoder" nogil:
    cdef cppclass lazy_segtree[S, OP, E, F, mapping, composition, id]:
        lazy_segtree(vector[S] v)
        void set(int p, S x)
        S get(int p)
        S prod(int l, int r)
        S all_prod()
        void apply(int p, F f)
        void apply(int l, int r, F f)
        int max_right[G](int l)
        int min_left[G](int r)
cdef struct s_t:
    long v, s
ctypedef long f_t
cdef extern from *:
    ctypedef int op_t "myop"
    ctypedef int e_t "mye"
    ctypedef int m_t "mymapping"
    ctypedef int c_t "mycomposition"
    ctypedef int i_t "myid"
    ctypedef int g_t "myg"
    cdef s_t myop(s_t a, s_t b) nogil
    cdef s_t mye() nogil
    cdef s_t mymapping(f_t f, s_t x) nogil
    cdef f_t mycomposition(f_t f, f_t g) nogil
    cdef f_t myid() nogil
    cdef bool myg(s_t k) nogil
cdef s_t myop(s_t a, s_t b) nogil:
    cdef s_t c
    c.v = (a.v * b.s + b.v) % 998244353
    c.s = (a.s * b.s) % 998244353
    return c
cdef s_t mye() nogil:
    cdef s_t e
    e.v = 0
    e.s = 1
    return e
cdef f_t myid() nogil:
    return -1
cdef s_t mymapping(f_t f, s_t x) nogil:
    if f == myid(): return x
    cdef s_t y
    y.v = (x.s - 1) * 443664157 * f % 998244353
    y.s = x.s
    return y
cdef f_t mycomposition(f_t f, f_t g) nogil:
    if f == myid(): return g
    return f
from libc.stdio cimport getchar, printf
cdef inline long read() nogil:
    cdef long b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: return c
        c = c * 10 + b
cdef main():
    cdef long n = read(), i, l, r, d
    cdef s_t a
    a.v = 1
    a.s = 10
    cdef lazy_segtree[s_t, op_t, e_t, f_t, m_t, c_t, i_t] *seg = new lazy_segtree[s_t, op_t, e_t, f_t, m_t, c_t, i_t](vector[s_t](n, a))
    for i in range(read()):
        l, r, d = read(), read(), read()
        seg.apply(l - 1, r, d)
        printf('%ld\n', seg.all_prod().v)
main()
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/opt/ac-library
# cython: cdivision=True
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "<atcoder/lazysegtree>" namespace "atcoder" nogil:
    cdef cppclass lazy_segtree[S, OP, E, F, mapping, composition, id]:
        lazy_segtree(vector[S] v)
        void set(int p, S x)
        S get(int p)
        S prod(int l, int r)
        S all_prod()
        void apply(int p, F f)
        void apply(int l, int r, F f)
        int max_right[G](int l)
        int min_left[G](int r)
cdef long mod = 998244353
cdef struct s_t:
    long v, s
ctypedef long f_t
cdef extern from *:
    ctypedef int op_t "myop"
    ctypedef int e_t "mye"
    ctypedef int m_t "mymapping"
    ctypedef int c_t "mycomposition"
    ctypedef int i_t "myid"
    ctypedef int g_t "myg"
    cdef s_t myop(s_t a, s_t b) nogil
    cdef s_t mye() nogil
    cdef s_t mymapping(f_t f, s_t x) nogil
    cdef f_t mycomposition(f_t f, f_t g) nogil
    cdef f_t myid() nogil
    cdef bool myg(s_t k) nogil
cdef s_t myop(s_t a, s_t b) nogil:
    cdef s_t c
    c.v = (a.v * b.s + b.v) % mod
    c.s = (a.s * b.s) % mod
    return c
cdef s_t mye() nogil:
    cdef s_t e
    e.v = 0
    e.s = 1
    return e
cdef f_t myid() nogil:
    return -1
cdef s_t mymapping(f_t f, s_t x) nogil:
    if f == myid(): return x
    cdef s_t y
    y.v = (x.s - 1) * 443664157 * f % mod
    y.s = x.s
    return y
cdef f_t mycomposition(f_t f, f_t g) nogil:
    if f == myid(): return g
    return f
from libc.stdio cimport getchar, printf
cdef inline int read() nogil:
    cdef int b, c = 0
    while 1:
        b = getchar() - 48
        if b < 0: return c
        c = c * 10 + b
cdef main():
    cdef int n = read(), i, l, r, d
    cdef s_t a
    a.v = 1
    a.s = 10
    cdef lazy_segtree[s_t, op_t, e_t, f_t, m_t, c_t, i_t] *seg = new lazy_segtree[s_t, op_t, e_t, f_t, m_t, c_t, i_t](vector[s_t](n, a))
    for i in range(read()):
        l, r, d = read(), read(), read()
        seg.apply(l - 1, r, d)
        printf('%ld\n', seg.all_prod().v)
main()
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve