Problem:

RSQ and RUQ

  Write a program which manipulates a sequence $A$ = {$a_0, a_1, ..., a_{n-1}$} with the following operations:

  

    
 $update(s, t, x)$: change $a_s, a_{s+1}, ..., a_t$ to $x$.

    
 $getSum(s, t)$: print the sum of $a_s, a_{s+1}, ..., a_t$.

  

  Note that the initial values of $a_i ( i = 0, 1, ..., n-1 )$ are 0.

Input

$n$ $q$
$query_1$
$query_2$
:
$query_q$

In the first line, $n$ (the number of elements in $A$) and $q$ (the number of queries) are given. Then, $i$-th query $query_i$ is given in the following format:

0 $s$ $t$ $x$

or

1 $s$ $t$

  The first digit represents the type of the query. '0' denotes $update(s, t, x)$
 and '1' denotes $find(s, t)$.

Output

  For each $getSum$ query, print the sum in a line.

Constraints

  
$1 ≤ n ≤ 100000$

  
$1 ≤ q ≤ 100000$

  
$0 ≤ s ≤ t < n$

  
$-1000 ≤ x ≤ 1000$

Sample Input 1

6 7
0 1 3 1
0 2 4 -2
1 0 5
1 0 1
0 3 5 3
1 3 4
1 0 5

Sample Output 1

-5
1
6
8



Sample input:
6 7
0 1 3 1
0 2 4 -2
1 0 5
1 0 1
0 3 5 3
1 3 4
1 0 5


Sample output:
-5
1
6
8

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DSL_2_I: RSQ and RUQ
# Range Sum Query and Range Update Query

import sys


