Problem:

RMQ and RUQ

Write a program which manipulates a sequence A = {a0, a1, . . .  , an&minus;1} with the following operations:

  
update(s, t, x): change as, as+1, ..., at to x.

  
find(s, t): report the minimum element in as, as+1, ..., at.

Note that the initial values of ai (i = 0, 1, . . .  , n&minus;1) are 231-1.

Input

n q
query1
query2
:
queryq

  In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, ith query queryi 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 find operation, print the minimum value.

Constraints

1 ≤ n ≤ 100000

1 ≤ q ≤ 100000

  0 ≤ s ≤ t < n

  0 ≤ x < 231&minus;1

Sample Input 1

3 5
0 0 1 1
0 1 2 3
0 2 2 2
1 0 2
1 1 2

Sample Output 1

1
2

Sample Input 2

1 3
1 0 0
0 0 0 5
1 0 0

Sample Output 2

2147483647
5



Sample input:
3 5
0 0 1 1
0 1 2 3
0 2 2 2
1 0 2
1 1 2


Sample output:
1
2

Submission status: Accepted

Solution code:
import math
from collections import deque


class SegmentTree:
    __slots__ = ["rank", "elem_size", "tree_size", "tree", "lazy", "default_value"]

    def __init__(self, a: list, default: int):
        self.default_value = default
        real_size = len(a)
        self.rank = math.ceil(math.log2(real_size))
        self.elem_size = 1 << self.rank
        self.tree_size = 2 * self.elem_size
        self.tree = [default]*self.elem_size + a + [default]*(self.elem_size - real_size)
        self.lazy = [None]*self.tree_size
        self.init_tree()

    def init_tree(self):
        tree = self.tree
        for i in range(self.elem_size-1, 0, -1):
            left, right = tree[i << 1], tree[(i << 1)+1]
            # ===== change me =====
            tree[i] = left if left < right else right

    def propagate(self, l: int, r: int, value: int = None):
        '''[x, y)'''
        tree, lazy, elem_size, rank = self.tree, self.lazy, self.elem_size, self.rank-1
        l, r, targets, p_l, p_r, l_rank, r_rank = l+elem_size, r+elem_size, deque(), 0, 0, 0, 0
        t_ap = targets.append

        while l < r:
            if l & 1:
                t_ap(l)
                p_l = p_l or l >> 1
                l_rank = l_rank or rank
                l += 1
            if r & 1:
                r -= 1
                t_ap(r)
                p_r = p_r or r >> 1
                r_rank = r_rank or rank
            l >>= 1
            r >>= 1
            rank -= 1

        deepest = (p_l, p_r)

        paths = [[p_l >> n for n in range(l_rank-1, -1, -1)], [p_r >> n for n in range(r_rank-1, -1, -1)]]

        for a in paths:
            for i in a:
                if lazy[i] is None:
                    continue
                # ===== change me =====
                tree[i] = lazy[i]
                if i < elem_size:
                    lazy[i << 1] = lazy[i]
                    lazy[(i << 1)+1] = lazy[i]
                lazy[i] = None

        result = self.default_value
        if value is None:
            for i in targets:
                if lazy[i] is not None:
                    tree[i] = lazy[i]
                    if i < elem_size:
                        lazy[i << 1] = lazy[i]
                        lazy[(i << 1)+1] = lazy[i]
                    lazy[i] = None
                # ===== change me =====
                if result > tree[i]:
                    result = tree[i]

        else:
            for i in targets:
                # ===== change me =====
                if i < elem_size:
                    lazy[i << 1] = value
                    lazy[(i << 1)+1] = value
                tree[i] = value
                lazy[i] = None

        self.update_tree(deepest)

        return result

    def update_lazy(self, l, r, value):
        self.propagate(l, r, value)

    def get_value(self, l: int, r: int):
        tree = self.tree
        targets = self.propagate(l, r)

        # ===== change me =====
        return min(tree[n] for n in targets)

    def update_tree(self, indexes: tuple):
        ''' ????????????lazy?????¨????????¬????????§???????????¨???????????¨???????????? '''

        tree, lazy = self.tree, self.lazy

        for k in indexes:
            while k > 0:
                left, right = k << 1, (k << 1)+1
                # ===== change me =====
                l_value = tree[left] if lazy[left] is None else lazy[left]
                r_value = tree[right] if lazy[right] is None else lazy[right]
                tree[k] = l_value if l_value < r_value else r_value

                k >>= 1


