[
segment tree
]
CodeForces Segment Trees, Part 2, 4.6
Problem statement
https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/F
Solution 1
This segment tree will support two operations:
- Set values in range
[l, r)
as arithmetic progression with parametersa, d
or add valuev
to value in this range. - Find maximum in range
[l, r)
In lazy updates we will keep pair (d, v)
where d
means that we need to set values to 0, d, 2d, ...
and v
means that after we add v
to all values. If d = -inf
, it means that we skip the first step.
Complexity
Standart compexities for segment tree. However it will give TLE here on python.
Code
from collections import defaultdict
class SegmentTree:
def __init__(self, n):
self.size = 1
while self.size < n:
self.size *= 2
self.ZERO = -float("inf") # neutral element, for ma it is +inf
self.NO_OPERATION = (float("inf"), 0)
self.T = defaultdict(int)
self.L = defaultdict(lambda: self.NO_OPERATION)
def op_query(self, a, b):
return max(a, b)
def op_modify_L(self, h0, h1, len_):
d, v = h1
if d != -float("inf"):
return d, v + d * len_
else d == -float("inf"):
if h0 != self.NO_OPERATION:
return h0[0], h0[1] + v
else:
return h1
def op_modify_T(self, x, h0, len_):
d, v = h0
if d != -float("inf"):
return v + d * len_
else:
return x + v
def propagate(self, x, lx, rx):
if self.L[x] == self.NO_OPERATION or rx - lx == 1:
return
mx = (lx + rx) // 2
d, v = self.L[x]
self.L[2 * x + 1] = self.op_modify_L(self.L[2 * x + 1], self.L[x], 0)
self.L[2 * x + 2] = self.op_modify_L(self.L[2 * x + 2], self.L[x], mx - lx)
l1 = mx - lx - 1 if d > 0 else 0
l2 = rx - lx - 1 if d > 0 else mx - lx
self.T[2 * x + 1] = self.op_modify_T(self.T[2 * x + 1], self.L[x], l1)
self.T[2 * x + 2] = self.op_modify_T(self.T[2 * x + 2], self.L[x], l2)
self.L[x] = self.NO_OPERATION
def _update(self, l, r, d, 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], (d, v), lx - l)
l1 = rx - l - 1 if d > 0 else lx - l
self.T[x] = self.op_modify_T(self.T[x], (d, v), l1)
return
mx = (lx + rx) // 2
self._update(l, r, d, v, 2 * x + 1, lx, mx)
self._update(l, r, d, 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, d, v):
return self._update(l, r, d, v, 0, 0, self.size)
def first_above_(self, v, x, lx, rx):
self.propagate(x, lx, rx)
if self.T[x] < v:
return -1
if rx - lx == 1:
return lx
mx = (lx + rx) // 2
res = self.first_above_(v, 2 * x + 1, lx, mx)
if res == -1:
res = self.first_above_(v, 2 * x + 2, mx, rx)
return res
def first_above(self, v):
return self.first_above_(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 = int(input())
STree = SegmentTree(n + 1)
while True:
t = input().split()
if t[0] == "I":
l, r, d = int(t[1]), int(t[2]), int(t[3])
v1, v2 = STree.get(l - 1), STree.get(r)
STree.update(l - 1, r + 1, d, v1)
v3 = STree.get(r)
STree.update(r + 1, n + 1, -float("inf"), v3 - v2)
elif t[0] == "Q":
x = STree.first_above(int(t[1]) + 1)
if x == -1:
print(n)
else:
print(x - 1)
else:
break
Solution 2
This solution is based on oficial solution of this problem (from IOI 2005): https://dmoj.ca/problem/ioi05p3/editorial, the second optimized solution. Idea is similar, but we can make smarter updates.
Complexity
Standart compexities for segment tree.
Code
class SegmentTree:
def __init__(self, n):
self.t = [0] * (n * 4)
self.p = [0] * (n * 4)
self.lz = [MINF] * (n * 4)
def push(self, x, lx, rx):
if self.lz[x] == MINF: return
self.t[x] = self.lz[x] * (c[rx] - c[lx])
self.p[x] = max(0, self.t[x])
if lx + 1 != rx:
self.lz[2*x] = self.lz[2*x+1] = self.lz[x]
self.lz[x] = MINF
def upd(self, l, r, val, x, lx, rx):
self.push(x, lx, rx)
if lx >= r or rx <= l: return
if lx >= l and rx <= r:
self.lz[x] = val
self.push(x, lx, rx)
return
mx = (lx + rx)//2
self.upd(l, r, val, x*2, lx, mx)
self.upd(l, r, val, x*2+1, mx, rx)
self.t[x] = self.t[x*2] + self.t[x*2+1]
self.p[x] = max(self.p[x*2], self.t[x*2] + self.p[x*2+1])
def query(self, val, x, lx, rx):
self.push(x, lx, rx)
if lx + 1 == rx:
d = self.t[x]//(c[rx] - c[lx])
return c[lx] - 1 + val // d if self.p[x] > val else c[rx] - 1
mx = (lx + rx)//2
self.push(x*2, lx, mx)
self.push(x*2 + 1, mx, rx)
if self.p[x*2] > val:
return self.query(val, x*2, lx, mx)
else:
return self.query(val - self.t[x*2], x*2+1, mx, rx)
N = int(input())
c, q = [N + 1], []
while True:
l = input().split()
if l[0] == "Q":
q += [[2, int(l[1]), 0, 0]]
elif l[0] == "I":
q += [[1, int(l[1]), int(l[2]), int(l[3])]]
c += [q[-1][1], q[-1][2] + 1]
else:
break
c = sorted(set(c))
d = {x: i for i, x in enumerate(c)}
M = len(c) - 1
MINF = -float("inf")
STree = SegmentTree(M)
for t, l, r, v in q:
if t == 1:
STree.upd(d[l], d[r + 1], v, 1, 0, M)
else:
print(STree.query(l, 1, 0, M))