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:
class LazyPropSegmentTree:
    def __init__(self, lst, op, apply, comp, e, identity):
        self.n = len(lst)
        self.depth = (self.n - 1).bit_length()
        self.N = 1 << self.depth
        self.op = op # binary operation of elements
        self.apply = apply # function to apply to an element
        self.comp = comp # composition of functions
        self.e = e # identity element w.r.t. op
        self.identity = identity # identity element w.r.t. comp
        self.v = self._build(lst) # self.v is set to be 1-indexed for simplicity
        self.lazy = [self.identity] * (2 * self.N)
    
    def __getitem__(self, i):
        return self.fold(i, i+1)
    
    def _build(self, lst):
        # construction of a tree
        # total 2 * self.N elements (tree[0] is not used)
        tree = [self.e] * (self.N) + lst + [self.e] * (self.N - self.n)
        for i in range(self.N - 1, 0, -1): tree[i] = self.op(tree[i << 1], tree[(i << 1)|1])
        return tree
    
    def _indices(self, l, r):
        left = l + self.N; right = r + self.N
        left //= (left & (-left)); right //= (right & (-right))
        left >>= 1; right >>= 1
        while left != right:
            if left > right: yield left; left >>= 1
            else: yield right; right >>= 1
        while left > 0: yield left; left >>= 1
    
    # propagate self.lazy and self.v in a top-down manner
    def _propagate_topdown(self, *indices):
        identity, v, lazy, apply, comp = self.identity, self.v, self.lazy, self.apply, self.comp
        for k in reversed(indices):
            x = lazy[k]
            if x == identity: continue
            lazy[k << 1] = comp(lazy[k << 1], x)
            lazy[(k << 1)|1] = comp(lazy[(k << 1)|1], x)
            v[k << 1] = apply(v[k << 1], x)
            v[(k << 1)|1] = apply(v[(k << 1)|1], x)
            lazy[k] = identity # propagated

    # propagate self.v in a bottom-up manner
    def _propagate_bottomup(self, indices):
        v, op = self.v, self.op
        for k in indices: v[k] = op(v[k << 1], v[(k << 1)|1])

    # update for the query interval [l, r) with function x
    def update(self, l, r, x):
        *indices, = self._indices(l, r)
        self._propagate_topdown(*indices)
        
        N, v, lazy, apply, comp = self.N, self.v, self.lazy, self.apply, self.comp
        
        # update self.v and self.lazy for the query interval [l, r)
        left = l + N; right = r + N
        if left & 1: v[left] = apply(v[left], x); left += 1
        if right & 1: right -= 1; v[right] = apply(v[right], x)
        left >>= 1; right >>= 1
        while left < right:
            if left & 1:
                lazy[left] = comp(lazy[left], x)
                v[left] = apply(v[left], x)
                left += 1
            if right & 1:
                right -= 1
                lazy[right] = comp(lazy[right], x)
                v[right] = apply(v[right], x)
            left >>= 1; right >>= 1
        self._propagate_bottomup(indices)
    
    # returns answer for the query interval [l, r)
    def fold(self, l, r):
        self._propagate_topdown(*self._indices(l, r))
        
        e, N, v, op = self.e, self.N, self.v, self.op
        
        # calculate the answer for the query interval [l, r)
        left = l + N; right = r + N
        L = R = e
        while left < right:
            if left & 1: # self.v[left] is the right child
                L = op(L, v[left])
                left += 1
            if right & 1: # self.v[right-1] is the left child
                right -= 1
                R = op(v[right], R)
            left >>= 1; right >>= 1
        return op(L, R)
    
N, Q = map(int, input().split())
op = min
apply = lambda x, f: f
comp = lambda f, g: g
e = 2**31 - 1
identity = None
A = [e] * N
lpsg = LazyPropSegmentTree(A, op, apply, comp, e, identity)
ans = []
for _ in range(Q):
    t, *arg, = map(int, input().split())
    if t == 0:
        s, t, x = arg
        lpsg.update(s, t+1, x)
    else:
        s, t = arg
        ans.append(lpsg.fold(s, t+1))
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_2_F
# 遅延セグ木