n, q = map(int, input().split())
rmq = SegmentTree([2**31-1]*n, 2**31-1)
ans = []
append = ans.append
for _ in [0]*q:
    l = list(map(int, input().split()))
    if l[0] == 0:
        rmq.propagate(l[1], l[2]+1, l[3])
    else:
        a = rmq.propagate(l[1], l[2]+1)
        append(a)

print("\n".join([str(n) for n in ans]))

Submission status: Accepted

Solution code:
import math
from collections import deque


class SegmentTree:
    __slots__ = ["rank", "elem_size", "tree_size", "tree", "lazy", "default_value"]

    def __init__(self, a: list, default: int):
        self.default_value = default
        real_size = len(a)
        self.rank = math.ceil(math.log2(real_size))
        self.elem_size = 1 << self.rank
        self.tree_size = 2 * self.elem_size
        self.tree = [default]*self.elem_size + a + [default]*(self.elem_size - real_size)
        self.lazy = [None]*self.tree_size
        # self.init_tree()

    def init_tree(self):
        tree = self.tree
        for i in range(self.elem_size-1, 0, -1):
            left, right = tree[i << 1], tree[(i << 1)+1]
            # ===== change me =====
            tree[i] = left if left < right else right

    def process_query(self, l: int, r: int, value: int = None):
        '''[x, y)'''
        tree, lazy, elem_size, rank = self.tree, self.lazy, self.elem_size, self.rank-1
        l, r, targets, p_l, p_r, l_rank, r_rank = l+elem_size, r+elem_size, deque(), 0, 0, 0, 0
        t_ap = targets.append

        while l < r:
            if l & 1:
                t_ap(l)
                p_l = p_l or l >> 1
                l_rank = l_rank or rank
                l += 1
            if r & 1:
                r -= 1
                t_ap(r)
                p_r = p_r or r >> 1
                r_rank = r_rank or rank
            l >>= 1
            r >>= 1
            rank -= 1

        deepest = (p_l, p_r)

        paths = [[p_l >> n for n in range(l_rank-1, -1, -1)], [p_r >> n for n in range(r_rank-1, -1, -1)]]

        for a in paths:
            for i in a:
                if lazy[i] is None:
                    continue
                # ===== change me =====
                tree[i] = lazy[i]
                if i < elem_size:
                    lazy[i << 1] = lazy[i]
                    lazy[(i << 1)+1] = lazy[i]
                lazy[i] = None

        result = self.default_value
        for i in targets:
            v = value if value is not None else lazy[i]
            # ===== change me =====
            if v is not None:
                if i < elem_size:
                    lazy[i << 1] = v
                    lazy[(i << 1)+1] = v
                tree[i] = v
                lazy[i] = None
            if result > tree[i]:
                result = tree[i]

        self.update_tree(deepest)

        return result

    def update_tree(self, indexes: tuple):
        ''' ????????????lazy?????¨????????¬????????§???????????¨???????????¨???????????? '''

        tree, lazy = self.tree, self.lazy

        for k in indexes:
            while k > 0:
                left, right = k << 1, (k << 1)+1
                # ===== change me =====
                l_value = tree[left] if lazy[left] is None else lazy[left]
                r_value = tree[right] if lazy[right] is None else lazy[right]
                tree[k] = l_value if l_value < r_value else r_value

                k >>= 1


n, q = map(int, input().split())
rmq = SegmentTree([2**31-1]*n, 2**31-1)
ans = []
append = ans.append
for _ in [0]*q:
    l = list(map(int, input().split()))
    if l[0] == 0:
        rmq.process_query(l[1], l[2]+1, l[3])
    else:
        a = rmq.process_query(l[1], l[2]+1)
        append(a)

print("\n".join([str(n) for n in ans]))

Submission status: Accepted

Solution code:
import math