class SegmentTree:

    def __init__(self, n):
        size = 2 ** (n.bit_length())
        self.size = 2*size - 1
        self.data = [0] * self.size
        self.lazy = [None] * self.size

    def update(self, lo, hi, v):
        def _update(r, i, j, lz):
            left, right = r*2 + 1, r*2 + 2
            if lz is None:
                lz = lazy[r]
            lazy[r] = None

            if lo <= i and j <= hi:
                data[r] = v * (j - i + 1)
                if i < j:
                    lazy[left] = v
                    lazy[right] = v
            else:
                mid = (i + j) // 2
                if mid >= lo:
                    lv = _update(left, i, mid, lz)
                else:
                    if lz is not None:
                        lazy[left] = lz
                        lv = lz * (mid - i + 1)
                    elif lazy[left] is not None:
                        lv = lazy[left] * (mid - i + 1)
                    else:
                        lv = data[left]

                if mid < hi:
                    rv = _update(right, mid+1, j, lz)
                else:
                    if lz is not None:
                        lazy[right] = lz
                        rv = lz * (j - mid)
                    elif lazy[right] is not None:
                        rv = lazy[right] * (j - mid)
                    else:
                        rv = data[right]

                data[r] = lv + rv

            return data[r]

        data = self.data
        lazy = self.lazy
        _update(0, 0, self.size//2, None)

    def sum(self, lo, hi):
        def _sum(r, i, j, lz):
            if lz is None:
                lz = lazy[r]
            lazy[r] = None
            if lz is not None:
                data[r] = lz * (j - i + 1)

            left, right = r*2 + 1, r*2 + 2
            if lo <= i and j <= hi:
                if lz is not None and i < j:
                    lazy[left] = lz
                    lazy[right] = lz
                return data[r]
            else:
                mid = (i + j) // 2
                lv, rv = 0, 0

                if mid >= lo:
                    lv = _sum(left, i, mid, lz)
                else:
                    if lz is not None:
                        lazy[left] = lz
                if mid < hi:
                    rv = _sum(right, mid+1, j, lz)
                else:
                    if lz is not None:
                        lazy[right] = lz
                return lv + rv

        data = self.data
        lazy = self.lazy
        return _sum(0, 0, self.size//2, None)


def run():
    n, q = [int(i) for i in input().split()]
    tree = SegmentTree(n)

    for line in sys.stdin:
        com, *args = line.split()
        if com == '0':
            s, t, x = [int(i) for i in args]
            tree.update(s, t, x)
        elif com == '1':
            s, t = [int(i) for i in args]
            print(tree.sum(s, t))


if __name__ == '__main__':
    run()

Submission status: Accepted

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

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

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

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




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

from operator import add

if __name__ == '__main__':
    n,q = map(int,readline().split())
    temp = map(int,read().split())

    seg = LazySegmentTree.all_identity(
        add,
        0,
        lambda x,y: x if y is None else y,
        None,
        lambda x,m,l: x if m is None else m*l,
        n)

    try:
        while True:
            mode = next(temp)
            if mode:
                l,r = next(temp), next(temp)+1
                print(seg.get_interval(l,r))
            else:
                l,r,x = next(temp), next(temp)+1, next(temp)
                seg.update_interval(l,r,x)
    except StopIteration:
        pass

Submission status: Accepted

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


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


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


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


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


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


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


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


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

        left //= 2
        right //= 2


def range_reduce(table, left, right, binop, unity):
    ret_left = unity
    ret_right = unity
    left += NONLEAF_SIZE
    right += NONLEAF_SIZE
    while left < right:
        if left & 1:
            ret_left = binop(ret_left, table[left])
            left += 1
        if right & 1:
            right -= 1
            ret_right = binop(table[right], ret_right)

        left //= 2
        right //= 2
    return binop(ret_left, ret_right)


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

    # print("action", file=sys.stderr)
    # debugprint(action_table)
    # print("value", file=sys.stderr)
    # debugprint(value_table)
    # print(file=sys.stderr)

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


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

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


def debugprint(xs, minsize=0, maxsize=None):
    global DEPTH
    strs = [str(x) for x in xs]
    if maxsize != None:
        for i in range(NONLEAF_SIZE, SEGTREE_SIZE):
            strs[i] = strs[i][:maxsize]
    s = max(len(s) for s in strs[NONLEAF_SIZE:])
    if s > minsize:
        minsize = s

    result = ["|"] * DEPTH
    level = 0
    next_level = 2
    for i in range(1, SEGTREE_SIZE):
        if i == next_level:
            level += 1
            next_level *= 2
        width = ((minsize + 1) << (DEPTH - 1 - level)) - 1
        result[level] += strs[i].center(width) + "|"
    print(*result, sep="\n", file=sys.stderr)


def main():
    # parse input
    from operator import add
    N, Q = map(int, input().split())
    set_width(N)

    value_unity = 0
    value_table = [0] * SEGTREE_SIZE
    value_binop = add
    action_unity = None
    action_table = [action_unity] * SEGTREE_SIZE

    def force(action, value, size):
        if action == action_unity:
            return value
        return action * size

    def composite(new_action, old_action):
        if new_action != action_unity:
            return new_action
        return old_action

    for _time in range(Q):
        q, *args = map(int, input().split())
        # debug(": q,", q, args)
        if q == 0:
            # update
            s, t, value = args
            lazy_range_update(
                action_table, value_table, s, t + 1,
                value, composite, force, action_unity, value_binop
            )
        else:
            # getSum
            s, t = args
            print(lazy_range_reduce(
                action_table, value_table, s, t + 1,
                composite, force, action_unity, value_binop, value_unity))


# tests
T1 = """
6 7
0 1 3 1
0 2 4 -2
1 0 5
1 0 1
0 3 5 3
1 3 4
1 0 5
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
-5
1
6
8
"""


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


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


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

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

main()

Submission status: Accepted

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

class LazyPropSegmentTree:
    def __init__(self, lst, op, apply, comp, e, identity):
        self.n = len(lst)
        self.depth = (self.n - 1).bit_length()
        self.N = 1 << self.depth
        self.op = op # binary operation of elements
        self.apply = apply # function to apply to an element
        self.comp = comp # composition of functions
        self.e = e # identity element w.r.t. op
        self.identity = identity # identity element w.r.t. comp
        self.v, self.length = self._build(lst) # self.v is set to be 1-indexed for simplicity
        self.lazy = [self.identity] * (2 * self.N)
    
    def __getitem__(self, i):
        return self.fold(i, i+1)
    
    def _build(self, lst):
        # construction of a tree
        # total 2 * self.N elements (tree[0] is not used)
        e, N, op = self.e, self.N, self.op
        tree = [e] * N + lst + [e] * (N - self.n)
        length = [1] * (2 * N)
        for i in range(N - 1, 0, -1):
            lc, rc = i << 1, (i << 1)|1
            tree[i] = op(tree[lc], tree[rc])
            length[i] = length[lc] + length[rc]
        return tree, length
    
    def _indices(self, l, r):
        left = l + self.N; right = r + self.N
        left //= (left & (-left)); right //= (right & (-right))
        left >>= 1; right >>= 1
        while left != right:
            if left > right: yield left; left >>= 1
            else: yield right; right >>= 1
        while left > 0: yield left; left >>= 1
    
    # propagate self.lazy and self.v in a top-down manner
    def _propagate_topdown(self, *indices):
        identity, v, lazy, length, apply, comp = self.identity, self.v, self.lazy, self.length, self.apply, self.comp
        for k in reversed(indices):
            x = lazy[k]
            if x == identity: continue
            lc, rc = k << 1, (k << 1) | 1
            v[lc] = apply(v[lc], x, length[lc])
            lazy[lc] = comp(lazy[lc], x)
            v[rc] = apply(v[rc], x, length[rc])
            lazy[rc] = comp(lazy[rc], x)
            lazy[k] = identity # propagated

    # propagate self.v in a bottom-up manner
    def _propagate_bottomup(self, indices):
        v, op = self.v, self.op
        for k in indices: v[k] = op(v[k << 1], v[(k << 1)|1])

    # update for the query interval [l, r) with function x
    def update(self, l, r, x):
        *indices, = self._indices(l, r)
        self._propagate_topdown(*indices)

        N, v, lazy, length, apply, comp = self.N, self.v, self.lazy, self.length, self.apply, self.comp
        
        # update self.v and self.lazy for the query interval [l, r)
        left = l + N; right = r + N
        if left & 1: v[left] = apply(v[left], x, length[left]); left += 1
        if right & 1: right -= 1; v[right] = apply(v[right], x, length[right])
        left >>= 1; right >>= 1
        while left < right:
            if left & 1:
                v[left] = apply(v[left], x, length[left])
                lazy[left] = comp(lazy[left], x)
                left += 1
            if right & 1:
                right -= 1
                v[right] = apply(v[right], x, length[right])
                lazy[right] = comp(lazy[right], x)
            left >>= 1; right >>= 1
        self._propagate_bottomup(indices)
    
    # returns answer for the query interval [l, r)
    def fold(self, l, r):
        self._propagate_topdown(*self._indices(l, r))
        
        e, N, v, op = self.e, self.N, self.v, self.op
        
        # calculate the answer for the query interval [l, r)
        left = l + N; right = r + N
        L = R = e
        while left < right:
            if left & 1: # self.v[left] is the right child
                L = op(L, v[left])
                left += 1
            if right & 1: # self.v[right-1] is the left child
                right -= 1
                R = op(v[right], R)
            left >>= 1; right >>= 1
        return op(L, R)
    
N, Q = map(int, input().split())
op = lambda x, y: x + y
apply = lambda x, f, l: f * l
comp = lambda f, g: g
e = 0
identity = None
A = [0] * N
lpsg = LazyPropSegmentTree(A, op, apply, comp, e, identity)
ans = []
for _ in range(Q):
    t, *arg, = map(int, input().split())
    if t == 0:
        s, t, x = arg
        lpsg.update(s, t+1, x)
    else:
        s, t = arg
        ans.append(lpsg.fold(s, t+1))
print('\n'.join(map(str, ans)))

Submission status: Accepted

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

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

seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
seg_height=1+N.bit_length() # Segment treeの高さ
SEG=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY=[None]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def indexes(L,R): # 遅延伝搬すべきノードのリストを返す. （つまり, updateやgetvaluesで見るノードより上にあるノードたち）
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST

def updates(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬
        if LAZY[ind]!=None:
            update_lazy = LAZY[ind] *(1<<(seg_height - 1 - (ind.bit_length())))
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=LAZY[ind]
            SEG[ind<<1]=SEG[1+(ind<<1)]=update_lazy
            LAZY[ind]=None

    while L!=R:
        if L > R:
            SEG[L]=x * (1<<(seg_height - (L.bit_length())))
            LAZY[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[R]=x * (1<<(seg_height - (R.bit_length())))
            LAZY[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=SEG[ind<<1]+SEG[1+(ind<<1)]

def getvalues(l,r): # 区間[l,r)に関するminを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]: # 遅延伝搬
        if LAZY[ind]!=None:
            update_lazy = LAZY[ind] *(1<<(seg_height - 1 - (ind.bit_length())))
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=LAZY[ind]
            SEG[ind<<1]=SEG[1+(ind<<1)]=update_lazy
            LAZY[ind]=None
            
    ANS=0

    while L!=R:
        if L > R:
            ANS+=SEG[L]
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS+=SEG[R]
            R//=(R & (-R))

    return ANS

ANS=[]
for _ in range(Q):
    query=list(map(int,input().split()))

    if query[0]==0:
        updates(query[1],query[2]+1,query[3])

    else:
        ANS.append(getvalues(query[1],query[2]+1))
    
print("\n".join([str(ans) for ans in ANS]))

Submission status: Accepted

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

import sys
from operator import add

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 2 ** 31 - 1
MOD = 10 ** 9 + 7

class SegTreeLazy:
    """ 遅延評価セグメント木(区間更新、区間合計取得) """

    def __init__(self, N, func, intv):
        self.intv = intv
        self.func = func
        self.LV = (N-1).bit_length()
        self.N0 = 2**self.LV
        self.data = [intv]*(2*self.N0)
        self.lazy = [None]*(2*self.N0)

    # 伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    def gindex(self, l, r):
        L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
        lc = 0 if l & 1 else (L & -L).bit_length()
        rc = 0 if r & 1 else (R & -R).bit_length()
        v = 2
        for i in range(self.LV):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>= 1; v <<= 1

    # 遅延評価の伝搬処理
    def propagates(self, *ids):
        # 1-indexedで単調増加のインデックスリスト
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.data[2*i-1] = self.lazy[2*i] = self.data[2*i] = v >> 1
            self.lazy[i-1] = None

    def update(self, l, r, x):
        """ 区間[l,r)の値をxに更新 """

        *ids, = self.gindex(l, r)
        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*ids)
        # 2. 区間[l,r)のdata, lazyの値を更新
        L = self.N0 + l; R = self.N0 + r
        v = x
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = v
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = v
                L += 1
            L >>= 1; R >>= 1; v <<= 1
        # 3. 伝搬させた区間について、ボトムアップにdataの値を伝搬する
        for i in ids:
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i])

    def query(self, l, r):
        """ 区間[l,r)の和を取得 """

        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        # 2. 区間[l, r)の和を求める
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.func(s, self.data[R-1])
            if L & 1:
                s = self.func(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

N, Q = MAP()
stl = SegTreeLazy(N+1, add, 0)

ans = []
for i in range(Q):
    cmd, *arg = MAP()
    if cmd == 0:
        s, t, x = arg
        stl.update(s, t+1, x)
    else:
        s, t = arg
        ans.append(str(stl.query(s, t+1)))
print('\n'.join(ans))

Submission status: Accepted

Solution code:
from typing import Optional


class SegmentTree(object):
    def __init__(self, n: int) -> None:
        size = 2 ** (n.bit_length())
        self.size = 2 * size - 1
        self.data = [0] * self.size
        self.lazy = [None] * self.size

    def update(self, lo: int, hi: int, v: int) -> None:
        def _update(r: int, i: int, j: int, lz: Optional[int]) -> int:
            left, right = r * 2 + 1, r * 2 + 2
            if (lz is None):
                lz = lazy[r]
            lazy[r] = None

            if (lo <= i and j <= hi):
                data[r] = v * (j - i + 1)
                if (i < j):
                    lazy[left] = v
                    lazy[right] = v
            else:
                mid = (i + j) // 2
                if (mid >= lo):
                    lv = _update(left, i, mid, lz)
                else:
                    if (lz is not None):
                        lazy[left] = lz
                        lv = lz * (mid - i + 1)
                    elif (lazy[left] is not None):
                        lv = lazy[left] * (mid - i + 1)
                    else:
                        lv = data[left]

                if (mid < hi):
                    rv = _update(right, mid + 1, j, lz)
                else:
                    if (lz is not None):
                        lazy[right] = lz
                        rv = lz * (j - mid)
                    elif (lazy[right] is not None):
                        rv = lazy[right] * (j - mid)
                    else:
                        rv = data[right]

                data[r] = lv + rv

            return data[r]

        data = self.data
        lazy = self.lazy
        _update(0, 0, self.size // 2, None)

    def sum(self, lo: int, hi: int) -> int:
        def _sum(r: int, i: int, j: int, lz: Optional[int]) -> int:
            if (lz is None):
                lz = lazy[r]
            lazy[r] = None
            if (lz is not None):
                data[r] = lz * (j - i + 1)

            left, right = r * 2 + 1, r * 2 + 2
            if (lo <= i and j <= hi):
                if (lz is not None and i < j):
                    lazy[left] = lz
                    lazy[right] = lz
                return data[r]
            else:
                mid = (i + j) // 2
                lv, rv = 0, 0

                if (mid >= lo):
                    lv = _sum(left, i, mid, lz)
                else:
                    if (lz is not None):
                        lazy[left] = lz
                if (mid < hi):
                    rv = _sum(right, mid + 1, j, lz)
                else:
                    if (lz is not None):
                        lazy[right] = lz
                return lv + rv

        data = self.data
        lazy = self.lazy
        return _sum(0, 0, self.size // 2, None)


if __name__ == "__main__":
    n, q = map(lambda x: int(x), input().split())
    segtree = SegmentTree(n)

    for _ in range(q):
        com, *v = map(lambda x: int(x), input().split())
        if (0 == com):
            segtree.update(v[0], v[1], v[2])
        else:
            print(segtree.sum(v[0], v[1]))

Submission status: Accepted

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

n, q = map(int, input().split())

Len = (n-1).bit_length()
size = 2**Len
tree = [0]*(2*size)
lazy = [None]*(2*size)
h = [None]
for i in range(Len+1):
    v = 2**(Len-i)
    h += [v]*(2**i)

def gindex(l,r):
    L = (l+size)>>1;R=(r+size)>>1
    lc = 0 if l & 1 else (L&-L).bit_length()
    rc = 0 if r & 1 else (R&-R).bit_length()
    for i in range(Len):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1
        
def propagates(ids):
    for i in reversed(ids):
        v = lazy[i]
        if v is None:
            continue
        lazy[2*i] = tree[2*i] = lazy[2*i+1] = tree[2*i+1] = v//2
        lazy[i]=None

def update(l,r,x):
    *ids, = gindex(l, r)
    propagates(ids)
    L = size+l
    R = size+r
    while L<R:
        if R&1:
            R -= 1
            lazy[R] = tree[R] = x*h[R]
        if L&1:
            lazy[L] = tree[L] = x*h[L]
            L+=1
        L>>=1;R>>=1
    for i in ids:
        if 2*i+1<size*2:
            tree[i]= tree[i*2]+tree[i*2+1]
        
def query(l, r):
    *ids, = gindex(l, r)
    propagates(ids)
    L = size + l
    R = size + r
    s = 0
    while L<R:
        if R&1:
            R-=1
            s +=tree[R]
        if L&1:
            s +=tree[L]
            L+=1
        L>>=1;R>>=1
    return s

ans = []
for i in range(q):
    a, *b = map(int, input().split())
    if a:
        ans.append(query(b[0],b[1]+1))
    else:
        update(b[0],b[1]+1,b[2])
print('\n'.join(map(str,ans)))