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:
header_code = """
#include "/opt/ac-library/atcoder/lazysegtree.hpp"
#include "/opt/ac-library/atcoder/modint.hpp"
#include <vector>
#include <algorithm>
#include <cassert>

namespace aclython {

using mint = atcoder::modint998244353;

const mint inv_nine = mint(1)/mint(9);

struct S {
    mint a;
    mint b;
    S(mint _a, mint _b) : a(_a) ,b(_b) {}
    S(int _a, int _b) : a(_a) ,b(_b) {}
    S(const S &s) : a(s.a), b(s.b) {}
    int get_a() { return (int)a.val(); }
};

struct F {
    mint a;
    F(mint _a) : a(_a) {}
    F(int _a) : a(_a) {}
};


S op(S l, S r) { return S{l.a * r.b + r.a, l.b * r.b}; }

S e() { return S{0, 1}; }

S mapping(F l, S r) {
    if (l.a==0) return r;
    return S{l.a * (r.b - 1)*inv_nine, r.b};
    }

F composition(F l, F r) {
    if (l.a==0) return r;
    return l;
    }

F id() { return F{0}; }

struct lazy_segtree{
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& vec) : seg(vec) {}
    void set(int p, S x) { seg.set(p, x); }
    S get(int p) { return seg.get(p); }
    S prod(int l, int r) { return seg.prod(l, r); }
    S all_prod() { return seg.all_prod(); }
    void apply(int p, F f) { seg.apply(p, f); }
    void apply(int l, int r, F f) { seg.apply(l, r, f); }
    private:
        atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg;
};

}
"""

code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/ac-library]
# cython: boundscheck=False
# cython: wraparound=False

from libcpp.string cimport string
from libcpp.vector cimport vector
from libc.stdio cimport getchar, printf
from libcpp cimport bool

cdef extern from "./intermediate.hpp" namespace "aclython" nogil:
    cdef cppclass S:
        S(int, int)
        S(S &)
        int get_a()
    cdef cppclass F:
        F(int)
    cdef cppclass lazy_segtree:
        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)

cdef class LazySegTree:
    cdef lazy_segtree *_thisptr
    def __cinit__(self, vector[vector[int]] v):
        cdef int n = v.size()
        cdef vector[S] *sv = new vector[S]()
        cdef S *s
        for i in range(n):
            s = new S(v.at(i).at(0), v.at(i).at(1))
            sv.push_back(s[0])
        self._thisptr = new lazy_segtree(sv[0])
    cpdef void set(self, int p, vector[int] v):
        cdef S *s = new S(v.at(0), v.at(1))
        self._thisptr.set(p, s[0])
    cpdef int get(self, int p):
        cdef S *s = new S(self._thisptr.get(p))
        return s.get_a()
    cpdef int prod(self, int l, int r):
        cdef S *s = new S(self._thisptr.prod(l, r))
        return s.get_a()
    cpdef int all_prod(self):
        cdef S *s = new S(self._thisptr.all_prod())
        return s.get_a()
    cpdef void apply(self, int p, int _f):
        cdef F *f = new F(_f)
        self._thisptr.apply(p, f[0])
    cpdef void apply_range(self, int l, int r, int _f):
        cdef F *f = new F(_f)
        self._thisptr.apply(l, r, f[0])
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld ", l[i])
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('intermediate.hpp','w').write(header_code)
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import LazySegTree, ReadInt

def main():
    N,Q = ReadInt(2)
    lst = LazySegTree([(1,10) for i in range(N)])
    for i in range(Q):
        l,r,d = ReadInt(3)
        lst.apply_range(l-1,r,d)
        print(lst.all_prod())

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.buffer.readline
mod = 998244353
INF = float("inf")


