[
segment tree
]
CodeForces Segment Trees, Part 2, 1.3
Problem statement
https://codeforces.com/edu/course/2/lesson/5/1/practice/contest/279634/problem/C
Solution
This segment tree will support two operations:
- For all elements in range
[r, l)
applyai = v
. This operation is associativef(a, x) = a
, but not commutative, so we need to use push technique here. Also for each node we need to have information if we need to apply operation or not, because0
is not good choice. - Find element at index
i
.
Complexity
Standart compexities for segment tree.
Code
class SegmentTree:
def __init__(self, n, arr, NO_OPERATION):
self.size = 1
while self.size < n:
self.size *= 2
self.T = [0] * (2 * self.size - 1)
self.NO_OP = NO_OPERATION
self.arr = arr
def propagate(self, x, lx, rx):
if self.T[x] == self.NO_OP or rx - lx == 1:
return
self.T[2*x+1] = self.T[x]
self.T[2*x+2] = self.T[x]
self.T[x] = self.NO_OP
def _modify(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.T[x] = v
return
mx = (lx + rx)//2
self._modify(l, r, v, 2*x+1, lx, mx)
self._modify(l, r, v, 2*x+2, mx, rx)
def modify(self, l, r, v):
return self._modify(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, m = [int(i) for i in input().split()]
STree = SegmentTree(n, [0]*n, -float("inf"))
for i in range(m):
t = [int(i) for i in input().split()]
if t[0] == 1:
STree.modify(t[1], t[2], t[3])
else:
print(STree.get(t[1]))