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: Time Limit Exceeded

Solution code:
from math import log2, ceil


class SegmentTree:
    def __init__(self, n):
        self.n = n
        tn = 2 ** ceil(log2(n))
        self.a = [2 ** 31 - 1] * (tn * 2)
        self.tn = tn

    def find(self, s, t):
        return self.__find(1, 0, st.n - 1, s, t)

    def __find(self, c, l, r, s, t):
        if self.a[c] == -1:
            return self.a[c // 2]
        if s <= l and r <= t:
            return self.a[c]
        mid = (l + r) // 2
        if t <= mid:
            return self.__find(c * 2, l, mid, s, t)
        elif s > mid:
            return self.__find(c * 2 + 1, mid + 1, r, s, t)
        else:
            return min(
                self.__find(c * 2, l, mid, s, mid),
                self.__find(c * 2 + 1, mid + 1, r, mid + 1, t))

    def update(self, s, t, x):
        self.__update(1, 0, self.n - 1, s, t, x)

    def __update(self, c, l, r, s, t, x, f=None):

        if f is None and self.a[c] == -1:
            f = self.a[c // 2]

        if l == s and r == t:
            return self.__set(c, x)

        mid = (l + r) // 2
        if t <= mid:
            rv, f = self.__get_child_not_updated(c, c * 2 + 1, f)
            u = min(self.__update(c * 2, l, mid, s, t, x, f), rv)
        elif s > mid:
            lv, f = self.__get_child_not_updated(c, c * 2, f)
            u = min(lv, self.__update(c * 2 + 1, mid + 1, r, s, t, x, f))
        else:
            u = min(
                self.__update(c * 2, l, mid, s, mid, x, f),
                self.__update(c * 2 + 1, mid + 1, r, mid + 1, t, x, f))
            if f is not None:
                u = min(f, u)
        self.a[c] = u

        return u

    def __set(self, c, x):
        self.a[c] = x
        if c < self.tn:
            self.a[c * 2] = self.a[c * 2 + 1] = -1
        return x

    def __get_child_not_updated(self, c, child, f):
        if f is not None:
            return self.__set(child, f), f
        v = self.a[child]
        if v == -1:
            f = self.a[c]
            v = self.__set(child, f)
        return v, f


n, q = map(int, input().split())
st = SegmentTree(n)
buf = []
for _ in range(q):
    query = input().split()
    if query[0] == '0':
        st.update(*map(int, query[1:]))
    else:
        buf.append(st.find(*map(int, query[1:])))
        # print(_, query, st.a)
print('\n'.join(map(str, buf)))

Submission status: Time Limit Exceeded

Solution code:
from math import log2, ceil


class SegmentTree:
    def __init__(self, n):
        self.n = n
        tn = 2 ** ceil(log2(n))
        self.a = [2 ** 31 - 1] * (tn * 2)
        self.tn = tn

    def find(self, s, t):
        return self.__find(1, 0, st.n - 1, s, t)

    def __find(self, c, l, r, s, t):
        if self.a[c] == -1:
            return self.a[c // 2]
        if s <= l and r <= t:
            return self.a[c]
        mid = (l + r) // 2
        if t <= mid:
            return self.__find(c * 2, l, mid, s, t)
        elif s > mid:
            return self.__find(c * 2 + 1, mid + 1, r, s, t)
        else:
            return min(
                self.__find(c * 2, l, mid, s, mid),
                self.__find(c * 2 + 1, mid + 1, r, mid + 1, t))

    def update(self, s, t, x):
        self.__update(1, 0, self.n - 1, s, t, x)

    def __update(self, c, l, r, s, t, x, f=None):

        if f is None and self.a[c] == -1:
            f = self.a[c // 2]

        if l == s and r == t:
            return self.__set(c, x)

        mid = (l + r) // 2
        if t <= mid:
            rv, f = self.__get_child(c, c * 2 + 1, f)
            u = min(self.__update(c * 2, l, mid, s, t, x, f), rv)
        elif s > mid:
            lv, f = self.__get_child(c, c * 2, f)
            u = min(lv, self.__update(c * 2 + 1, mid + 1, r, s, t, x, f))
        else:
            u = min(
                self.__update(c * 2, l, mid, s, mid, x, f),
                self.__update(c * 2 + 1, mid + 1, r, mid + 1, t, x, f))
            if f is not None:
                u = min(f, u)
        self.a[c] = u

        return u

    def __set(self, c, x):
        self.a[c] = x
        if c < self.tn:
            self.a[c * 2] = self.a[c * 2 + 1] = -1
        return x

    def __get_child(self, c, child, f):
        if f is not None:
            return self.__set(child, f), f
        v = self.a[child]
        if v == -1:
            f = self.a[c]
            v = self.__set(child, f)
        return v, f


n, q = map(int, input().split())
st = SegmentTree(n)
buf = []
for _ in range(q):
    q_type, *query = map(int, input().split())
    if q_type == 0:
        st.update(*query)
    else:
        buf.append(st.find(*query))
        # print(_, query, st.a)
print('\n'.join(map(str, buf)))

Submission status: Time Limit Exceeded

Solution code:
import math

lazy_default = None

def update_tree(k: int):
    #print("update_tree",k)
    if k >= l:
        k >>= 1
    while k > 0:
        l_index, r_index = k << 1, (k << 1) + 1
        left = tree[l_index] if lazy[l_index] is None else lazy[l_index]
        right = tree[r_index] if lazy[r_index] is None else lazy[r_index]
        # ===== change me =====
        tree[k] = left if left < right else right
        k >>= 1

def merge(node_index, value, update=False):
    lazy_value = lazy[node_index]
    # ===== change me =====
    value = lazy_value if value is None else value
    lazy[node_index] = None
    #print("merge",node_index,value,update)
    # ===== change me =====
    if value is not None:
        tree[node_index] = value

    if value is not None and node_index < l:
        # ===== change me =====
        if node_index < l // 2:
            lazy[node_index << 1] = value
            lazy[(node_index << 1) + 1] = value
        else:
            tree[node_index << 1] = value
            tree[(node_index << 1) + 1] = value

    if update:
        if node_index >= l//2:
            update_tree(node_index)
        else:
            update_tree(node_index >> 1)

def hoge(s, e, value):
    s, e, d, l_active, r_active = s+l, e+l, rank, 1, 1
    values = []
    append = values.append
    #print("===hoge===",s,e,value)

    while l_active or r_active:
        l_node, r_node = s >> d, e >> d
        l_leaf = l_node << d, (l_node + 1 << d) - 1
        r_leaf = r_node << d, (r_node + 1 << d) - 1
        lazy_left, lazy_right = lazy[l_node], lazy[r_node]
        #print(l_node,r_node,d,lazy_left,lazy_right,l_active,r_active)

        if l_node == r_node:
            if l_leaf[0] == s and r_leaf[1] == e:
                # match
                merge(l_node, value, True)
                append(tree[l_node])
                break
            elif lazy_left is not None:
                merge(l_node, None)
        else:
            if l_active:
                if l_leaf[0] == s:
                    # match
                    merge(l_node, value, True)
                    append(tree[l_node])
                    l_active = 0
                # ??????????????????????????????????????????????¶?????????????????????´???
                else:
                    if lazy_left is not None:
                        merge(l_node, None)
                    if l_node >> 1 << 1 == l_node and l_node+1 < r_node:
                        # match
                        merge(l_node+1, value)
                        append(tree[l_node+1])

            if r_active:
                if r_leaf[1] == e:
                    # match
                    merge(r_node, value, True)
                    append(tree[r_node])
                    r_active = 0
                else:
                    if lazy_right is not None:
                        merge(r_node, None)
                    if r_node >> 1 << 1 == r_node-1 and l_node+1 < r_node:
                        # match
                        merge(r_node-1, value)
                        append(tree[r_node-1])
        d -= 1
    return values

def get_value(i):
    i += l
    v = 0
    for j in range(rank, -1, -1):
        v += lazy[i>>j]
    return v + tree[i]

n, q = map(int,input().split())
l = 1 << math.ceil(math.log2(n))
tree = [2**31-1]*(2*l)
lazy = [None]*(2*l)
rank = int(math.log2(l))
ans = []
ap = ans.append

for _ in [None]*q:
    query = list(map(int, input().split()))
    if query[0] == 0:
        hoge(query[1], query[2], query[3])
    else:
        a = hoge(query[1], query[2], None)
        ap(min(a))
print("\n".join((str(n) for n in ans)))

Submission status: Time Limit Exceeded

Solution code:
import math

lazy_default = None

def update_tree(k: int):
    #print("update_tree",k)
    if k >= l:
        k >>= 1
    while k > 0:
        l_index, r_index = k << 1, (k << 1) + 1
        left = tree[l_index] if lazy[l_index] is None else lazy[l_index]
        right = tree[r_index] if lazy[r_index] is None else lazy[r_index]
        # ===== change me =====
        tree[k] = left if left < right else right
        k >>= 1

def merge(node_index, value, update=False):
    lazy_value = lazy[node_index]
    # ===== change me =====
    value = lazy_value if value is None else value
    lazy[node_index] = None
    #print("merge",node_index,value,update)
    # ===== change me =====
    if value is not None:
        tree[node_index] = value

    if value is not None and node_index < l:
        # ===== change me =====
        if node_index < l // 2:
            lazy[node_index << 1] = value
            lazy[(node_index << 1) + 1] = value
        else:
            tree[node_index << 1] = value
            tree[(node_index << 1) + 1] = value

    if update:
        if node_index >= l//2:
            update_tree(node_index)
        else:
            update_tree(node_index >> 1)

def hoge(s, e, value):
    s, e, d, l_active, r_active = s+l, e+l, rank, 1, 1
    values = []
    append = values.append
    #print("===hoge===",s,e,value)

    while l_active or r_active:
        l_node, r_node = s >> d, e >> d
        l_leaf = l_node << d, (l_node + 1 << d) - 1
        r_leaf = r_node << d, (r_node + 1 << d) - 1
        lazy_left, lazy_right = lazy[l_node], lazy[r_node]
        #print(l_node,r_node,d,lazy_left,lazy_right,l_active,r_active)

        if l_node == r_node:
            if l_leaf[0] == s and r_leaf[1] == e:
                # match
                merge(l_node, value, True)
                if value is None:
                    append(tree[l_node])
                break
            elif lazy_left is not None:
                merge(l_node, None)
        else:
            if l_active:
                if l_leaf[0] == s:
                    # match
                    merge(l_node, value, True)
                    if value is None:
                        append(tree[l_node])
                    l_active = 0
                # ??????????????????????????????????????????????¶?????????????????????´???
                else:
                    if lazy_left is not None:
                        merge(l_node, None)
                    if l_node >> 1 << 1 == l_node and l_node+1 < r_node:
                        # match
                        merge(l_node+1, value)
                        if value is None:
                            append(tree[l_node+1])

            if r_active:
                if r_leaf[1] == e:
                    # match
                    merge(r_node, value, True)
                    if value is None:
                        append(tree[r_node])
                    r_active = 0
                else:
                    if lazy_right is not None:
                        merge(r_node, None)
                    if r_node >> 1 << 1 == r_node-1 and l_node+1 < r_node:
                        # match
                        merge(r_node-1, value)
                        if value is None:
                            append(tree[r_node-1])
        d -= 1
    return values

def get_value(i):
    i += l
    v = 0
    for j in range(rank, -1, -1):
        v += lazy[i>>j]
    return v + tree[i]

n, q = map(int,input().split())
l = 1 << math.ceil(math.log2(n))
tree = [2**31-1]*(2*l)
lazy = [None]*(2*l)
rank = int(math.log2(l))
ans = []
ap = ans.append

for _ in [None]*q:
    query = list(map(int, input().split()))
    if query[0] == 0:
        hoge(query[1], query[2], query[3])
    else:
        a = hoge(query[1], query[2], None)
        ap(min(a))
print("\n".join((str(n) for n in ans)))

Submission status: Time Limit Exceeded

Solution code:
import math

lazy_default = None

def update_tree(k: int):
    #print("update_tree",k)
    if k >= l:
        k >>= 1
    while k > 0:
        l_index, r_index = k << 1, (k << 1) + 1
        left = tree[l_index] if lazy[l_index] is None else lazy[l_index]
        right = tree[r_index] if lazy[r_index] is None else lazy[r_index]
        # ===== change me =====
        tree[k] = left if left < right else right
        k >>= 1

def merge(node_index, value, update=False):
    lazy_value = lazy[node_index]
    # ===== change me =====
    value = lazy_value if value is None else value
    lazy[node_index] = None
    #print("merge",node_index,value,update)
    # ===== change me =====
    if value is not None:
        tree[node_index] = value

    if value is not None and node_index < l:
        # ===== change me =====
        if node_index < l // 2:
            lazy[node_index << 1] = value
            lazy[(node_index << 1) + 1] = value
        else:
            tree[node_index << 1] = value
            tree[(node_index << 1) + 1] = value

    if update:
        if node_index >= l:
            node_index >>= 1
        while node_index > 0:
            l_index, r_index = node_index << 1, (node_index << 1) + 1
            left = tree[l_index] if lazy[l_index] is None else lazy[l_index]
            right = tree[r_index] if lazy[r_index] is None else lazy[r_index]
            # ===== change me =====
            tree[node_index] = left if left < right else right
            node_index >>= 1

def hoge(s, e, value):
    s, e, d, l_active, r_active = s+l, e+l, rank, 1, 1
    values = []
    append = values.append
    #print("===hoge===",s,e,value)

    while l_active or r_active:
        l_node, r_node = s >> d, e >> d
        l_leaf = l_node << d, (l_node + 1 << d) - 1
        r_leaf = r_node << d, (r_node + 1 << d) - 1
        lazy_left, lazy_right = lazy[l_node], lazy[r_node]
        #print(l_node,r_node,d,lazy_left,lazy_right,l_active,r_active)

        if l_node == r_node:
            if l_leaf[0] == s and r_leaf[1] == e:
                # match
                merge(l_node, value, True)
                if value is None:
                    append(tree[l_node])
                break
            elif lazy_left is not None:
                merge(l_node, None)
        else:
            if l_active:
                if l_leaf[0] == s:
                    # match
                    merge(l_node, value, True)
                    if value is None:
                        append(tree[l_node])
                    l_active = 0
                # ??????????????????????????????????????????????¶?????????????????????´???
                else:
                    if lazy_left is not None:
                        merge(l_node, None)
                    if l_node >> 1 << 1 == l_node and l_node+1 < r_node:
                        # match
                        merge(l_node+1, value)
                        if value is None:
                            append(tree[l_node+1])

            if r_active:
                if r_leaf[1] == e:
                    # match
                    merge(r_node, value, True)
                    if value is None:
                        append(tree[r_node])
                    r_active = 0
                else:
                    if lazy_right is not None:
                        merge(r_node, None)
                    if r_node >> 1 << 1 == r_node-1 and l_node+1 < r_node:
                        # match
                        merge(r_node-1, value)
                        if value is None:
                            append(tree[r_node-1])
        d -= 1
    return values

def get_value(i):
    i += l
    v = 0
    for j in range(rank, -1, -1):
        v += lazy[i>>j]
    return v + tree[i]

n, q = map(int,input().split())
l = 1 << math.ceil(math.log2(n))
tree = [2**31-1]*(2*l)
lazy = [None]*(2*l)
rank = int(math.log2(l))
ans = []
ap = ans.append

for _ in [None]*q:
    query = list(map(int, input().split()))
    if query[0] == 0:
        hoge(query[1], query[2], query[3])
    else:
        a = hoge(query[1], query[2], None)
        ap(min(a))
print("\n".join((str(n) for n in ans)))

Submission status: Time Limit Exceeded

Solution code:
import math


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

    def __init__(self, a: list, default: int):
        real_size = len(a)
        self.elem_size = 1 << math.ceil(math.log2(real_size))
        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 get_indexes(self, l: int, r: int):
        '''[x, y)'''
        l, r, indexes = l+self.elem_size, r+self.elem_size, []
        append = indexes.append
        while l < r:
            if l & 1:
                append(l)
                l += 1
            if r & 1:
                r -= 1
                append(r)
            l, r = l >> 1, r >> 1

        return indexes

    def get_indexes_with_propagation(self, l: int, r: int, current_node: int, l_end: int, r_end: int):
        # print(l,r,current_node,l_end,r_end,self.lazy[current_node])
        indexes = []
        tree, lazy = self.tree, self.lazy
        lazy_value = lazy[current_node]
        left_child, right_child = current_node << 1, (current_node << 1) + 1

        if lazy_value is not None:
            self.lazy[current_node] = None
            tree[current_node] = lazy_value
            if left_child < self.tree_size:
                if left_child < self.elem_size:
                    lazy[left_child] = lazy[right_child] = lazy_value
                else:
                    tree[left_child] = tree[right_child] = lazy_value

        if l == l_end and r == r_end:
            return [current_node]

        mid = (l_end + r_end) // 2

        if l < mid:
            l_r = r if r < mid else mid
            indexes += self.get_indexes_with_propagation(l, l_r, left_child, l_end, mid)

        if r > mid:
            r_l = l if mid < l else mid
            indexes += self.get_indexes_with_propagation(r_l, r, right_child, mid, r_end)

        return indexes

    def update_lazy(self, l, r, value):
        indexes = sorted(self.get_indexes_with_propagation(l, r, 1, 0, self.elem_size))
        l = self.elem_size
        lazy, tree, update = self.lazy, self.tree, self.update_tree
        for n in indexes:
            lazy[n] = None
            if n < l//2:
                lazy[n << 1] = value
                lazy[(n << 1)+1] = value
            elif n < l:
                tree[n << 1] = value
                tree[(n << 1)+1] = value
            tree[n] = value
            update(n)

    def get_value(self, l: int, r: int):
        tree = self.tree
        indexes = self.get_indexes_with_propagation(l, r, 1, 0, self.elem_size)
        update = self.update_tree
        for n in indexes:
            update(n)

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

    def update_tree(self, k: int):
        tree, lazy = self.tree, self.lazy
        if k >= self.elem_size:
            k >>= 1

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

            k >>= 1

    def set_value(self, i: int, value: int, op: str):
        k = self.elem_size + i
        if op == "=":
            self.tree[k] = value
        elif op == "+":
            self.tree[k] += value
        self.update_tree(k)


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.update_lazy(l[1], l[2]+1, l[3])
    else:
        a = rmq.get_value(l[1], l[2]+1)
        append(a)

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

Submission status: Time Limit Exceeded

Solution code:
import math


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

    def __init__(self, a: list, default: int):
        real_size = len(a)
        self.elem_size = 1 << math.ceil(math.log2(real_size))
        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 get_indexes(self, l: int, r: int):
        '''[x, y)'''
        l, r, targets, path, p_l, p_r, = l+self.elem_size, r+self.elem_size, [], set(), 0, 0
        t_ap, p_add = targets.append, path.add

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

        while p_l > 0 or p_r > 0:
            if p_l > 0:
                p_add(p_l)
                p_l >>= 1
            if p_r > 0:
                p_add(p_r)
                p_r >>= 1

        #print(targets, path)
        return sorted(targets), sorted(path)

    def propagate(self, indexes: list, value: int = None):
        tree, lazy = self.tree, self.lazy
        if value is None:
            for n in indexes:
                if lazy[n] is None:
                    continue
                tree[n] = lazy[n]
                if n < self.elem_size:
                    lazy[n << 1] = lazy[(n << 1)+1] = lazy[n]
                lazy[n] = None
        else:
            for n in indexes:
                if n < self.elem_size:
                    lazy[n << 1] = lazy[(n << 1)+1] = value
                tree[n] = value
                lazy[n] = None
                self.update_tree(n)

    def get_indexes_with_propagation(self, l: int, r: int, current_node: int, l_end: int, r_end: int):
        # print(l,r,current_node,l_end,r_end,self.lazy[current_node])
        indexes = []
        tree, lazy = self.tree, self.lazy
        lazy_value, lazy[current_node] = lazy[current_node], None
        left_child, right_child = current_node << 1, (current_node << 1) + 1

        if lazy_value is not None:
            tree[current_node] = lazy_value
            if left_child < self.tree_size:
                lazy[left_child] = lazy[right_child] = lazy_value

        if l == l_end and r == r_end:
            return [current_node]

        mid = (l_end + r_end) // 2

        if l < mid:
            l_r = r if r < mid else mid
            indexes += self.get_indexes_with_propagation(l, l_r, left_child, l_end, mid)
        if r > mid:
            r_l = l if mid < l else mid
            indexes += self.get_indexes_with_propagation(r_l, r, right_child, mid, r_end)

        return indexes

    def update_lazy(self, l, r, value):
        '''
        indexes = sorted(self.get_indexes_with_propagation(l, r, 1, 0, self.elem_size))
        l = self.elem_size
        lazy, tree, update = self.lazy, self.tree, self.update_tree
        for n in indexes:
            lazy[n] = None
            if n < l:
                lazy[n << 1] = value
                lazy[(n << 1)+1] = value
            tree[n] = value
            update(n)
        print("update_lazy",indexes)
        '''
        targets, paths = self.get_indexes(l, r)
        self.propagate(paths)
        self.propagate(targets, value)

    def get_value(self, l: int, r: int):
        '''
        tree = self.tree
        indexes = self.get_indexes_with_propagation(l, r, 1, 0, self.elem_size)
        update = self.update_tree
        for n in indexes:
            update(n)
        '''
        tree = self.tree
        targets, paths = self.get_indexes(l, r)
        self.propagate(paths)
        self.propagate(targets)

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

    def update_tree(self, k: int):
        tree, lazy = self.tree, self.lazy
        if k >= self.elem_size:
            k >>= 1

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

            k >>= 1

    def set_value(self, i: int, value: int, op: str):
        k = self.elem_size + i
        if op == "=":
            self.tree[k] = value
        elif op == "+":
            self.tree[k] += value
        self.update_tree(k)


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.update_lazy(l[1], l[2]+1, l[3])
        #print(rmq.get_indexes(l[1],l[2]+1))
    else:
        a = rmq.get_value(l[1], l[2]+1)
        #print(rmq.get_indexes(l[1],l[2]+1))
        append(a)
    #print(rmq.tree,rmq.lazy)

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