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 sys
input = sys.stdin.readline
class LazySegTree:
    """
    遅延評価セグメント木
    デフォルト引数は RMQ and RUQ
    値の更新・取得は半開区間
    内部実装は 1-indexed
    参考: https://yukicoder.me/submissions/295288

    """
    def __init__(self,
                 a,
                 op=lambda a,b: a if a<b else b,
                 op_e=(1<<31)-1,
                 ap=lambda a,b,length: a if a!=-1 else b,
                 cp=lambda a,b: a if a!=-1 else b,
                 ap_identity=-1):
        """
        :param a: 初期状態
        :param op: 区間取得のための関数
        :param op_e: 単位元
        :param ap: 区間更新のための関数　第1引数は作用させる値　第2引数はもとの値
        :param cp: ap を結合するための関数
        :param ap_identity: 恒等変換
        """
        self.n = n = len(a)
        self.op, self.op_e, self.ap, self.cp, self.ap_identity = op, op_e, ap, cp, ap_identity
        self.val = val = [op_e] * n + a
        self.act = [ap_identity] * n
        self.length = length = [1] * (2*n)
        l = 2*n-2
        for i in range(n-1, 0, -1):
            r = l+1
            length[i] = length[l] + length[r]
            val[i] = op(val[l], val[r])
            l -= 2

    def get(self, l, r):
        self._push(l, r)
        res_l = res_r = self.op_e
        l += self.n
        r += self.n
        val, op = self.val, self.op
        while l < r:
            if l & 1:
                res_l = op(res_l, val[l])
            if r & 1:
                res_r = op(val[r-1], res_r)
            l = l+1 >> 1
            r >>= 1
        return op(res_l, res_r)

    def push(self):
        for i in range(1, self.n):
            self._push_one(i)

    def set(self, l, r, value):
        # 区間更新
        if l >= r:
            return
        n, ap, val, op, act, cp, length = self.n, self.ap, self.val, self.op, self.act, self.cp, self.length
        self._push(l, r)
        l = i = l + n
        r = j = r + n
        if i & 1: val[i] = ap(value, val[i], length[i])
        if j & 1: j-=1; val[j] = ap(value, val[j], length[j])
        i = i+1 >> 1
        j >>= 1
        while i < j:
            if i & 1:
                val[i] = ap(value, val[i], length[i])
                act[i] = cp(value, act[i])
            if j & 1:
                j -= 1
                val[j] = ap(value, val[j], length[j])
                act[j] = cp(value, act[j])
            i = i+1 >> 1
            j >>= 1
        l = l // (l & -l) >> 1
        while l>0:
            val[l] = op(val[2*l], val[2*l+1])
            l >>= 1
        r = r // (r & -r) >> 1
        while r>0:
            val[r] = op(val[2*r], val[2*r+1])
            r >>= 1

    def set_one(self, i, value):
        # 値の代入のみ行う
        val, op = self.val, self.op
        self._push(i, i+1)
        i += self.n
        val[i] = value
        i >>= 1
        while i>0:
            val[i] = op(val[2*i], val[2*i+1])
            i >>= 1

    def _ap(self, value, i):
        # 内部インデックス i の要素に値 value で作用させる
        self.val[i] = self.ap(value, self.val[i], self.length[i])
        if i < self.n:
            self.act[i] = self.cp(value, self.act[i])

    def _push_one(self, i):
        act = self.act
        self._ap(act[i], 2*i)
        self._ap(act[i], 2*i+1)
        act[i] = self.ap_identity

    def _push(self, l, r):
        n, act, ap_identity, ap, cp, val, length = self.n, self.act, self.ap_identity, self.ap, self.cp, self.val, self.length
        ln = l + n
        rnm1 = r + n - 1
        hl = ln.bit_length()-1
        hr = rnm1.bit_length()-1
        for hr in range(hr, 0, -1):
            al = ln >> hl
            ar = rnm1 >> hr
            if al < n:
                #_push_one(al)
                al_l = 2 * al
                al_r = al_l + 1
                act_al = act[al]
                val[al_l] = ap(act_al, val[al_l], length[al_l])
                if al_l < n:
                    act[al_l] = cp(act_al, act[al_l])
                val[al_r] = ap(act_al, val[al_r], length[al_r])
                if al_r < n:
                    act[al_r] = cp(act_al, act[al_r])
                act[al] = ap_identity
            if ar != al:
                #_push_one(ar)
                ar_l = 2 * ar
                ar_r = ar_l + 1
                act_ar = act[ar]
                val[ar_l] = ap(act_ar, val[ar_l], length[ar_l])
                if ar_l < n:
                    act[ar_l] = cp(act_ar, act[ar_l])
                val[ar_r] = ap(act_ar, val[ar_r], length[ar_r])
                if ar_r < n:
                    act[ar_r] = cp(act_ar, act[ar_r])
                act[ar] = ap_identity
            hl -= 1


