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

        deepest = (p_l, p_r)

        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), deepest

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

    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, deepest = self.get_indexes(l, r)
        self.propagate(paths)
        self.propagate(targets, value)
        self.update_tree(deepest[0])
        self.update_tree(deepest[1])

    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, deepest = self.get_indexes(l, r)
        self.propagate(paths)
        self.propagate(targets)
        self.update_tree(deepest[0])
        self.update_tree(deepest[1])

        # ===== 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]))

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, [], [], 0, 0
        t_ap, p_add = targets.append, path.append

        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

        deepest = (p_l, p_r)

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

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

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

    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, deepest = self.get_indexes(l, r)
        self.propagate(paths)
        self.propagate(targets, value)
        self.update_tree(deepest[0])
        self.update_tree(deepest[1])

    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, deepest = self.get_indexes(l, r)
        self.propagate(paths)
        self.propagate(targets)
        self.update_tree(deepest[0])
        self.update_tree(deepest[1])

        # ===== 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]))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

N, Q = map(int, input().split())
INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)

def gindex(l, r):
    L = l + N0; R = r + N0
    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(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s


ans = []
for q in range(Q):
    t, *cmd = map(int, readline().split())
    if t:
        s, t = cmd
        ans.append(str(query(s, t+1)))
    else:
        s, t, x = cmd
        update(s, t+1, x)

write("\n".join(ans))
write("\n")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
 
n, q = map(int, input().split())
INF = 2**31-1
 
LV = (n-1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)
 
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 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(LV):
        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-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None
 
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)
 
    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])
 
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r
 
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
 
 
ans = []
for i in range(q):
    t, *cmd = map(int, readline().split())
    if t:
        s, t = cmd
        ans.append(str(query(s, t+1)))
    else:
        s, t, x = cmd
        update(s, t+1, x)
 
write("\n".join(ans))
write("\n")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INT_MAX = (1<<31) - 1
_N,num = map(int, input().split())
Q = [list(map(int, input().split())) for i in range(num)]
N = 1<<17
N1 = N - 1
N2 = N1 // 2
ars = 2*N - 1
A = [INT_MAX]*(ars)
L = [-1]*(ars)

def propagate(k):

    if(L[k] == -1):
        return
    left = k*2+1
    right = k*2+2
    if(k < N2):
        A[left] = A[right] = L[left] = L[right] = L[k]
        L[k] = -1
        return
    if(k < N1):
        A[left] = A[right] = L[k]
        L[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):
            L[k] = x
        return

    propagate(k)
    mid = (l+r)//2
    left = k*2 + 1
    right = k*2 + 2
    update(s, t, x, left, l, mid)
    update(s, t, x, right, mid, r)

    A[k] = min(A[left], A[right])

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]

    propagate(k)
    mid = (l+r)//2
    left = k*2 + 1
    right = k*2 + 2
    v_left = find(s, t, left, l, mid)
    v_right = find(s, t, right, mid, r)
    return min(v_left,v_right)

res = []
for q in Q:
    # update
    if(q[0]==0):
        update(q[1],q[2]+1,q[3],0,0,N)
    # find
    else:
        res.append(find(q[1],q[2]+1,0,0,N))

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

Submission status: Accepted

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)
buf = []
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:])
        buf.append(st.find(1, 0, st.tn - 1, s, t))
        # print(_, query, st.a)
print('\n'.join(map(str, buf)))

Submission status: Accepted

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, self.tn - 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.tn - 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: Accepted

Solution code:
import math
from collections import deque


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, deque(), deque(), 0, 0
        t_ap, p_ap = targets.append, path.appendleft

        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

        deepest = (p_l, p_r)

        while p_l > 1 or p_r > 1:
            if p_l > 1:
                p_ap(p_l)
            if p_l != p_r > 1:
                p_ap(p_r)
            p_l >>= 1
            p_r >>= 1

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

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

    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, deepest = self.get_indexes(l, r)
        self.propagate(paths)
        self.propagate(targets, value)
        self.update_tree(deepest[0])
        self.update_tree(deepest[1])

    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, deepest = self.get_indexes(l, r)
        self.propagate(paths)
        self.propagate(targets)
        self.update_tree(deepest[0])
        self.update_tree(deepest[1])

        # ===== 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]))

Submission status: Accepted

Solution code:
import math
from collections import deque


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, deque(), deque(), 0, 0
        t_ap, p_ap = targets.append, path.appendleft

        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 >>= 1
            r >>= 1

        deepest = (p_l, p_r)

        while p_l > 1 or p_r > 1:
            if p_r != p_l > 1:
                p_ap(p_l)
            p_l >>= 1
            if p_r > 1:
                p_ap(p_r)
                p_r >>= 1

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

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

    def update_lazy(self, l, r, value):
        targets, paths, deepest = self.get_indexes(l, r)
        self.propagate(paths)
        self.propagate(targets, value)
        self.update_tree(deepest)

    def get_value(self, l: int, r: int):
        tree = self.tree
        targets, paths, deepest = self.get_indexes(l, r)
        self.propagate(paths)
        self.propagate(targets)
        self.update_tree(deepest)

        # ===== 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:
            #if k >= self.elem_size:
            #    k >>= 1

            while k > 0:
                left, right = k << 1, (k << 1)+1
                # ===== change me =====
                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]

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