#yukicoder 2662 Installing Cell Towers #Lazy Segment Tree class LazySegmentTree: #適応条件: 値X, 遅延Lが (1)モノイド (2)単位元 (3)結合法則 (4)右作用可能 def __init__(self, N, e_node, e_lazy, node_f, lazy_f, ref_f): self._N = N; self._height = (N - 1).bit_length(); self._size = 1 << self._height; self._e_node = e_node; self._e_lazy = e_lazy; self._node_f = node_f; self._lazy_f = lazy_f; self._ref_f = ref_f; self._node = [e_node] * 2 * self._size; self._lazy = [e_lazy] * 2 * self._size def build(self, array): assert len(array) == self._N, 'array too large' for i, v in enumerate(array, start = self._size): self._node[i] = v for i in range(self._size - 1, 0, -1): self._node[i] = self._node_f(self._node[i << 1], self._node[i << 1 | 1]) def _ref_lazy(self, index): return self._ref_f(self._node[index], self._lazy[index]) def _propagate_from_top(self, index): #遅延評価・子へのpush 唯一遅延をresetする関数 index += self._size for h in range(self._height, 0, -1): i = index >> h if self._lazy[i] != self._e_lazy: Lt, Rt = i << 1, i << 1 | 1; self._lazy[Lt] = self._lazy_f(self._lazy[Lt], self._lazy[i]); self._lazy[Rt] = self._lazy_f(self._lazy[Rt], self._lazy[i]); self._node[i] = self._ref_lazy(i); self._lazy[i] = self._e_lazy def _update_from_bottom(self, index): i = (index + self._size) >> 1 while i > 0: self._node[i] = self._node_f(self._ref_lazy(i << 1), self._ref_lazy(i << 1 | 1)); i >>= 1 def update(self, Lt, Rt, value): #半開区間[Lt, Rt)に値valueを作用 if Lt == Rt: return self._propagate_from_top(Lt); self._propagate_from_top(Rt - 1); Li, Ri = Lt + self._size, Rt + self._size while Li < Ri: if Li & 1: self._lazy[Li] = self._lazy_f(self._lazy[Li], value); Li += 1 if Ri & 1: Ri -= 1; self._lazy[Ri] = self._lazy_f(self._lazy[Ri], value) Li >>= 1; Ri >>= 1 self._update_from_bottom(Lt); self._update_from_bottom(Rt - 1) def fold(self, Lt, Rt): #半開区間[Lt, Rt)の作用値を取得 if Lt == Rt: return self._e_node self._propagate_from_top(Lt); self._propagate_from_top(Rt - 1); Lt, Rt = Lt + self._size, Rt + self._size; vL, vR = self._e_node, self._e_node while Lt < Rt: if Lt & 1: vL = self._node_f(vL, self._ref_lazy(Lt)); Lt += 1 if Rt & 1: Rt -= 1; vR = self._node_f(self._ref_lazy(Rt), vR) Lt >>= 1; Rt >>= 1 return self._node_f(vL, vR) #入力受取 N, M = map(int, input().split()) P, Q = [], [] for _ in range(M): p, q = map(int, input().split()) P.append(p) Q.append(q) #区間加算のLazy SegTreeを定義 区間sumなのでnode値は(値, 該当ノード数) def node_f(node1, node2): return (node1[0] + node2[0], node1[1] + node2[1]) def lazy_f(lazy1, lazy2): return lazy1 + lazy2 def ref_f(node, lazy): return (node[0] + node[1] * lazy, node[1]) LST = LazySegmentTree(N + 2, (0, 0), 0, node_f, lazy_f, ref_f) LST.build([(0, 0)] + [(0, 1) for _ in range(N + 1)]) #imos法を応用した区間加算 for Pi, Qi in zip(P, Q): #1. B[Pi - Qi + 1, Pi) に+1 B[Pi]に-(Qi - 1) #2. B[Pi]に+Qi, B[Pi + 1, Pi + Qi + 1) に-1 の処理をしたい #区間端が超過するので注意して計算 Lt = max(1, Pi - Qi) Lt_add = max(0, Lt + (Qi - Pi)) Rt = min(N, Pi + Qi) #右端は適当でよい(答えには影響しないため) LST.update(Lt, Lt + 1, + Lt_add) LST.update(Lt + 1, Pi + 1, + 1) LST.update(Pi + 1, Rt + 1, - 1) #答えを出力 ans = [LST.fold(0, i + 1)[0] for i in range(N + 1)] print(*ans[1:]) ''' ここからデバッグ用 ''' #愚直解 def brute(N, M, P, Q): A = [0] * (N + 1) for p, q in zip(P, Q): for j in range(1, N + 1): A[j] += max(0, q - abs(p - j)) return A def solve(N, M, P, Q): def node_f(node1, node2): return (node1[0] + node2[0], node1[1] + node2[1]) def lazy_f(lazy1, lazy2): return lazy1 + lazy2 def ref_f(node, lazy): return (node[0] + node[1] * lazy, node[1]) LST = LazySegmentTree(N + 2, (0, 0), 0, node_f, lazy_f, ref_f) LST.build([(0, 0)] + [(0, 1) for _ in range(N + 1)]) #imos法を応用した区間加算 for Pi, Qi in zip(P, Q): Lt = max(1, Pi - Qi) Lt_add = max(0, Lt + (Qi - Pi)) Rt = min(N, Pi + Qi) LST.update(Lt, Lt + 1, + Lt_add) LST.update(Lt + 1, Pi + 1, + 1) LST.update(Pi + 1, Rt + 1, - 1) #答えを出力 ans = [LST.fold(0, i + 1)[0] for i in range(N + 1)] return ans #random test import random def make_test(N = 10, M = 10): P = [random.randint(1, N) for _ in range(M)] Q = [random.randint(1, 10 ** 9) for _ in range(M)] return N, M, P, Q def random_test(time): for t in range(1, time + 1): N, M, P, Q = make_test() if brute(N, M, P, Q) != solve(N, M, P, Q): print('WA in test', t) return N, M, P, Q print('AC') return [None] * 4