class SegmentTree:
    __slots__ = ["rank", "elem_size", "tree_size", "tree", "lazy", "default_value"]

    def __init__(self, a: list, default: int):
        self.default_value = default
        real_size = len(a)
        self.rank = math.ceil(math.log2(real_size))
        self.elem_size = 1 << self.rank
        self.tree_size = 2 * self.elem_size
        self.tree = [default]*self.elem_size + a + [default]*(self.elem_size - real_size)
        self.lazy = [None]*self.tree_size
        # self.init_tree()

    def init_tree(self):
        tree = self.tree
        for i in range(self.elem_size-1, 0, -1):
            left, right = tree[i << 1], tree[(i << 1)+1]
            # ===== change me =====
            tree[i] = left if left < right else right

    def process_query(self, l: int, r: int, value: int = None):
        '''[x, y)'''
        tree, lazy, elem_size, rank = self.tree, self.lazy, self.elem_size, self.rank-1
        l, r, targets, p_l, p_r, l_rank, r_rank = l+elem_size, r+elem_size, [], 0, 0, 0, 0
        t_ap = targets.append

        while l < r:
            if l & 1:
                t_ap(l)
                p_l = p_l or l >> 1
                l_rank = l_rank or rank
                l += 1
            if r & 1:
                r -= 1
                t_ap(r)
                p_r = p_r or r >> 1
                r_rank = r_rank or rank
            l >>= 1
            r >>= 1
            rank -= 1

        deepest = (p_l, p_r)

        paths = [[p_l >> n for n in range(l_rank-1, -1, -1)], [p_r >> n for n in range(r_rank-1, -1, -1)]]

        for a in paths:
            for i in a:
                if lazy[i] is None:
                    continue
                # ===== change me =====
                tree[i] = lazy[i]
                if i < elem_size:
                    lazy[i << 1] = lazy[i]
                    lazy[(i << 1)+1] = lazy[i]
                lazy[i] = None

        result = self.default_value
        for i in targets:
            v = value if value is not None else lazy[i]
            # ===== change me =====
            if v is not None:
                if i < elem_size:
                    lazy[i << 1] = v
                    lazy[(i << 1)+1] = v
                tree[i] = v
                lazy[i] = None
            if result > tree[i]:
                result = tree[i]

        self.update_tree(deepest)

        return result

    def update_tree(self, indexes: tuple):
        ''' ????????????lazy?????¨????????¬????????§???????????¨???????????¨???????????? '''

        tree, lazy = self.tree, self.lazy

        for k in indexes:
            while k > 0:
                left, right = k << 1, (k << 1)+1
                # ===== change me =====
                l_value = tree[left] if lazy[left] is None else lazy[left]
                r_value = tree[right] if lazy[right] is None else lazy[right]
                tree[k] = l_value if l_value < r_value else r_value

                k >>= 1


n, q = map(int, input().split())
rmq = SegmentTree([2**31-1]*n, 2**31-1)
ans = []
append = ans.append
for _ in [0]*q:
    l = list(map(int, input().split()))
    if l[0] == 0:
        rmq.process_query(l[1], l[2]+1, l[3])
    else:
        a = rmq.process_query(l[1], l[2]+1)
        append(a)

print("\n".join([str(n) for n in ans]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

# from collections import defaultdict
# from heapq import heappush, heappop
# import numpy as np
import sys

try:
    profile
except:
    def profile(f): return f


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)


@profile
def force_point(value_table, action_table, pos, action_force, action_composite, action_unity):
    action = action_table[pos]
    if action != action_unity:
        value_table[pos] = action

        if pos < NONLEAF_SIZE:
            action_table[pos * 2] = action
            action_table[pos * 2 + 1] = action
    action_table[pos] = action_unity


def force_down_propagate(action_table, value_table, pos, action_composite, action_force, action_unity):
    max_level = pos.bit_length() - 1

    for level in range(max_level):
        i = pos >> (max_level - level)
        action = action_table[i]
        if action != action_unity:
            action_table[i * 2] = action_composite(action, action_table[i * 2])
            action_table[i * 2 +
                         1] = action_composite(action, action_table[i * 2 + 1])
            action_table[i] = action_unity
            value_table[i * 2] = action
            value_table[i * 2 + 1] = action


def down_propagate_target(pos):
    max_level = pos.bit_length() - 1

    for level in range(max_level):
        i = pos >> (max_level - level)
        yield i


@profile
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
            action_table[left] = action
            left += 1
        if right & 1:
            right -= 1
            value_table[right] = action
            action_table[right] = action

        left //= 2
        right //= 2


@profile
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)


@profile
def up_prop_force(value_table, action_table, pos, binop, action_force, action_composite, action_unity):
    """
    force_children + up_propagation
    """
    while pos > 1:
        pos >>= 1
        force_point(
            value_table, action_table,
            pos * 2, action_force, action_composite, action_unity)

        force_point(
            value_table, action_table,
            pos * 2 + 1, action_force, action_composite, action_unity)
        value_table[pos] = binop(
            value_table[pos * 2],
            value_table[pos * 2 + 1]
        )


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


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


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


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

    force_down_propagate(
        action_table, value_table, up(start),
        action_composite, action_force,  action_unity)
    force_down_propagate(
        action_table, value_table, up(end),
        action_composite, action_force, action_unity)

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


def 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")


