[
segment tree
]
CodeForces Segment Trees, Part 2, 2.3
Problem statement
https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/C
Solution
This segment tree will support two operations:
- Apply
OR
withv
for all elements on[l, r)
- Add
AND
for all elements on[l, r)
Complexity
Standart compexities for segment tree.
Code
class SegmentTree:
def __init__(self, n, op_modify, op_sum, ZERO):
self.size = 1
while self.size < n:
self.size *= 2
self.T = [0] * (2 * self.size - 1) # to multiply
self.L = [0] * (2 * self.size - 1) # current sum
self.op_modify = op_modify
self.op_sum = op_sum
self.ZERO = ZERO
def _build(self, x, lx, rx):
if rx - lx == 1:
self.T[x] = 0
self.L[x] = 0
else:
mx = (lx + rx)//2
self._build(2*x+1, lx, mx)
self._build(2*x+2, mx, rx)
self.L[x] = 0
self.T[x] = self.op_sum(self.T[2*x+1], self.T[2*x+2])
def build(self):
self._build(0, 0, self.size)
def _mult(self, l, r, v, x, lx, rx):
if l >= rx or lx >= r:
return
if lx >= l and rx <= r:
self.T[x] = self.op_modify(self.T[x], v)
self.L[x] = self.op_modify(self.L[x], v)
return
mx = (lx + rx)//2
self._mult(l, r, v, 2*x+1, lx, mx)
self._mult(l, r, v, 2*x+2, mx, rx)
self.T[x] = self.op_modify(self.op_sum(self.T[2*x+1], self.T[2*x+2]), self.L[x])
def mult(self, l, r, v):
return self._mult(l, r, v, 0, 0, self.size)
def _sum(self, l, r, x, lx, rx):
if l >= rx or lx >= r:
return self.ZERO
if lx >= l and rx <= r:
return self.T[x]
mx = (lx + rx) // 2
m1 = self._sum(l, r, 2 * x + 1, lx, mx)
m2 = self._sum(l, r, 2 * x + 2, mx, rx)
return self.op_modify(self.op_sum(m1, m2), self.L[x])
def sum(self, l, r):
return self._sum(l, r, 0, 0, self.size)
# import io, os, sys
# input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
if __name__ == '__main__':
n, m = [int(i) for i in input().split()]
MOD = 10**9 + 7
STree = SegmentTree(n, lambda a, b: a|b, lambda a, b: a&b, (1<<31) - 1)
STree.build()
for i in range(m):
t = [int(i) for i in input().split()]
if t[0] == 1:
STree.mult(t[1], t[2], t[3])
else:
print(STree.sum(t[1], t[2]))