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: Wrong Answer

Solution code:
INT_MAX = 1<<31 - 1
_N,query_num = map(int, input().split())
queries = [list(map(int, input().split())) for i in range(query_num)]
N = 1<<17

arr_size = 2*N - 1
A = [INT_MAX]*(arr_size)
lazy_A = [None]*(arr_size)

def tree_propagate(k):

    if(lazy_A[k] is None):
        return

    if(k < N // 2):
        A[k*2+1] = A[k*2+2] = lazy_A[k*2+1] = lazy_A[k*2+2] = lazy_A[k]
        lazy_A[k] = None
        return
    if(k < N-1):
        A[k*2+1] = A[k*2+2] = lazy_A[k]
        lazy_A[k] = None

def update(s,t,x,k,l,r):

    if (r <= s or t <= l):
        return
    if (s <= l and r <= t):
        A[k] = x
        if(k < N-1):
            lazy_A[k] = x
        return

    tree_propagate(k)
    center = (l+r)//2
    update(s, t, x, k*2 + 1, l, center)
    update(s, t, x, k*2 + 2, center, r)

    A[k] = min(A[k*2+1], A[k*2+2])

def find(s,t,k,l,r):

    if (r <= s or t <= l):
        return INT_MAX

    if(s <= l and r <= t):
        return A[k]

    tree_propagate(k)
    center = (l+r)//2
    v_left = find(s, t, k*2 + 1, l, center)
    v_right = find(s, t, k*2 + 2, center, r)
    return min(v_left,v_right)

answers = []
for query in queries:
    # update
    if(query[0]==0):
        update(query[1],query[2]+1,query[3],0,0,N)
    # find
    else:
        answers.append(find(query[1],query[2]+1,0,0,N))

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

Submission status: Wrong Answer

Solution code:
from math import log2, ceil


class SegmentTree:
    SENTINEL = 2 ** 31 - 1

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

    def find(self, c, l, r, s, t):
        if l == s 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, c, l, r, s, t, x):
        if l == s and r == t:
            self.a[c] = x
            return x
        mid = (l + r) // 2
        if t <= mid:
            if self.a[c * 2 + 1] == self.SENTINEL:
                self.a[c * 2 + 1] = self.a[c]
            u = min(self.update(c * 2, l, mid, s, t, x), self.a[c * 2 + 1])
        elif s > mid:
            if self.a[c * 2] == self.SENTINEL:
                self.a[c * 2] = self.a[c]
            u = min(self.a[c * 2], self.update(c * 2 + 1, mid + 1, r, s, t, x))
        else:
            u = min(
                self.update(c * 2, l, mid, s, mid, x),
                self.update(c * 2 + 1, mid + 1, r, mid + 1, t, x))
        self.a[c] = u
        return u


n, q = map(int, input().split())
st = SegmentTree(n)
for _ in range(q):
    query = input().split()
    if query[0] == '0':
        s, t, x = map(int, query[1:])
        st.update(1, 0, n - 1, s, t, x)
    else:
        s, t = map(int, query[1:])
        print(st.find(1, 0, n - 1, s, t))

Submission status: Wrong Answer

Solution code:
from math import log2, ceil


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

    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, c, l, r, s, t, x):
        if l == s and r == t:
            self.postpone(c, x)
            return x
        mid = (l + r) // 2
        if t <= mid:
            rv = self.a[c * 2 + 1]
            if rv == -1:
                rv = self.postpone(c * 2 + 1, self.a[c])
            u = min(self.update(c * 2, l, mid, s, t, x), rv)
        elif s > mid:
            lv = self.a[c * 2]
            if lv == -1:
                lv = self.postpone(c * 2, self.a[c])
            u = min(lv, self.update(c * 2 + 1, mid + 1, r, s, t, x))
        else:
            u = min(
                self.update(c * 2, l, mid, s, mid, x),
                self.update(c * 2 + 1, mid + 1, r, mid + 1, t, x))
        self.a[c] = u
        return u

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


