Problem statement

https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/E

Solution

This segment tree will support two operations:

  1. Apply min or max with value h on interval [r, v).
  2. Find min of elements in interval [r, l).

For our lazy updates we will keep pairs [h_max, h_min], where operation max was applied with h_max and min with h_min. It can be proven that we always can keep pairs where h_max <= h_min.

Complexity

Standart compexities for segment tree.

Code

class SegmentTree:
    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.ZERO = float("inf")  # neutral element, for min it is +inf
        self.NO_OPERATION = (1, 0)  # in correct values h[0] always <= h[1]
        self.T = [0] * (2 * self.size - 1)  #   minimums
        self.L = [self.NO_OPERATION] * (2 * self.size - 1)  # lazy updates

    def op_modify_L(self, h0, h1):
        if h0 == self.NO_OPERATION: return h1
        if h1[1] <= h0[0]: return h1[1], h1[1]
        if h0[1] <= h1[0]: return h1[0], h1[0]
        if h1[0] <= h0[0] and h0[1] <= h1[1]: return h0
        if h0[0] <= h1[0] and h1[1] <= h0[1]: return h1
        if h1[0] <= h0[0]: return h0[0], h1[1]
        return h1[0], h0[1]

    def op_modify_T(self, x, h):
        return max(min(x, h[1]), h[0])

    def op_query(self, a, b):
        return min(a, b)

    def propagate(self, x, lx, rx):
        if self.L[x] == self.NO_OPERATION or rx - lx == 1:
            return
        mx = (lx + rx)//2
        self.L[2 * x + 1] = self.op_modify_L(self.L[2 * x + 1], self.L[x])
        self.T[2 * x + 1] = self.op_modify_T(self.T[2 * x + 1], self.L[x])
        self.L[2 * x + 2] = self.op_modify_L(self.L[2 * x + 2], self.L[x])
        self.T[2 * x + 2] = self.op_modify_T(self.T[2 * x + 2], self.L[x])
        self.L[x] = self.NO_OPERATION

    def _update(self, l, r, v, x, lx, rx):
        self.propagate(x, lx, rx)
        if l >= rx or lx >= r:
            return
        if lx >= l and rx <= r:
            self.L[x] = self.op_modify_L(self.L[x], v)
            self.T[x] = self.op_modify_T(self.T[x], v)
            return
        mx = (lx + rx)//2
        self._update(l, r, v, 2*x+1, lx, mx)
        self._update(l, r, v, 2*x+2, mx, rx)
        self.T[x] = self.op_query(self.T[2*x+1], self.T[2*x+2])

    def update(self, l, r, v):
        return self._update(l, r, v, 0, 0, self.size)

    def _get(self, i, x, lx, rx):
        self.propagate(x, lx, rx)
        if rx - lx == 1:
            return self.T[x]
        mx = (lx + rx) // 2
        if i < mx:
            return self._get(i, 2 * x + 1, lx, mx)
        else:
            return self._get(i, 2 * x + 2, mx, rx)

    def get(self, i):
        return self._get(i, 0, 0, self.size)

if __name__ == '__main__':
    n, k = [int(i) for i in input().split()]
    STree = SegmentTree(n)

    for i in range(k):
        t = [int(i) for i in input().split()]
        if t[0] == 2:
            STree.update(t[1], t[2] + 1, (-float("inf"), t[3]))
        else:
            STree.update(t[1], t[2] + 1, (t[3], float("inf")))

    print("\n".join([str(STree.get(i)) for i in range(n)]))

Code 2

Here is iterative version, which is fast enough to get AC.

class SegmentTree:
    def __init__(self, N):
        self.N = N
        self.H = 1
        while 1 << self.H < N:
            self.H += 1
        self.size = 1 << self.H

        self.ZERO = float("inf")  # neutral element, for min it is +inf
        self.NO_OPERATION = (1, 0)  # in correct values h[0] always <= h[1]
        self.T = [0] * (2 * self.size - 1)  # minimums
        self.L = [self.NO_OPERATION] * (2 * self.size - 1)  # lazy updates

    def op_modify_L(self, h0, h1):
        if h0 == self.NO_OPERATION: return h1
        if h1 == self.NO_OPERATION: return h0
        if h1[1] <= h0[0]: return h1[1], h1[1]
        if h0[1] <= h1[0]: return h1[0], h1[0]
        if h1[0] <= h0[0] and h0[1] <= h1[1]: return h0
        if h0[0] <= h1[0] and h1[1] <= h0[1]: return h1
        if h1[0] <= h0[0]: return h0[0], h1[1]
        return h1[0], h0[1]

    def op_modify_T(self, x, h):
        if h == self.NO_OPERATION: return x
        return max(min(x, h[1]), h[0])

    def op_query(self, a, b):
        return min(a, b)

    def _apply(self, x, val):
        self.T[x] = self.op_modify_T(self.T[x], val)
        self.L[x] = self.op_modify_L(self.L[x], val)

    def _pull(self, x):
        while x > 1:
            x //= 2
            self.T[x] = self.op_query(self.T[x*2], self.T[x*2 + 1])
            self.T[x] = self.op_modify_T(self.T[x], self.L[x])

    def _push(self, x):
        for h in range(self.H, 0, -1):
            y = x >> h
            if self.L[y] != self.NO_OPERATION:
                self._apply(y * 2, self.L[y])
                self._apply(y * 2 + 1, self.L[y])
                self.L[y] = self.NO_OPERATION

    def update(self, l, r, h):
        l += self.N
        r += self.N
        self._push(l)
        self._push(r)
        l0, r0 = l, r
        while l <= r:
            if l & 1:
                self._apply(l, h)
                l += 1
            if r & 1 == 0:
                self._apply(r, h)
                r -= 1
            l //= 2; r //= 2
        self._pull(l0)
        self._pull(r0)

    def query(self, l, r):
        l += self.N
        r += self.N
        self._push(l); self._push(r)
        ans = self.ZERO
        while l <= r:
            if l & 1:
                ans = self.op_query(ans, self.T[l])
                l += 1
            if r & 1 == 0:
                ans = self.op_query(ans, self.T[r])
                r -= 1
            l //= 2; r //= 2
        return ans

if __name__ == '__main__':
    n, k = [int(i) for i in input().split()]
    STree = SegmentTree(n)
    sh = 0

    for i in range(k):
        t = [int(i) for i in input().split()]
        if t[0] == 2:
            STree.update(t[1]+sh, t[2]+sh, (-float("inf"), t[3]))
        else:
            STree.update(t[1]+sh, t[2]+sh, (t[3], float("inf")))

    print("\n".join([str(STree.query(i, i)) for i in range(n)]))