def main():
    N, Q = map(int, input().split())
    set_width(N)

    value_unity = (1 << 31) - 1
    value_table = [value_unity] * SEGTREE_SIZE
    action_unity = -1
    action_table = [action_unity] * SEGTREE_SIZE

    action_force = None

    def action_composite(new_action, old_action):
        return new_action

    for _ in range(Q):
        q, *args = map(int, input().split())
        if q == 0:
            # update
            s, t, value = args
            lazy_range_update(
                action_table, value_table, s, t + 1, value,
                action_composite, action_force, action_unity, min)
        else:
            # find
            s, t = args
            print(lazy_range_reduce(
                action_table, value_table, s, t + 1,
                action_composite, action_force, action_unity, min, value_unity))
        # debugprint(action_table)
        # debugprint(value_table)


T1 = """
3 5
0 0 1 1
0 1 2 3
0 2 2 2
1 0 2
1 1 2
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
2
"""
T2 = """
1 3
1 0 0
0 0 0 5
1 0 0
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
2147483647
5
"""
T3 = """
8 10
0 1 6 5
0 2 7 2
0 2 5 7
1 3 3
1 2 4
1 0 3
1 5 7
1 2 6
0 3 7 9
1 2 6
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
7
7
5
2
2
7
"""
T4 = """
15 3
0 1 6 5
0 2 7 2
1 6 7
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
2
"""


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")


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

main()

Submission status: Accepted

Solution code:
from typing import Callable, Iterator, List, Optional, Sequence, Union


class LazySegmentTree:
    """Segment Tree with Lazy Propagation"""

    __slots__ = [
        "_identity",
        "_seg_func",
        "_modifying_func",
        "_level",
        "_size",
        "_tree",
        "_lazy",
    ]

    def __init__(
        self,
        initial_values: Sequence,
        identity: Union[int, str],
        seg_func: Callable,
        modifying_func: Optional[Callable] = None,
    ) -> None:
        self._identity = identity
        self._seg_func = seg_func
        self._modifying_func = modifying_func
        self._level = (len(initial_values) - 1).bit_length()
        self._size = 1 << self._level
        self._tree = self._build(initial_values)
        self._lazy: List[Optional[Union[int, str]]] = [None] * (2 * self._size)

    def _build(self, initial_values: Sequence) -> List[Union[int, str]]:
        """Build a segment tree with initial values."""
        tree = [self._identity] * (2 * self._size)

        if self._modifying_func:
            initial_values = map(self._modifying_func, initial_values)

        for idx, val in enumerate(initial_values):  # set a tree
            tree[idx + self._size - 1] = val

        for idx in range(self._size - 2, -1, -1):  # build
            tree[idx] = self._seg_func(tree[2 * idx + 1], tree[2 * idx + 2])

        return tree

    def _generate_indices(self, initial_left: int, initial_right: int) -> Iterator[int]:
        """Generate indices to propagate."""
        left = (initial_left + self._size) >> 1
        right = (initial_right + self._size) >> 1
        lc = 0 if initial_left & 1 else (left & -left).bit_length()
        rc = 0 if initial_right & 1 else (right & -right).bit_length()

        for i in range(self._level):
            if lc <= i:
                yield left
            if rc <= i:
                yield right
            left >>= 1
            right >>= 1

    def _propagate(self, *indices: int) -> None:
        """Propagate a given section."""
        for i in reversed(indices):
            value = self._lazy[i - 1]
            if value is not None:
                self._tree[2 * i - 1] = self._tree[2 * i] = value
                self._lazy[2 * i - 1] = self._lazy[2 * i] = value
                self._lazy[i - 1] = None

    def update(self, left: int, right: int, value: Union[int, str]) -> None:
        """Update [left, right] to value."""
        right += 1  # [left, right] == [left, right + 1)
        if self._modifying_func:
            value = self._modifying_func(value)
        (*indices,) = self._generate_indices(left, right)
        self._propagate(*indices)
        left += self._size
        right += self._size
        while left < right:
            if left & 1:
                self._lazy[left - 1] = self._tree[left - 1] = value
                left += 1
            if right & 1:
                right -= 1
                self._lazy[right - 1] = self._tree[right - 1] = value
            left >>= 1
            right >>= 1

        for i in indices:
            self._tree[i - 1] = self._seg_func(self._tree[2 * i - 1], self._tree[2 * i])

    def query(self, left: int, right: int) -> Union[int, str]:
        """Respond to query in [left, right]."""
        right += 1  # [left, right] == [left, right + 1)
        self._propagate(*self._generate_indices(left, right))
        left += self._size
        right += self._size
        result = self._identity
        while left < right:
            if left & 1:
                result = self._seg_func(result, self._tree[left - 1])
                left += 1
            if right & 1:
                right -= 1
                result = self._seg_func(result, self._tree[right - 1])
            left >>= 1
            right >>= 1
        return result