n, q = map(int, input().split())
st = SegmentTree(n)
for _ in range(q):
    query = input().split()
    if query[0] == '0':
        s, t, x = map(int, query[1:])
        st.update(1, 0, n - 1, s, t, x)
    else:
        s, t = map(int, query[1:])
        print(st.find(1, 0, n - 1, s, t))

Submission status: Wrong Answer

Solution code:
from math import log2, ceil


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

    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, c, l, r, s, t, x, f=False):

        if not f 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:
                u = min(f, u)
        self.a[c] = u

        return u

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

    def get_child(self, c, child, f):
        if f:
            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)
for _ in range(q):
    query = input().split()
    if query[0] == '0':
        s, t, x = map(int, query[1:])
        st.update(1, 0, st.tn - 1, s, t, x)
    else:
        s, t = map(int, query[1:])
        print(st.find(1, 0, st.tn - 1, s, t))
        # print(st.a)

Submission status: Wrong Answer

Solution code:
import math

lazy_default = None

def update_tree(k: int):
    if k >= l:
        k >>= l
    while k > 0:
        left, right = tree[k << 1], tree[(k << 1) + 1]
        # ===== 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
    # ===== change me =====
    if value is not lazy_default:
        tree[node_index] = value

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

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

    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]

        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
        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 != 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)
                    update_tree(r_node)
                    append(tree[r_node])
                    r_active = 0
                else:
                    if lazy_right != 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: Wrong Answer

Solution code:
import math

lazy_default = None

def update_tree(k: int):
    if k >= l:
        k >>= 1
    while k > 0:
        left, right = tree[k << 1], tree[(k << 1) + 1]
        # ===== 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
    # ===== change me =====
    if value is not lazy_default:
        tree[node_index] = value

    if node_index < l and value != lazy_default:
        # ===== 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:
        update_tree(node_index)

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

    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]

        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
        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 != 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)
                    update_tree(r_node)
                    append(tree[r_node])
                    r_active = 0
                else:
                    if lazy_right != 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
        #print(d, lazy,"\n",tree)
    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: Wrong Answer

Solution code:
import math

lazy_default = None

def update_tree(k: int):
    if k >= l:
        k >>= 1
    while k > 0:
        left, right = tree[k << 1], tree[(k << 1) + 1]
        # ===== 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
    # ===== 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

    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)
                    update_tree(r_node)
                    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: Wrong Answer

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 = self.lazy, self.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
            else:
                tree[n] = value
            self.update_tree(n)

    def get_value(self, l: int, r: int):
        tree = self.tree
        index_list = self.get_indexes_with_propagation(l, r, 1, 0, self.elem_size)

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

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

        while k > 1:
            left, right = k << 1, (k << 1)+1
            left_value = lazy[left] or tree[left]
            right_value = lazy[right] or tree[right]
            # ===== change me =====
            tree[k] = left_value if left_value < right_value else right_value

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import time
sys.setrecursionlimit(20000)
INT_MAX = 2**31 - 1
def lazy_tree_merge(lazy,tree,i,N):
    if(lazy[i] is not None):
        tree[i] = lazy[i]
        if(i < N-1):
            lazy[i*2+1] = lazy[i]
            lazy[i*2+2] = lazy[i]
        lazy[i] = None

def update(tree,lazy,x,y,k,l,r,i,z,N):
    if (r <= x or y <= l):
        lazy_tree_merge(lazy,tree,k,N)
        return True
    if ( x <= l and r <= y):
        lazy[k] = z
        lazy_tree_merge(lazy,tree,k,N)
        return True

    lazy_tree_merge(lazy,tree,k,N)
    center = int((l+r)/2)
    update(tree, lazy, x, y, k*2 + 1, l, center, i, z, N)
    #update(tree, lazy, x, y, k*2 + 2, l, int((l+r)/2), i, z, N)
    update(tree, lazy, x, y, k*2 + 2, center, r, i, z, N)
    tree[k] = min(tree[k*2+1],tree[k*2+2])