def _gidx(l, r, treesize):
    '''
    lazy propagation用idx生成器 木の下から生成される。1based-indexなので注意.(使うときは-1するとか)
    もとの配列において[l,r)を指定したときに更新すべきidxをyieldする
    treesizeは多くの場合self.num
    '''
    L, R = l + treesize, r + treesize
    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:  # Rでもいいけどね
        yield L
        L >>= 1


class SegmentTreeForRMQ:  # range minimum query
    def __init__(self, ls: list, segfunc=min, identity_element=2**63, lazy_ide=None):
        '''
        セグ木
        一次元のリストlsを受け取り初期化する。O(len(ls))
        区間のルールはsegfuncによって定義される
        identity elementは単位元。e.g., 最小値を求めたい→inf, 和→0, 積→1, gcd→0
        [単位元](https://ja.wikipedia.org/wiki/%E5%8D%98%E4%BD%8D%E5%85%83)
        '''
        self.ide = identity_element
        self.lide = lazy_ide  # lazy用単位元
        self.func = segfunc
        n = len(ls)
        self.num = 2 ** (n - 1).bit_length()  # n以上の最小の2のべき乗
        self.tree = [self.ide] * (2 * self.num)  # 関係ない値を-1においてアクセスを許すと都合が良い
        self.lazy = [self.lide] * (2 * self.num)  # 遅延配列
        for i, l in enumerate(ls):  # 木の葉に代入
            self.tree[i + self.num - 1] = l
        for i in range(self.num - 2, -1, -1):  # 子を束ねて親を更新
            self.tree[i] = segfunc(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def _lazyprop(self, *ids):
        '''
        遅延評価用の関数
        - self.tree[i] に self.lazy[i]の値を伝播させて遅延更新する
        - 子ノードにself.lazyの値を伝播させる **ここは問題ごとに書き換える必要がある**
        - self.lazy[i]をリセットする
        '''
        for i in reversed(ids):
            i -= 1  # 0basedindexに修正
            v = self.lazy[i]
            if v == self.lide:
                continue  # 単位元ならする必要のNASA
            # どうやって遅延更新するかは問題によってことなる
            # 今回なら数字書き換えなので数字をそのまま子ノードに伝播
            # lazyもtreeも書き換える必要あり
            self.tree[2 * i + 1] = v
            self.tree[2 * i + 2] = v
            self.lazy[2 * i + 1] = v
            self.lazy[2 * i + 2] = v
            self.lazy[i] = self.lide  # 遅延配列を空に戻す

    def update(self, l, r, x):
        '''
        [l,r)番目の要素をxに変更する(木の中間ノードも更新する) O(logN)
        '''
        # 1, 根から区間内においてlazyの値を伝播しておく(self.treeの値が有効になる)
        ids = tuple(_gidx(l, r, self.num))
        self._lazyprop(*ids)
        # 2, 区間に対してtree,lazyの値を更新 (treeは根方向に更新するため、lazyはpropで葉方向に更新するため)
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        l += self.num
        r += self.num
        while l < r:
            if r & 1:
                r -= 1  # 一旦半開ではなくするために
                self.tree[r - 1] = x
                self.lazy[r - 1] = x
            if l & 1:
                self.tree[l - 1] = x
                self.tree[l - 1] = x  # ここのセットの仕方も問題によって変えるべし
                self.lazy[l - 1] = x  # lazyの区間に値をセット
                l += 1
            l >>= 1
            r >>= 1
        # 3, 伝播させた区間について下からdataの値を伝播する
        for i in ids:
            i -= 1  # to 0based
            self.tree[i] = self.func(
                self.tree[2 * i + 1], self.tree[2 * i + 2])

    def query(self, l, r):
        '''
        区間[l,r)に対するクエリをO(logN)で処理する。例えばその区間の最小値、最大値、gcdなど
        '''
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        # 1, 根からにlazyの値を伝播させる
        self._lazyprop(*_gidx(l, r, self.num))
        # 2, 区間[l,r)の最小値を求める
        l += self.num
        r += self.num
        res = self.ide
        while l < r:  # 右から寄りながら結果を結合していくイメージ
            if r & 1:
                r -= 1
                res = self.func(res, self.tree[r - 1])
            if l & 1:
                res = self.func(res, self.tree[l - 1])
                l += 1
            l >>= 1
            r >>= 1  # 親の一つ左に移動
        return res


n, q = map(int, input().split())
ls = [2 ** 31 - 1] * n
seg = SegmentTreeForRMQ(ls, identity_element=2**31 - 1)

for _ in range(q):
    cmd, *tmp = map(int, input().split())
    if cmd == 0:
        s, t, x = tmp
        seg.update(s, t + 1, x)
    else:
        s, t = tmp
        print(seg.query(s, t + 1))

Submission status: Accepted

Solution code:
class LazySegTree: # Non Recursion, RmQ, RUQ
    def __init__(self, N):
        self.N = N
        self._N = 1<<((N-1).bit_length())
        self.INF = (1<<31) - 1
        self.node = [self.INF]*2*self._N
        self.lazy = [None]*2*self._N

    def build(self, lis):
        for i in range(self.N):
            self.node[i+self._N-1] = lis[i]
        for i in range(self._N-2,-1,-1):
            self.node[i] = self.node[i*2+1] + self.node[i*2+2]

    def _gindex(self, l, r):
        left = l + self._N; right = r + self._N
        lm = (left // (left & -left)) >> 1
        rm = (right // (right & -right)) >> 1
        while left < right:
            if right <= rm: yield right
            if left <= lm: yield left
            left >>= 1; right >>= 1
        while left:
            yield left
            left >>= 1

    def propagates(self, *ids): # ids: 1-indexded
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None: continue
            self.lazy[2*i-1] = self.node[2*i-1] = v
            self.lazy[2*i] = self.node[2*i] = v
            self.lazy[i-1] = None
        return

    def update(self, l, r, x): # change all[left, right) to x
        *ids, = self._gindex(l, r)
        self.propagates(*ids)
        left = l + self._N; right = r + self._N
        while left < right:
            if left & 1:
                self.lazy[left-1] = self.node[left-1] = x
                left += 1
            if right & 1:
                right -= 1
                self.lazy[right-1] = self.node[right-1] = x
            left >>= 1; right >>= 1
        for i in ids:
            self.node[i-1] = min(self.node[2*i-1], self.node[2*i])

    def query(self, l, r):
        self.propagates(*self._gindex(l, r))
        left = l + self._N; right = r + self._N
        ret = self.INF
        while left < right:
            if right & 1:
                right -= 1
                ret = min(ret, self.node[right-1])
            if left & 1:
                ret = min(ret, self.node[left-1])
                left += 1
            left >>= 1; right >>= 1
        return ret

nm = lambda: map(int, input().split())
n,q = nm()
S = LazySegTree(n)
for _ in range(q):
  v = list(nm())
  if v[0]:
    # print(S.node)
    # print(S.lazy)
    print(S.query(v[1], v[2]+1))
  else:
  	S.update(v[1], v[2]+1, v[3])

Submission status: Accepted

Solution code:

def func(x,y):
    return min(x,y)

class LazySegmentTree():
    def __init__(self, n):
        self.lv = (n-1).bit_length()
        self.n = 2 ** self.lv
        self.arr = [2**31-1] * (2*self.n-1)
        self.lazy = [None] * (2*self.n-1)

    #伝播区間
    def getidx(self, l, r):
        L = (l + self.n) >> 1
        R = (r + self.n) >> 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(self.lv):
            if rc <= i:
                yield R
            if L < R and lc <= i:
                yield L
            L >>= 1; R >>=1

    #伝播
    def propagate(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.arr[2*i-1] = self.lazy[2*i] = self.arr[2*i] = v
            self.lazy[i-1] = None

    #[l, r] をxで更新
    def update(self,l,r,x):
        #[l, r)に変更
        r+=1
        *ids, = self.getidx(l,r)
        self.propagate(*ids)

        L = self.n + l; R = self.n + r
        while L < R:
            if R & 1:
                R -=1
                self.lazy[R-1] = self.arr[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.arr[L-1] = x
                L += 1
            L >>= 1; R >>= 1

        for i in ids:
            self.arr[i-1] = func(self.arr[2*i-1], self.arr[2*i])

    #[l, r]のクエリに答える
    def query(self,l,r):
        #[l, r)に変更
        r+=1
        self.propagate(*self.getidx(l,r))
        L = self.n + l; R = self.n + r

        s = 2**31-1
        while L < R:
            if R & 1:
                R -=1
                s = func(s, self.arr[R-1])
            if L & 1:
                s = func(s, self.arr[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
sg=LazySegmentTree(n)
for _ in range(q):
    que=list(map(int,input().split()))
    if que[0]==0:
        y,l,r,x=que
        sg.update(l,r,x)
    else:
        y,l,r=que
        print(sg.query(l,r))

Submission status: Accepted

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


class LazySegmentTree():
    def __init__(self,
                 array,
                 ti,
                 ei,
                 f=lambda: None,
                 g=lambda: None,
                 h=lambda: None):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        ti : T
            identity element of T
        ei : E
            identity element of E
        f : func
            binary operation of the monoid
            T x T -> T
            T is dat
        g : func
            binary operation of the monoid
            T x E -> T
            T is dat, E is laz
        h : func
            binary operation of the monoid
            E x E -> T
            E is laz
        """
        self.f = f
        self.g = g
        self.h = h
        self.ti = ti
        self.ei = ei
        self.LV = LV = (len(array) - 1).bit_length()
        self.N0 = N0 = 2**LV
        self.data = data = [ti] * N0 + array + [ti] * (N0 - len(array))
        self.lazy = [ei] * (2 * N0)
        '''
        for i in range(N0 - 1, 0, -1):  # build
            data[i] = f(data[i << 1], data[i << 1 | 1])
        '''
        for i in range(N0 - 1, 0, -1):  # build
            data[i] = data[i << 1] if data[i << 1] < data[i << 1
                                                          | 1] else data[i << 1
                                                                         | 1]

    def gindex(self, l, r):
        LV = self.LV
        N0 = self.N0
        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()
        ret = []
        for i in range(LV):
            if rc <= i:
                ret += [R]
            if L < R and lc <= i:
                ret += [L]
            L >>= 1
            R >>= 1
        return ret

    def propagates(self, *ids):
        data = self.data
        lazy = self.lazy
        for i in reversed(ids):
            v = lazy[i - 1]
            if v is ei:
                continue
            '''
            data[2 * i - 1] = g(data[2 * i - 1], v)
            data[2 * i] = g(data[2 * i], v)
            lazy[2 * i - 1] = h(lazy[2 * i - 1], v)
            lazy[2 * i] = h(lazy[2 * i], v)
            '''
            data[2 * i - 1] = v
            data[2 * i] = v
            lazy[2 * i - 1] = v
            lazy[2 * i] = v

            lazy[i - 1] = ei

    def update(self, l, r, x):
        data = self.data
        lazy = self.lazy
        N0 = self.N0
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        L = N0 + l
        R = N0 + r
        while L < R:
            '''
            if R & 1:
                R -= 1
                lazy[R - 1] = h(lazy[R - 1], x)
                data[R - 1] = g(data[R - 1], x)
            if L & 1:
                lazy[L - 1] = h(lazy[L - 1], x)
                data[L - 1] = g(data[L - 1], x)
                L += 1
            '''
            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] = f(data[2 * i - 1], data[2 * i])
            '''
            data[i - 1] = data[
                2 * i - 1] if data[2 * i - 1] < data[2 * i] else data[2 * i]

    def query(self, l, r):
        data = self.data
        N0 = self.N0
        ti = self.ti
        self.propagates(*self.gindex(l, r))
        L = N0 + l
        R = N0 + r
        vl = vr = ti
        while L < R:
            '''
            if R & 1:
                R -= 1
                vr = f(data[R - 1], vr)
            if L & 1:
                vl = f(vl, data[L - 1])
                L += 1
            '''
            if R & 1:
                R -= 1
                vr = data[R - 1] if data[R - 1] < vr else vr
            if L & 1:
                vl = vl if vl < data[L - 1] else data[L - 1]
                L += 1
            L >>= 1
            R >>= 1
        '''
        return f(vl, vr)
        '''
        return vl if vl < vr else vr


I = sys.stdin.read()[:-1].split('\n')
N, Q = map(int, I[0].split())

ti = 2**31 - 1  #float('inf')
ei = None
#f = lambda tl, tr: tl if tl < tr else tr
#g = lambda t, e: t if e is ei else e
#h = lambda eo, en: eo if en is ei else en
LST = LazySegmentTree([ti] * N, ti, ei)
ans = []
for r in I[1:]:
    t, *cmd = map(int, r.split())
    if t:
        s, t = cmd
        ans.append(str(LST.query(s, t + 1)))
    else:
        s, t, x = cmd
        LST.update(s, t + 1, x)

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

Submission status: Accepted

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

N,Q=map(int,input().split())

seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
SEG=[(1<<31)-1]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化
LAZY=[None]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化


def indexes(L,R):
    INDLIST=[]

    R-=1
    
    L>>=1
    R>>=1

    while L!=R:
        if L>R:
            INDLIST.append(L)
            L>>=1
        else:
            INDLIST.append(R)
            R>>=1

    while L!=0:
        INDLIST.append(L)
        L>>=1

    return INDLIST
        

def updates(l,r,x): # 区間[l,r)をxに更新
        
    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
    
    while L!=R:
        if L > R:
            SEG[L]=x
            LAZY[L]=x
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            SEG[R]=x
            LAZY[R]=x
            R//=(R & (-R))

    for ind in UPIND:
        SEG[ind]=min(SEG[ind<<1],SEG[1+(ind<<1)])  
        
def getvalues(l,r): # 区間[l,r)に関するminを調べる

    L=l+seg_el
    R=r+seg_el

    L//=(L & (-L))
    R//=(R & (-R))

    UPIND=indexes(L,R)
    
    for ind in UPIND[::-1]:
        if LAZY[ind]!=None:
            LAZY[ind<<1]=LAZY[1+(ind<<1)]=SEG[ind<<1]=SEG[1+(ind<<1)]=LAZY[ind]
            LAZY[ind]=None
            
    ANS=1<<31

    while L!=R:
        if L > R:
            ANS=min(ANS , SEG[L])
            L+=1
            L//=(L & (-L))

        else:
            R-=1
            ANS=min(ANS , SEG[R])
            R//=(R & (-R))

    return ANS

ANS=[]

for _ in range(Q):
    query=list(map(int,input().split()))
    if query[0]==0:
        updates(query[1],query[2]+1,query[3])

    else:
        ANS.append(getvalues(query[1],query[2]+1))


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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 2 ** 31 - 1
MOD = 10 ** 9 + 7

class SegTreeLazy:
    """ 遅延評価セグメント木 """

    def __init__(self, N, func, intv):
        self.intv = intv
        self.func = func
        LV = (N-1).bit_length()
        self.N0 = 2**LV
        self.data = [intv]*(2*self.N0)
        self.lazy = [None]*(2*self.N0)

    # 伝搬される区間のインデックス(1-indexed)を全て列挙するgenerator
    def gindex(self, l, r):
        L = l + self.N0; R = r + self.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(self, *ids):
        # 1-indexedで単調増加のインデックスリスト
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.data[2*i-1] = self.lazy[2*i] = self.data[2*i] = v
            self.lazy[i-1] = None

    def update(self, l, r, x):
        """ 区間[l,r)の値をxに更新 """

        *ids, = self.gindex(l, r)
        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*ids)
        # 2. 区間[l,r)のdata, lazyの値を更新
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = x
                L += 1
            L >>= 1; R >>= 1
        # 3. 伝搬させた区間について、ボトムアップにdataの値を伝搬する
        for i in ids:
            self.data[i-1] = self.func(self.data[2*i-1], self.data[2*i])

    def query(self, l, r):
        """ 区間[l,r)の最小値を取得 """

        # 1. トップダウンにlazyの値を伝搬
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        # 2. 区間[l, r)の最小値を求める
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.func(s, self.data[R-1])
            if L & 1:
                s = self.func(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

N, Q = MAP()
stl = SegTreeLazy(N+1, min, INF)

ans = []
for i in range(Q):
    cmd, *arg = MAP()
    if cmd == 0:
        s, t, x = arg
        stl.update(s, t+1, x)
    else:
        s, t = arg
        ans.append(str(stl.query(s, t+1)))
print('\n'.join(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 2**31 - 1

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

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

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

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

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

n, q = map(int, input().split())
lst = LazySegmentTree(n)

for _ in range(q):
    que = list(map(int, input().split()))
    
    if que[0] == 0:
        s, t, x = que[1], que[2], que[3]
        lst.update(s, t+1, x)
    elif que[0] == 1:
        s, t = que[1], que[2]
        print(lst.query(s, t+1))

Submission status: Accepted

Solution code:
class SegmentTree(object):
    INIT = 2 ** 31 - 1
    DIVIDED = -1

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

    def set_range(self, l: int, h: int, v: int) -> None:
        def _set_range(r, i: int, j: int, vv: int) -> None:
            if (j < l or i > h):
                if vv != self.DIVIDED:
                    self.data[r] = vv
            elif (l <= i and j <= h):  # noqa: E741
                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: int, j: int) -> int:
        def _min(r, l: int, h: int) -> int:
            if (j < l or i > h):
                return self.INIT
            elif self.data[r] != self.DIVIDED:
                return self.data[r]
            else:
                mid = l + (h - l) // 2
                return min(_min(r * 2 + 1, l, mid),
                           _min(r * 2 + 2, mid + 1, h))

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


if __name__ == "__main__":
    n, q = map(lambda x: int(x), input().split())
    segtree = SegmentTree(n)

    for _ in range(q):
        com, *v = map(lambda x: int(x), input().split())
        if (0 == com):
            segtree.set_range(v[0], v[1], v[2])
        else:
            print(segtree.min(v[0], v[1]))

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
print = sys.stdout.write
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

class SegmentTree:
    def __init__(self,N,d):
        self.N0 = 2**(N-1).bit_length()
        self.node = [d]*(self.N0*2)
        self.lazy = [None]*(self.N0*2)

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

    def update(self,l,r,x): #iの値をxに更新
        *ids, = self.gindex(l, r)

        # トップダウンにlazyの値を伝搬
        self.propagates(*ids)

        # 区間[l, r)のnode, lazyの値を更新
        L = self.N0 + l
        R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.node[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.node[L-1] = x
                L += 1
            L >>= 1; R >>= 1

        # 伝搬させた区間について、ボトムアップにnodeの値を伝搬する
        for i in ids:
            self.node[i-1] = self.process(self.node[2*i-1], self.node[2*i])

    def query(self,l, r):
        # トップダウンにlazyの値を伝搬
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l
        R = self.N0 + r

        # 区間[l, r)の最小値を求める
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = self.process(s, self.node[R-1])
            if L & 1:
                s = self.process(s, self.node[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    def process(self,x,y): #x,yが子の時，親に返る値
        return min(x,y)

N,Q = inpl()
ST = SegmentTree(N,2**31-1)
ans = []
for _ in range(Q):
    c,*arg = inpl()
    if c:
        s,t = arg
        ans.append(str(ST.query(s,t+1)))
    else:
        s,t,x = arg
        ST.update(s,t+1,x)

print('\n'.join(ans))
print('\n')