N, Q = map(int, input().split())
tree = LazySegTree([(1<<31)-1]*N)
ans = []
for i in range(Q):
    q, *A = map(int, input().split())
    if q==0:
        s, t, x = A
        tree.set(s, t+1, x)
    else:
        s, t = A
        ans.append(tree.get(s, t+1))
print("\n".join(map(str, ans)))

Submission status: Accepted

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

def gindex(l,r):
    L,R=l+N0,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==None:
            continue
        lazy[2*i-1]=v
        lazy[2*i]=v
        data[2*i-1]=v
        data[2*i]=v
        lazy[i-1]=None
def update(l,r,x):#1-index [s,t)
    L,R=N0+l,N0+r
    *ids,=gindex(l,r)
    propagates(*ids)
    while L<R:#上から
        if R&1:
            R-=1
            lazy[R-1]=x
            data[R-1]=x
        if L&1:
            lazy[L-1]=x
            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,R=N0+l,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
n,q=map(int,input().split())

LV=n.bit_length()
N0=2**LV
INF=2**40
data=[2**31-1]*2*N0
lazy=[None]*2*N0
for i in range(q):
    l=list(map(int,input().split()))
    if l[0]==0:
        s,t,x=l[1:]
        update(s,t+1,x)
    else:
        s,t=l[1:]
        print(query(s,t+1))

Submission status: Accepted