def find(tree,lazy,x,y,k,l,r,N):

    if (r <= x or y <= l):
        return INT_MAX
    if ( x <= l and r <= y):
        lazy_tree_merge(lazy,tree,k,N)
        return tree[k]

    lazy_tree_merge(lazy,tree,k,N)
    v_left = find(tree, lazy_A, x, y, k*2 + 1, l, int((l+r)/2), N)
    v_right = find(tree, lazy_A, x, y, k*2 + 2, int((l+r)/2), r, N)
    #print(v_left)
    #print(v_right)
    return min(v_left, v_right)

if __name__ == '__main__':
    _N,query_num = map(int, input().split())
    N = 1
    while True:
        if(N >= _N):
            break
        N <<= 1
    if not (N == 1):
        A = [INT_MAX]*(2*N - 1)
        lazy_A = [None]*(2*N - 1)
    else:
        A = [INT_MAX]*(2*N)
        lazy_A = [None]*(2*N)
    #start = time.time()
    for i in range(query_num):
        query = list(map(int,input().split()))
        # update
        if(query[0]==0):
            update(A,lazy_A,query[1],query[2]+1,0,0,N,i,query[3],N)
            #print(A,lazy_A)
        # find
        if(query[0]==1):
            z = find(A,lazy_A,query[1],query[2]+1,0,0,N,N)
            print(z)
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
#import time
sys.setrecursionlimit(20000)
INT_MAX = 2**31 - 1