def main():
    # https://onlinejudge.u-aizu.ac.jp/problems/DSL_2_F
    import sys

    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines

    N, _ = map(int, readline().split())
    tree = LazySegmentTree([2 ** 31 - 1] * N, 2 ** 31 - 1, min)
    ans = []
    for query in readlines():
        com, *info = map(int, query.split())
        if com:
            ans.append(tree.query(*info))
        else:
            tree.update(*info)
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#####segfunc#####
def segfunc(x, y):
    return min(x, y)
#################

#####ide_ele#####
ide_ele = 2**31 - 1
#################

class LazySegmentTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(l, r, x): 区間[l, r)をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        num: n以上の最小の2のべき乗
        data: 値配列(1-index)
        lazy: 遅延配列(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [None] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.data[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])

    def gindex(self, l, r):
            """
            伝搬する対象の区間を求める
            lm: 伝搬する必要のある最大の左閉区間
            rm: 伝搬する必要のある最大の右開区間
            """
            l += self.num
            r += self.num
            lm = l >> (l & -l).bit_length()
            rm = r >> (r & -r).bit_length()

            while r > l:
                if l <= lm:
                    yield l
                if r <= rm:
                    yield r
                r >>= 1
                l >>= 1
            while l:
                yield l
                l >>= 1

    def propagates(self, *ids):
        """
        遅延伝搬処理
        ids: 伝搬する対象の区間 
        """
        for i in reversed(ids):
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[2 * i] = v
            self.lazy[2 * i + 1] = v
            self.data[2 * i] = v
            self.data[2 * i + 1] = v
            self.lazy[i] = None

    def update(self, l, r, x):
        """
        区間[l, r)の値をxに更新
        l, r: index(0-index)
        x: update value
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] = x
                self.data[l] = x
                l += 1
            if r & 1:
                self.lazy[r - 1] = x
                self.data[r - 1] = x
            r >>= 1
            l >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])


    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.data[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res
n, q = [int(x) for x in input().split()]
seg = LazySegmentTree([ide_ele]*n, segfunc, ide_ele)
for _ in range(q):
    a, *b = [int(x) for x in input().split()]
    if a == 1:
        s, t = b
        print(seg.query(s, t + 1))
    else:
        s, t, x = b
        seg.update(s, t + 1, x)

Submission status: Accepted

Solution code:
# ref http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3986599#1
class Lazy_SegTree:
    """
    Lazy Segment Tree
        * handle range update
    """

    def __init__(self, n, func, init=float('inf')):
        """__init__
        :param
            n: size of node
            func: merge func
            init: initial value of each nde
        """
        self._n = n
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.lazy = [None]*(2*self.n)
        self.func = func

    def set(self, pos, val):
        """set

        :param pos: position of value
        :param val: set value
        """
        self.data[pos+self.n-1] = val

    def build(self):
        """build
            called after set, build initial seg tree
        """
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def _update_range(self, l, r):
        """_update_range
            get range of updated nodes

        :param l:
        :param r:
        """
        L = l+self.n
        R = r+self.n

        lm = (L//(L & -L)) >> 1
        rm = (R//(R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1
            R >>= 1
        while L:
            yield L
            L >>= 1

    def _propagates(self, *ids):
        """_propagates
            propagete lazy-value

        :param *ids:
        """
        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
            self.lazy[i-1] = None

    def update(self, l, r, x):
        """update
            update values [l,r) with x
        :param l: left index
        :param r: right index
        :param x: value
        """
        *ids, = self._update_range(l, r)
        self._propagates(*ids)
        L = l+self.n
        R = r + self.n
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = x
                L += 1
            L >>= 1
            R >>= 1
        for i in ids:
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i])

    def query(self, l, r):
        """query
            return value [l,r)
        :param l: left index
        :param r: right index
        """
        self._propagates(*self._update_range(l, r))
        L = l + self.n
        R = r + self.n
        ret = self.init

        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

    def print_tree(self):
        print(" ".join(map(str, [self.data[i+self.n-1]
                                 for i in range(self._n)])))


N, Q = map(int, input().split())
query = [list(map(lambda x:int(x), input().split())) for _ in range(Q)]
Seg = Lazy_SegTree(N+1, min, 2**31-1)
Seg.build()
for q in query:
    if q[0] == 0:
        s = q[1]
        t = q[2]
        x = q[3]
        Seg.update(s, t+1, x)
    else:
        s = q[1]
        t = q[2]
        r = Seg.query(s, t+1)
        print(r)