Solution code:
import sys
class Lazysegtree:
    def __init__(self, A, intv, initialize = True):
        #区間は 1-indexed で管理
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        #self.segf = segf
        self.lazy = [None]*(2*self.N0)
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-2, -1, -1):
                self.data[i] = min(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
  
    def _ascend(self, k):
        k = k >> 1
        c = k.bit_length()
        for j in range(c):
            idx = k >> j
            self.data[idx] = min(self.data[2*idx], self.data[2*idx+1])
              
    def _descend(self, k):
        k = k >> 1
        idx = 1
        c = k.bit_length()
        for j in range(1, c+1):
            idx = k >> (c - j)
            if self.lazy[idx] is None:
                continue
            self.data[2*idx] = self.data[2*idx+1] = self.lazy[2*idx] \
            = self.lazy[2*idx+1] = self.lazy[idx] 
            self.lazy[idx] = None
              
              
    def query(self, l, r):
        L = l+self.N0
        R = r+self.N0
        self._descend(L//(L & -L))
        self._descend(R//(R & -R) - 1)
          
        s = self.intv                                                                   
  
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R])
            if L & 1:
                s = min(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
      
    def update(self, l, r, x):
        L = l+self.N0
        R = r+self.N0
  
        Li = L//(L & -L)
        Ri = R//(R & -R)
        self._descend(Li)
        self._descend(Ri-1)
          
        while L < R :
            if R & 1:
                R -= 1
                self.data[R] = x
                self.lazy[R] = x
            if L & 1:
                self.data[L] = x
                self.lazy[L] = x
                L += 1
            L >>= 1
            R >>= 1
          
        self._ascend(Li)
        self._ascend(Ri-1)
  
N, Q = map(int, input().split())
T = Lazysegtree([None]*N, 2**31-1, initialize = False) 
Ans = []
for _ in range(Q):
    t, *q = map(int, sys.stdin.readline().split())
    q[1] += 1
    if t:
        Ans.append(T.query(*q))
    else:
        T.update(*q)
print('\n'.join(map(str, Ans)))

Submission status: Accepted

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

n, q = map(int, input().split())
INF = 2**31-1

Len = (n-1).bit_length()
size = 2**Len
tree = [INF]*(2*size)
lazy = [None]*(2*size)

def gindex(l,r):
    L = (l+size)>>1;R=(r+size)>>1
    lc = 0 if l & 1 else (L&-L).bit_length()
    rc = 0 if r & 1 else (R&-R).bit_length()
    for i in range(Len):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1
        
        

def propagates(ids):
    #上から更新
    for i in reversed(ids):
        v = lazy[i]
        if v is None:
            continue
        lazy[2*i]=tree[2*i]=lazy[2*i+1]=tree[2*i+1]=v
        lazy[i]=None

#[l,r)の探索
def update(l,r,x):
    *ids, = gindex(l, r)
    propagates(ids)
    
    L = size+l
    R = size+r
    while L<R:
        if R&1:
            R -= 1
            lazy[R]=tree[R]=x
        if L&1:
            lazy[L]=tree[L]=x
            L+=1
        L>>=1;R>>=1
    #値を更新し終わったら、最小値を下から更新
    for i in ids:
        if 2*i+1<size*2:
            tree[i]=min(tree[i*2],tree[i*2+1])
        
def query(l, r):
    *ids, = gindex(l, r)
    propagates(ids)
    L = size + l
    R = size + r
    s = INF
    while L<R:
        if R&1:
            R-=1
            s = min(s,tree[R])
        if L&1:
            s = min(s,tree[L])
            L+=1
        L>>=1;R>>=1
    return s

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

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
 
 
answer = []
for q in range(Q):
    t, *cmd = map(int, readline().split())
    if t:
        s, t = cmd
        answer.append(str(query(s, t+1)))
    else:
        s, t, x = cmd
        update(s, t+1, x)
 
write("\n".join(answer))
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 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:
#!/usr/bin/env python3
# DSL_2_F: RMQ and RUQ
# Range Minimum Query and Range Update Query


class SegmentTree:
    INITIAL_VALUE = 2**31 - 1
    DIVIDED = -1

    def __init__(self, n):
        size = 1
        while size < n:
            size *= 2
        self.size = 2*size - 1
        self.data = [-1] * self.size
        self.data[0] = self.INITIAL_VALUE

    def set_range(self, lo, hi, v):
        def _set_range(r, i, j, vv):
            if j < lo or i > hi:
                if vv != self.DIVIDED:
                    self.data[r] = vv
            elif lo <= i and j <= hi:
                self.data[r] = v
            else:
                if self.data[r] != self.DIVIDED:
                    if vv == self.DIVIDED:
                        vv = self.data[r]
                    self.data[r] = self.DIVIDED
                mid = i + (j - i)//2
                _set_range(r*2 + 1, i, mid, vv)
                _set_range(r*2 + 2, mid+1, j, vv)

        _set_range(0, 0, self.size//2, self.DIVIDED)

    def min(self, i, j):
        def _min(r, lo, hi):
            if j < lo or i > hi:
                return self.INITIAL_VALUE
            elif self.data[r] != self.DIVIDED:
                return self.data[r]
            else:
                mid = lo + (hi - lo)//2
                return min(_min(r*2 + 1, lo, mid),
                           _min(r*2 + 2, mid+1, hi))

        return _min(0, 0, self.size//2)


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

    tree = SegmentTree(n)

    for _ in range(q):
        com, *args = input().split()
        if com == '0':
            s, t, x = [int(i) for i in args]
            tree.set_range(s, t, x)
        elif com == '1':
            s, t = [int(i) for i in args]
            print(tree.min(s, t))


if __name__ == '__main__':
    run()

Submission status: Runtime Error

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