def tree_propagate(tree,lazy,k,N):
    if(lazy[k] is None):
        return
    if(k < N // 2):
        tree[k*2+1] = tree[k*2+2] = lazy[k]
        lazy[k*2+1] = lazy[k*2+2] = lazy[k]
        lazy[k] = None
        return
    if(k < N-1):
        tree[k*2+1] = tree[k*2+2] = lazy[k]
        lazy[k] = None

def update(tree,lazy,s,t,x,k,l,r,N):

    if (r <= s or t <= l):
        return
    if (s <= l and r <= t):
        tree[k] = x
        if(k < N-1):
            lazy[k] = x
        #tree_propagate(tree,lazy,k,N)
        return

    tree_propagate(tree,lazy,k,N)
    center = int((l+r)/2)
    update(tree, lazy, s, t, x, k*2 + 1, l, center, N)
    update(tree, lazy, s, t, x, k*2 + 2, center, r, N)

    tree[k] = min(tree[k*2+1], tree[k*2+2])

def find(tree,lazy,s,t,k,l,r,N):

    if (r <= s or t <= l):
        return INT_MAX

    if(s <= l and r <= t):
        return tree[k]

    tree_propagate(tree,lazy,k,N)
    center = int((l+r)/2)
    v_left = find(tree, lazy, s, t, k*2 + 1, l, center, N)
    v_right = find(tree, lazy, s, t, k*2 + 2, center, r, N)
    return min(v_left,v_right)

if __name__ == '__main__':
    _N,query_num = map(int, input().split())
    queries = [list(map(int, input().split())) for i in range(query_num)]
    N = 1
    while True:
        if(N >= _N):
            break
        N <<= 1

    A = [INT_MAX]*(2*N - 1)
    lazy_A = [None]*(2*N - 1)
    #start = time.time()
    answers = []
    #for i in range(query_num):
    for query in queries:
        #query = list(map(int,input().split()))
        # update
        if(query[0]==0):
            update(A,lazy_A,query[1],query[2]+1,query[3],0,0,N,N)
        # find
        if(query[0]==1):
            z = find(A,lazy_A,query[1],query[2]+1,0,0,N,N)
            answers.append(z)
            #print(z)
    for ans in answers:
        print(ans)
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Time Limit Exceeded

Solution code:
INT_MAX = (1<<31) - 1
_N,query_num = map(int, input().split())
queries = [list(map(int, input().split())) for i in range(query_num)]
N = 1<<17

arr_size = 2*N - 1
A = [INT_MAX]*(arr_size)
lazy_A = [None]*(arr_size)

def tree_propagate(k):
    if(lazy_A[k] is None):
        return
    if(k < N // 2):
        A[k*2+1] = A[k*2+2] = lazy_A[k*2+1] = lazy_A[k*2+2] = lazy_A[k]
        lazy_A[k] = None
        return
    if(k < N-1):
        A[k*2+1] = A[k*2+2] = lazy_A[k]
        lazy_A[k] = None

def update(s,t,x,k,l,r):
    if (r <= s or t <= l):
        return
    if (s <= l and r <= t):
        A[k] = x
        if(k < N-1):
            lazy_A[k] = x
        return

    tree_propagate(k)
    center = (l+r)//2
    update(s, t, x, k*2 + 1, l, center)
    update(s, t, x, k*2 + 2, center, r)
    A[k] = min(A[k*2+1], A[k*2+2])

def find(s,t,k,l,r):
    if (r <= s or t <= l):
        return INT_MAX
    if(s <= l and r <= t):
        return A[k]

    tree_propagate(k)
    center = (l+r)//2
    v_left = find(s, t, k*2 + 1, l, center)
    v_right = find(s, t, k*2 + 2, center, r)
    return min(v_left,v_right)

answers = []
for query in queries:
    if(query[0]==0):
        update(query[1],query[2]+1,query[3],0,0,N)
    else:
        answers.append(find(query[1],query[2]+1,0,0,N))

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

Submission status: Time Limit Exceeded

Solution code:
INT_MAX = (1<<31) - 1
_N,query_num = map(int, input().split())
queries = [list(map(int, input().split())) for i in range(query_num)]
N = 1<<17
N1 = N - 1
N2 = N1 // 2
arr_size = 2*N - 1
A = [INT_MAX]*(arr_size)
lazy_A = [-1]*(arr_size)

def tree_propagate(k):

    if(lazy_A[k] == -1):
        return

    if(k < N2):
        A[k*2+1] = A[k*2+2] = lazy_A[k*2+1] = lazy_A[k*2+2] = lazy_A[k]
        lazy_A[k] = -1
        return
    if(k < N1):
        A[k*2+1] = A[k*2+2] = lazy_A[k]
        lazy_A[k] = -1

def update(s,t,x,k,l,r):

    if (r <= s or t <= l):
        return
    if (s <= l and r <= t):
        A[k] = x
        if(k < N1):
            lazy_A[k] = x
        return

    tree_propagate(k)
    center = (l+r)//2
    update(s, t, x, k*2 + 1, l, center)
    update(s, t, x, k*2 + 2, center, r)

    A[k] = min(A[k*2+1], A[k*2+2])

def find(s,t,k,l,r):

    if (r <= s or t <= l):
        return INT_MAX

    if(s <= l and r <= t):
        return A[k]

    tree_propagate(k)
    center = (l+r)//2
    v_left = find(s, t, k*2 + 1, l, center)
    v_right = find(s, t, k*2 + 2, center, r)
    return min(v_left,v_right)

answers = []
for query in queries:
    if(query[0]==0):
        update(query[1],query[2]+1,query[3],0,0,N)
    else:
        answers.append(find(query[1],query[2]+1,0,0,N))

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

Submission status: Time Limit Exceeded

Solution code:
from math import log2, ceil


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

    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, 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 * 2 < self.l:
            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)
for _ in range(q):
    query = input().split()
    if query[0] == '0':
        s, t, x = map(int, query[1:])
        st.update(1, 0, st.tn - 1, s, t, x)
    else:
        s, t = map(int, query[1:])
        print(st.find(1, 0, st.tn - 1, s, t))
    # print(_, query, st.a)