class lazySegTree(object):
	def __init__(self, N):
		self.N = N
		self.LV = (N-1).bit_length()
		self.N0 = 2**self.LV
		self.data = [0]*(2*self.N0) #桁の値を管理(lazy*size)
		self.lazy = [0]*(2*self.N0) #桁の文字を管理
		self.size = [1]*(2*self.N0) #桁の和を管理(10^n)(更新しない)
		for i in range(self.N):
			self.size[self.N0-1+i] = pow(10, self.N-i-1, mod)
		for i in range(self.N0-2, -1, -1):
			self.size[i] = (self.size[2*i+1] + self.size[2*i+2])%mod
	# 遅延セグ木の初期化
	def initialize(self):
		for i in range(self.N):
			self.data[self.N0-1+i] = pow(10, self.N-i-1, mod)
		for i in range(self.N0-2, -1, -1):
			self.data[i] = (self.data[2*i+1] + self.data[2*i+2])%mod

  # 遅延伝播を行うindexを生成
	def gindex(self, l, r):
		L = l + self.N0
		L >>= 1
		R = r + self.N0
		R >>= 1
		if l & 1:
			lc = 0
		else:
			lc = (L & -L).bit_length()
		if r & 1:
			rc = 0
		else:
			rc = (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1 
			R >>= 1

	# 遅延伝搬処理
	def propagates(self, *ids):
		for i in reversed(ids):
			v = self.lazy[i - 1]
			if not v:
				continue
			self.lazy[2*i-1] = v
			self.lazy[2*i] = v
			self.data[2*i-1] = v * self.size[2*i-1]
			self.data[2*i] = v * self.size[2*i]
			self.lazy[i-1] = 0

	def update(self, l, r, x):
		*ids, = self.gindex(l, r+1)
		self.propagates(*ids)
		L = self.N0 + l
		R = self.N0 + r + 1
		while L < R:
			if R & 1:
				R -= 1
				self.lazy[R-1] = x #桁の文字を更新
				self.data[R-1] = x * self.size[R-1] #桁の値を更新
			if L & 1:
				self.lazy[L-1] = x
				self.data[L-1] = x * self.size[L-1]
				L += 1
			L >>= 1
			R >>= 1
		for i in ids:
			self.data[i-1] = (self.data[2*i-1] + self.data[2*i])%mod

	# 区間[l, r]内のdataの和を求める
	def query(self, l, r):
		self.propagates(*self.gindex(l, r+1))
		L = self.N0 + l
		R = self.N0 + r + 1
		s = 0
		while L < R:
			if R & 1:
				R -= 1
				s = (s + self.data[R-1])%mod
			if L & 1:
				s = (s + self.data[L-1])%mod
				L += 1
			L >>= 1
			R >>= 1
		return s

N, Q = map(int, input().split())
lSeg = lazySegTree(N)
lSeg.initialize()

for i in range(Q):
	L, R, D = map(int, input().split())
	L -= 1
	R -= 1
	lSeg.update(L, R, D)
	ans = lSeg.query(0, N-1)
	ans %= mod
	print(ans)

Submission status: Accepted

Solution code:
class LazySegmentTree:

    __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]

    def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
        self.me = monoid_identity
        self.oe = operator_identity
        self.fmm = func_monoid_monoid
        self.fmo = func_monoid_operator
        self.foo = func_operator_operator

        self.n = len(monoid_data)
        self.data = monoid_data * 2
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
        self.lazy = [self.oe] * (self.n * 2)
        

    def replace(self, index, value):
        index += self.n

        # propagation
        for shift in range(index.bit_length()-1, 0, -1):
            i = index >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # update
        self.data[index] = value
        self.lazy[index] = self.oe

        # recalculation
        i = index
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe


    def effect(self, l, r, operator):
        l += self.n
        r += self.n
        
        # preparing indices
        indices = []
        l0 = (l // (l & -l))     // 2
        r0 = (r // (r & -r) - 1) // 2
        while r0 > l0:
            indices.append(r0)
            r0 //= 2
        while l0 > r0:
            indices.append(l0)
            l0 //= 2
        while l0 and l0 != r0:
            indices.append(r0)
            r0 //= 2
            if l0 == r0:
                break
            indices.append(l0)
            l0 //= 2
        while r0:
            indices.append(r0)
            r0 //= 2

        # propagation
        for i in reversed(indices):
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # effect
        while l < r:
            if l % 2:
                self.lazy[l] = self.foo(self.lazy[l], operator)
                l += 1
            if r % 2:
                r -= 1
                self.lazy[r] = self.foo(self.lazy[r], operator)
            l //= 2
            r //= 2

        # recalculation
        for i in indices:
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
            
        
    def folded(self, l, r):
        l += self.n
        r += self.n

        # preparing indices
        indices = []
        l0 = (l // (l & -l))     // 2
        r0 = (r // (r & -r) - 1) // 2
        while r0 > l0:
            indices.append(r0)
            r0 //= 2
        while l0 > r0:
            indices.append(l0)
            l0 //= 2
        while l0 and l0 != r0:
            indices.append(r0)
            r0 //= 2
            if l0 == r0:
                break
            indices.append(l0)
            l0 //= 2
        while r0:
            indices.append(r0)
            r0 //= 2
        
        # propagation
        for i in reversed(indices):
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # fold
        left_folded = self.me
        right_folded = self.me
        while l < r:
            if l % 2:
                left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
            l //= 2
            r //= 2
        return self.fmm(left_folded, right_folded)


mod = 998244353
N,Q = map(int, input().split())
monoid_data = [(1,1) for _ in range(N)]
ones = [0,1]
pow10 = [1]
for i in range(N):
    ones.append((ones[-1]*10+1) % mod)
    pow10.append(pow10[-1]*10 % mod)

def fmm(m1, m2):
    return ((m1[0]*pow10[m2[1]]+m2[0]) % mod,m1[1]+m2[1])

def fmo(m1, o1):
    if o1 != -1:
        return (ones[m1[1]]*o1 % mod,m1[1])
    else:
        return m1

def foo(o1, o2):
    if o2 == -1:
        return o1
    else:
        return o2

lst = LazySegmentTree(monoid_data, (0,0), -1, fmm, fmo, foo)
for i in range(Q):
    l,r,d = map(int,input().split())
    lst.effect(l-1,r,d)
    print(lst.folded(0,N)[0])

Submission status: Accepted

Solution code:
# class化。
import sys

input = sys.stdin.buffer.readline

mod = 998244353


max_n = 262144 + 10
pow_list = [1] * max_n
cum_pow = [0] * max_n
cum_pow[0] = 1
for i in range(1, max_n):
    pow_list[i] = pow_list[i - 1] * 10
    pow_list[i] %= mod
    cum_pow[i] += cum_pow[i - 1] + pow_list[i]
    cum_pow[i] %= mod
cum_pow = [0] + cum_pow


class LazySegmentTree:
    # funcはseg同士、calcはpoint計算
    def __init__(self, n, ele, lazy_ele, mod=mod):
        self.n = n
        self.ele = ele
        self.lazy_ele = lazy_ele
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)
        self.LAZY = [self.lazy_ele] * (2 * self.num)
        self.node = [1] * (self.num + self.n) + [0] * (self.num - self.n)
        for i in reversed(range(1, self.num)):
            self.node[i] = self.node[2 * i] + self.node[2 * i + 1]

    # SEG同士の計算
    def func(self, a, b, b_node):
        if b == 0:
            return a
        if a == 0:
            return b
        return (a * pow_list[b_node] + b) % mod

    # LAZYをSEGに作用
    def calc(self, idx):
        if self.LAZY[idx] == -1:
            return self.SEG[idx]
        node_num = self.node[idx]
        res = (self.LAZY[idx] * cum_pow[node_num]) % mod
        return res

    # LAZY同士の作用の蓄積
    def lazy_func(self, a, b):
        return b

    # 配列で初期化
    def initialize(self, A):
        for i, val in enumerate(A):
            i += self.num
            self.SEG[i] = val
        for i in reversed(range(1, self.num)):
            self.SEG[i] = self.func(
                self.SEG[2 * i], self.SEG[2 * i + 1], self.node[2 * i + 1]
            )

    # LAZYの値を1つ下に伝播して初期化
    def propagate_point(self, idx):
        if self.LAZY[idx] >= 0:
            self.SEG[idx] = self.calc(idx)
            # print(idx)
            self.LAZY[2 * idx] = self.lazy_func(self.LAZY[2 * idx], self.LAZY[idx])
            self.LAZY[2 * idx + 1] = self.lazy_func(
                self.LAZY[2 * idx + 1], self.LAZY[idx]
            )
            self.LAZY[idx] = lazy_ele

    # idx=1からidxの直上まで、伝播を行う
    def propagate_above(self, idx):
        height = idx.bit_length() - 1
        # print(idx, height)
        for h in reversed(range(1, height + 1)):
            self.propagate_point(idx >> h)

    # そのidxの直上の値を計算
    def recalc_above(self, idx):
        # print("ra", idx)
        while idx > 1:
            idx //= 2
            self.SEG[idx] = self.func(
                self.calc(2 * idx), self.calc(2 * idx + 1), self.node[2 * idx + 1],
            )

    # 1点更新
    def update_point(self, idx):
        idx += self.num
        while idx > 0:
            idx //= 2
            self.SEG[idx] = self.func(
                self.calc(self.SEG[2 * idx]),
                self.calc(self.SEG[2 * idx + 1]),
                self.node[2 * idx + 1],
            )

    # 範囲更新
    def update_range(self, left, right, mono):
        left += self.num
        right += self.num
        left_temp = left // (left & -left)
        right_temp = right // (right & -right) - 1
        self.propagate_above(left_temp)
        self.propagate_above(right_temp)
        while left < right:
            if left & 1:
                self.LAZY[left] = self.lazy_func(self.LAZY[left], mono)
                left += 1
            if right & 1:
                right -= 1
                self.LAZY[right] = self.lazy_func(self.LAZY[right], mono)
            left //= 2
            right //= 2
        self.recalc_above(left_temp)
        self.recalc_above(right_temp)

    # 範囲取得
    def get_range(self, left, right):
        left += self.num
        right += self.num
        self.propagate_above(left // (left & -left))
        self.propagate_above(right // (right & -right) - 1)
        res_left = self.ele
        res_left_node = 0
        res_right = self.ele
        res_right_node = 0
        while left < right:
            if left & 1:
                res_left = self.func(res_left, self.calc(left), res_left_node)
                res_left_node += self.node[left]
                left += 1
            if right & 1:
                right -= 1
                res_right = self.func(self.calc(right), res_right, res_right_node)
                res_right_node += self.node[right]
            left //= 2
            right //= 2
        # print(res_left, res_right, left, right)
        return self.func(res_right, res_left, res_left_node) % mod

    # def get_point(self, idx):
    #     a,b=self.LAZY[idx]>>32, self.LAZY[idx]&(1<<32-1)
    #     return a*self.SEG[idx]+b*self.node[idx]


ele = 0
lazy_ele = -1
n, q = map(int, input().split())
A = [1 for _ in range(n)]

# for i in range(122, 456):
#     A[i] = 7
LST = LazySegmentTree(n, ele, lazy_ele)
LST.initialize(A)

# print(LST.get_range(0, n) % mod)
for _ in range(q):
    l, r, d = map(int, input().split())
    l -= 1

    LST.update_range(l, r, d)

    print(LST.get_range(0, n) % mod)

Submission status: Accepted

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

# LazySegmentTree
class LazySegmentTree:
  # f(X, X) -> X
  # g(X, M) -> X
  # h(M, M) -> M
  __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)

# X(要素) -> sum*200001+(文字列の長さ)
# (tuple,listで持つと2倍くらい遅くなるのでintにぶち込みます。多倍長最高！)
# M(作用) -> 置き換える数字

mod=998244353
n,q=map(int,input().split())
num=2**((n-1).bit_length())
p=[]
for i in range(num):
  if i<n:
    p.append(200002)
  else:
    p.append(0)
digit=[1]
for _ in range(num):
  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(num,p,0,None,f,g,h)
for _ in range(q):
  l,r,d=map(int,input().split())
  seg.update(l-1,r,d)
  ans,_=divmod(seg.query(0,n),200001)
  print(ans)

Submission status: Accepted

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

# LazySegmentTree
class LazySegmentTree:
  # f(X, X) -> X
  # g(X, M) -> X
  # h(M, M) -> M
  __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)

# X(要素) -> (文字列の長さ, sum)
# M(作用) -> 置き換える数字

mod=998244353
n,q=map(int,input().split())
num=2**((n-1).bit_length())
p=[]
for i in range(num):
  if i<n:
    p.append(200002)
  else:
    p.append(0)
digit=[1]
for _ in range(num):
  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(num,p,0,None,f,g,h)
for _ in range(q):
  l,r,d=map(int,input().split())
  seg.update(l-1,r,d)
  ans,_=divmod(seg.query(0,n),200001)
  print(ans)

Submission status: Accepted

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

# LazySegmentTree
class LazySegmentTree:
  # f(X, X) -> X
  # g(X, M) -> X
  # h(M, M) -> M
  __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)

# X(要素) -> (文字列の長さ, sum)
# M(作用) -> 置き換える数字

mod=998244353
n,q=map(int,input().split())
num=2**((n-1).bit_length())
p=[]
for i in range(num):
  if i<n:
    p.append((1,1))
  else:
    p.append((0,0))
digit=[1]
for _ in range(num):
  digit.append(digit[-1]*10%mod)
inv9=pow(9,mod-2,mod)
def f(a,b):
  # (4, 1111), (4, 2222) -> (8, 1111*1000 + 2222)
  alen,asum=a
  blen,bsum=b
  return (alen+blen,(digit[blen]*asum+bsum)%mod)
def g(x,y):
  # (4, 1222), 5 -> (4, 5555)
  # (digit[xlen]-1)*inv9 = (10^xlen - 1)/9 = 11111....
  if y is None:
    return x
  xlen,_=x
  return (xlen,(digit[xlen]-1)*inv9*y%mod)
def h(x,y):
  if y is None:
    return x
  return y

seg=LazySegmentTree(num,p,(0,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)[1])

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np


def solve(N, Q, LRD):
    mod = 998244353
    p = 1
    n = 0
    p10 = np.empty(202020, dtype=np.int64)
    n11 = np.empty(202020, dtype=np.int64)
    for i in range(202020):
        p10[i] = p
        n11[i] = n
        p = p*10%mod
        n = (n*10+1)%mod

    identity = 0
    sqrtN = 256
    n_buckets = N//sqrtN+1
    Data_val = np.ones(n_buckets*sqrtN, dtype=np.int64)
    Data_val[N:] = 0
    Bucket_val = np.full(n_buckets, n11[sqrtN], dtype=np.int64)
    Lazy = np.full(n_buckets, identity, dtype=np.int64)
    M = N % sqrtN
    Bucket_val[n_buckets-1] = n11[M]

    def eval_data(k):
        if Lazy[k] != identity:
            l, r = k*sqrtN, (k+1)*sqrtN
            for i in range(l, r):
                Data_val[i] = Lazy[k]
            Lazy[k] = identity

    def apply(s, t, f):
        for k in range(s//sqrtN, (t-1)//sqrtN+1):
            l, r = k*sqrtN, (k+1)*sqrtN
            if s <= l and r <= t:
                Bucket_val[k] = f * n11[sqrtN] % mod
                Lazy[k] = f
            else:
                eval_data(k)
                for i in range(max(l, s), min(r, t)):
                    Data_val[i] = f
                Bucket_val[k] = 0
                for i in range(l, min(r, N)):
                    Bucket_val[k] = (Bucket_val[k] * 10 + Data_val[i]) % mod

    def get(i):
        k = i//sqrtN
        eval_data(k)
        return Data_val[i]

    def all_prod():
        res = 0
        for k in range(n_buckets-1):
            res = (res * p10[sqrtN] + Bucket_val[k]) % mod
        res = (res * p10[M] + Bucket_val[n_buckets-1]) % mod
        return res

    Ans = np.zeros(Q, dtype=np.int64)
    for i in range(Q):
        l, r, d = LRD[i]
        apply(l-1, r, d)
        ans = all_prod()
        Ans[i] = ans

    return Ans


numba_compile([
    [solve, "i8[:](i8,i8,i8[:,:])"]
])


def main():
    N, Q = map(int, sys.stdin.buffer.readline().split())
    LRD = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(Q, 3)
    Ans = solve(N, Q, LRD)
    print("\n".join(map(str, Ans.tolist())))


main()