雑多（未確認）
| 投稿者 | sig |
|---|---|
| 言語 | PyPy3 |
| 更新日時 (JST) | 2026-10-17 05:54:34 |
| サイズ | 36,813 Byte |
| 参照URL | |
日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。
"""Segment Tree Beats for Python.
Supports the following operations on an integer (or comparable numeric) array:
range_chmin(l, r, x) : A[i] = min(A[i], x) for l <= i < r
range_chmax(l, r, x) : A[i] = max(A[i], x) for l <= i < r
range_add(l, r, x) : A[i] += x for l <= i < r
range_set(l, r, x) : A[i] = x for l <= i < r
range_sum(l, r) : sum(A[l:r])
range_max(l, r) : max(A[l:r])
range_min(l, r) : min(A[l:r])
All ranges are half-open: [l, r), as in Python slices and AtCoder Library.
Notes
-----
* Empty updates and range_sum(l, l) are allowed.
* range_min / range_max require a non-empty range and raise ValueError otherwise.
* This is a Segment Tree Beats implementation, not a plain lazy segment tree.
The chmin/chmax operations use the second maximum/minimum and their counts to
decide whether a whole node can be updated without descending to its children.
* Updates are amortized, not guaranteed O(log N) in the worst case per call.
Example
-------
seg = SegmentTreeBeats([2, 5, 7, 9, 12])
seg.range_chmin(1, 5, 8) # [2, 5, 7, 8, 8]
seg.range_add(0, 2, 3) # [5, 8, 7, 8, 8]
assert seg.range_sum(0, 5) == 36
assert seg.range_max(0, 5) == 8
assert seg.to_list() == [5, 8, 7, 8, 8]
"""
from __future__ import annotations
from math import inf
from typing import Iterable, List, Optional, TypeVar
T = TypeVar("T", int, float)
class SegmentTreeBeats:
"""Range chmin/chmax/add/set and range sum/min/max queries."""
__slots__ = (
"n", "_length", "_sum", "_max1", "_max2", "_max_count",
"_min1", "_min2", "_min_count", "_lazy_add", "_lazy_set",
)
def __init__(self, values: Iterable[T]):
a = list(values)
self.n = len(a)
size = max(1, 4 * self.n)
self._length: List[int] = [0] * size
self._sum: List[T] = [0] * size # type: ignore[list-item]
self._max1 = [-inf] * size
self._max2 = [-inf] * size
self._max_count = [0] * size
self._min1 = [inf] * size
self._min2 = [inf] * size
self._min_count = [0] * size
self._lazy_add: List[T] = [0] * size # type: ignore[list-item]
self._lazy_set: List[Optional[T]] = [None] * size
if self.n:
self._build(1, 0, self.n, a)
# ---------- Construction and aggregate maintenance ----------
def _build(self, k: int, left: int, right: int, a: List[T]) -> None:
self._length[k] = right - left
if right - left == 1:
v = a[left]
self._sum[k] = v
self._max1[k] = self._min1[k] = v
self._max2[k] = -inf
self._min2[k] = inf
self._max_count[k] = self._min_count[k] = 1
return
mid = (left + right) // 2
self._build(k * 2, left, mid, a)
self._build(k * 2 + 1, mid, right, a)
self._pull(k)
def _pull(self, k: int) -> None:
lc, rc = k * 2, k * 2 + 1
self._sum[k] = self._sum[lc] + self._sum[rc]
lmax, rmax = self._max1[lc], self._max1[rc]
if lmax > rmax:
self._max1[k] = lmax
self._max_count[k] = self._max_count[lc]
self._max2[k] = max(self._max2[lc], rmax)
elif lmax < rmax:
self._max1[k] = rmax
self._max_count[k] = self._max_count[rc]
self._max2[k] = max(lmax, self._max2[rc])
else:
self._max1[k] = lmax
self._max_count[k] = self._max_count[lc] + self._max_count[rc]
self._max2[k] = max(self._max2[lc], self._max2[rc])
lmin, rmin = self._min1[lc], self._min1[rc]
if lmin < rmin:
self._min1[k] = lmin
self._min_count[k] = self._min_count[lc]
self._min2[k] = min(self._min2[lc], rmin)
elif lmin > rmin:
self._min1[k] = rmin
self._min_count[k] = self._min_count[rc]
self._min2[k] = min(lmin, self._min2[rc])
else:
self._min1[k] = lmin
self._min_count[k] = self._min_count[lc] + self._min_count[rc]
self._min2[k] = min(self._min2[lc], self._min2[rc])
# ---------- Applying operations directly to a node ----------
def _apply_set(self, k: int, x: T) -> None:
length = self._length[k]
self._sum[k] = x * length
self._max1[k] = self._min1[k] = x
self._max2[k] = -inf
self._min2[k] = inf
self._max_count[k] = self._min_count[k] = length
self._lazy_set[k] = x
self._lazy_add[k] = 0 # type: ignore[assignment]
def _apply_add(self, k: int, x: T) -> None:
self._sum[k] += x * self._length[k]
self._max1[k] += x
self._min1[k] += x
# +/- infinity sentinels remain +/- infinity after addition.
self._max2[k] += x
self._min2[k] += x
if self._lazy_set[k] is not None:
self._lazy_set[k] += x # type: ignore[operator]
else:
self._lazy_add[k] += x
def _apply_chmin(self, k: int, x: T) -> None:
"""Apply chmin when max2 < x < max1 (or max1 <= x)."""
old_max = self._max1[k]
if old_max <= x:
return
# Caller/push guarantees that the second maximum is strictly below x.
if not self._max2[k] < x:
raise AssertionError("invalid Beats chmin application: max2 >= x")
self._sum[k] -= (old_max - x) * self._max_count[k]
if self._min1[k] == old_max:
self._min1[k] = x
elif self._min2[k] == old_max:
self._min2[k] = x
self._max1[k] = x
def _apply_chmax(self, k: int, x: T) -> None:
"""Apply chmax when min1 < x < min2 (or min1 >= x)."""
old_min = self._min1[k]
if old_min >= x:
return
# Caller/push guarantees that the second minimum is strictly above x.
if not x < self._min2[k]:
raise AssertionError("invalid Beats chmax application: min2 <= x")
self._sum[k] += (x - old_min) * self._min_count[k]
if self._max1[k] == old_min:
self._max1[k] = x
elif self._max2[k] == old_min:
self._max2[k] = x
self._min1[k] = x
# ---------- Lazy propagation ----------
def _push(self, k: int) -> None:
if self._length[k] <= 1:
return
lc, rc = k * 2, k * 2 + 1
value = self._lazy_set[k]
if value is not None:
self._apply_set(lc, value)
self._apply_set(rc, value)
self._lazy_set[k] = None
add = self._lazy_add[k]
if add != 0:
self._apply_add(lc, add)
self._apply_add(rc, add)
self._lazy_add[k] = 0 # type: ignore[assignment]
# Propagate the parent's implicit upper/lower bounds to each child.
parent_max = self._max1[k]
parent_min = self._min1[k]
if self._max1[lc] > parent_max:
self._apply_chmin(lc, parent_max)
if self._min1[lc] < parent_min:
self._apply_chmax(lc, parent_min)
if self._max1[rc] > parent_max:
self._apply_chmin(rc, parent_max)
if self._min1[rc] < parent_min:
self._apply_chmax(rc, parent_min)
# ---------- Range updates ----------
def range_chmin(self, l: int, r: int, x: T) -> None:
"""Set every A[i] in [l, r) to min(A[i], x)."""
self._check_range(l, r)
if l < r and self.n:
self._range_chmin(1, 0, self.n, l, r, x)
def _range_chmin(self, k: int, nl: int, nr: int, ql: int, qr: int, x: T) -> None:
if qr <= nl or nr <= ql or self._max1[k] <= x:
return
if ql <= nl and nr <= qr and self._max2[k] < x:
self._apply_chmin(k, x)
return
self._push(k)
mid = (nl + nr) // 2
self._range_chmin(k * 2, nl, mid, ql, qr, x)
self._range_chmin(k * 2 + 1, mid, nr, ql, qr, x)
self._pull(k)
def range_chmax(self, l: int, r: int, x: T) -> None:
"""Set every A[i] in [l, r) to max(A[i], x)."""
self._check_range(l, r)
if l < r and self.n:
self._range_chmax(1, 0, self.n, l, r, x)
def _range_chmax(self, k: int, nl: int, nr: int, ql: int, qr: int, x: T) -> None:
if qr <= nl or nr <= ql or self._min1[k] >= x:
return
if ql <= nl and nr <= qr and x < self._min2[k]:
self._apply_chmax(k, x)
return
self._push(k)
mid = (nl + nr) // 2
self._range_chmax(k * 2, nl, mid, ql, qr, x)
self._range_chmax(k * 2 + 1, mid, nr, ql, qr, x)
self._pull(k)
def range_add(self, l: int, r: int, x: T) -> None:
"""Add x to every A[i] in [l, r)."""
self._check_range(l, r)
if l < r and self.n:
self._range_add(1, 0, self.n, l, r, x)
def _range_add(self, k: int, nl: int, nr: int, ql: int, qr: int, x: T) -> None:
if qr <= nl or nr <= ql:
return
if ql <= nl and nr <= qr:
self._apply_add(k, x)
return
self._push(k)
mid = (nl + nr) // 2
self._range_add(k * 2, nl, mid, ql, qr, x)
self._range_add(k * 2 + 1, mid, nr, ql, qr, x)
self._pull(k)
def range_set(self, l: int, r: int, x: T) -> None:
"""Assign x to every A[i] in [l, r)."""
self._check_range(l, r)
if l < r and self.n:
self._range_set(1, 0, self.n, l, r, x)
def _range_set(self, k: int, nl: int, nr: int, ql: int, qr: int, x: T) -> None:
if qr <= nl or nr <= ql:
return
if ql <= nl and nr <= qr:
self._apply_set(k, x)
return
self._push(k)
mid = (nl + nr) // 2
self._range_set(k * 2, nl, mid, ql, qr, x)
self._range_set(k * 2 + 1, mid, nr, ql, qr, x)
self._pull(k)
# ---------- Range queries ----------
def range_sum(self, l: int, r: int):
"""Return sum(A[l:r]); an empty range has sum 0."""
self._check_range(l, r)
if l == r or self.n == 0:
return 0
return self._range_sum(1, 0, self.n, l, r)
def _range_sum(self, k: int, nl: int, nr: int, ql: int, qr: int):
if qr <= nl or nr <= ql:
return 0
if ql <= nl and nr <= qr:
return self._sum[k]
self._push(k)
mid = (nl + nr) // 2
return self._range_sum(k * 2, nl, mid, ql, qr) + self._range_sum(
k * 2 + 1, mid, nr, ql, qr
)
def range_max(self, l: int, r: int):
"""Return max(A[l:r]); raises ValueError for an empty range."""
self._check_range(l, r)
if l == r:
raise ValueError("range_max requires a non-empty range")
return self._range_max(1, 0, self.n, l, r)
def _range_max(self, k: int, nl: int, nr: int, ql: int, qr: int):
if qr <= nl or nr <= ql:
return -inf
if ql <= nl and nr <= qr:
return self._max1[k]
self._push(k)
mid = (nl + nr) // 2
return max(
self._range_max(k * 2, nl, mid, ql, qr),
self._range_max(k * 2 + 1, mid, nr, ql, qr),
)
def range_min(self, l: int, r: int):
"""Return min(A[l:r]); raises ValueError for an empty range."""
self._check_range(l, r)
if l == r:
raise ValueError("range_min requires a non-empty range")
return self._range_min(1, 0, self.n, l, r)
def _range_min(self, k: int, nl: int, nr: int, ql: int, qr: int):
if qr <= nl or nr <= ql:
return inf
if ql <= nl and nr <= qr:
return self._min1[k]
self._push(k)
mid = (nl + nr) // 2
return min(
self._range_min(k * 2, nl, mid, ql, qr),
self._range_min(k * 2 + 1, mid, nr, ql, qr),
)
# ---------- Convenience methods ----------
def all_sum(self):
"""Return the sum of the whole array (0 for an empty tree)."""
return self._sum[1] if self.n else 0
def all_max(self):
"""Return the maximum of the whole array; raises ValueError if empty."""
if not self.n:
raise ValueError("all_max requires a non-empty tree")
return self._max1[1]
def all_min(self):
"""Return the minimum of the whole array; raises ValueError if empty."""
if not self.n:
raise ValueError("all_min requires a non-empty tree")
return self._min1[1]
def __getitem__(self, i: int):
"""Return A[i]."""
if not 0 <= i < self.n:
raise IndexError("index out of range")
return self.range_max(i, i + 1)
def __len__(self) -> int:
return self.n
def to_list(self) -> List:
"""Materialize and return the current array in O(N) time."""
if not self.n:
return []
result = [None] * self.n
def dfs(k: int, left: int, right: int) -> None:
if right - left == 1:
result[left] = self._max1[k]
return
self._push(k)
mid = (left + right) // 2
dfs(k * 2, left, mid)
dfs(k * 2 + 1, mid, right)
dfs(1, 0, self.n)
return result
def _check_range(self, l: int, r: int) -> None:
if not (0 <= l <= r <= self.n):
raise ValueError(f"invalid range [{l}, {r}) for n={self.n}")
if __name__ == "__main__":
# Small smoke test. Run `python segment_tree_beats.py` to check the module.
seg = SegmentTreeBeats([2, 5, 7, 9, 12])
seg.range_chmin(1, 5, 8)
assert seg.to_list() == [2, 5, 7, 8, 8]
seg.range_add(0, 2, 3)
assert seg.to_list() == [5, 8, 7, 8, 8]
assert seg.range_sum(0, 5) == 36
assert seg.range_max(0, 5) == 8
assert seg.range_min(0, 5) == 5
seg.range_chmax(0, 4, 7)
assert seg.to_list() == [7, 8, 7, 8, 8]
seg.range_set(1, 4, -2)
assert seg.to_list() == [7, -2, -2, -2, 8]
print("SegmentTreeBeats smoke test: OK")
"""Wavelet Matrix for static range-frequency / order-statistics queries.
Values may be arbitrary comparable integers; values are coordinate-compressed.
Intervals are half-open [l, r). Complexity: O(log sigma) per query.
"""
from bisect import bisect_left
from array import array
class WaveletMatrix:
def __init__(self, data):
self.n = len(data)
self.values = sorted(set(data))
sigma = len(self.values)
self.bitlen = max(1, (sigma - 1).bit_length())
rank = {v: i for i, v in enumerate(self.values)}
cur = [rank[x] for x in data]
self.pref_ones = []
self.zeros = []
for bit in range(self.bitlen - 1, -1, -1):
pref = array('I', [0])
zero, one = [], []
acc = 0
for x in cur:
if (x >> bit) & 1:
acc += 1
one.append(x)
else:
zero.append(x)
pref.append(acc)
self.pref_ones.append(pref)
self.zeros.append(len(zero))
cur = zero + one
def _check_range(self, l, r):
if not (0 <= l <= r <= self.n):
raise IndexError("expected 0 <= l <= r <= n")
def _count_rank_lt(self, l, r, k):
"""Count compressed ranks < k in [l,r)."""
if k <= 0 or l == r:
return 0
if k >= len(self.values):
return r - l
result = 0
for level, bit in enumerate(range(self.bitlen - 1, -1, -1)):
pref = self.pref_ones[level]
ones_l, ones_r = pref[l], pref[r]
zeros_l, zeros_r = l - ones_l, r - ones_r
if (k >> bit) & 1:
result += zeros_r - zeros_l
l = self.zeros[level] + ones_l
r = self.zeros[level] + ones_r
else:
l, r = zeros_l, zeros_r
return result
def range_freq_lt(self, l, r, x):
"""Count i in [l,r) such that data[i] < x."""
self._check_range(l, r)
return self._count_rank_lt(l, r, bisect_left(self.values, x))
def range_freq(self, l, r, lower, upper):
"""Count i in [l,r) such that lower <= data[i] < upper."""
self._check_range(l, r)
if lower >= upper:
return 0
return self.range_freq_lt(l, r, upper) - self.range_freq_lt(l, r, lower)
def kth_smallest(self, l, r, k):
"""Return the 0-indexed k-th smallest value in data[l:r]."""
self._check_range(l, r)
if not (0 <= k < r - l):
raise IndexError("k must satisfy 0 <= k < r-l")
rank = 0
for level, bit in enumerate(range(self.bitlen - 1, -1, -1)):
pref = self.pref_ones[level]
ones_l, ones_r = pref[l], pref[r]
zeros_l, zeros_r = l - ones_l, r - ones_r
zero_count = zeros_r - zeros_l
rank <<= 1
if k < zero_count:
l, r = zeros_l, zeros_r
else:
k -= zero_count
rank |= 1
l = self.zeros[level] + ones_l
r = self.zeros[level] + ones_r
return self.values[rank]
def range_min(self, l, r):
return self.kth_smallest(l, r, 0)
def range_max(self, l, r):
return self.kth_smallest(l, r, r - l - 1)
"""Slope Trick for a convex piecewise-linear function.
The represented function is maintained up to additive constants as a sum of
hinges. Supports adding max(a-x, 0), max(x-a, 0), |x-a|, constants, and a
horizontal translation. `get_min()` returns the minimum function value;
`get_argmin()` returns the interval of minimizers.
Heaps maintain the invariant max(L) <= min(R). L is a max-heap (negated), R a
min-heap. Offsets make `shift(dx)` O(1).
"""
from heapq import heappush, heappop
class SlopeTrick:
def __init__(self):
self.L = []
self.R = []
self.add_l = 0
self.add_r = 0
self.min_f = 0
def _left_max(self):
return -self.L[0] + self.add_l
def _right_min(self):
return self.R[0] + self.add_r
def _rebalance(self):
while self.L and self.R and self._left_max() > self._right_min():
x = self._left_max()
y = self._right_min()
self.min_f += x - y
heappop(self.L)
heappop(self.R)
heappush(self.L, -(y - self.add_l))
heappush(self.R, x - self.add_r)
def add_const(self, c):
self.min_f += c
def add_a_minus_x(self, a):
"""Add max(a-x, 0) to the function."""
heappush(self.L, -(a - self.add_l))
self._rebalance()
def add_x_minus_a(self, a):
"""Add max(x-a, 0) to the function."""
heappush(self.R, a - self.add_r)
self._rebalance()
def add_abs(self, a):
"""Add |x-a| to the function."""
self.add_a_minus_x(a)
self.add_x_minus_a(a)
def shift(self, dx):
"""Horizontal translation: new_f(x) = old_f(x-dx)."""
self.add_l += dx
self.add_r += dx
def get_min(self):
return self.min_f
def get_argmin(self):
"""Return (leftmost minimizer, rightmost minimizer); may be infinite."""
left = self._left_max() if self.L else float('-inf')
right = self._right_min() if self.R else float('inf')
return left, right
"""Generic all-roots tree DP (rerooting).
`graph[u]` contains `(v, edge_data)` for every directed adjacency of the tree.
`merge(a, b)` combines two neighbor contributions (must be associative).
`vertex(merged_value, u)` adds/handles vertex u.
`edge(value_at_u, u, v, edge_data)` converts the message from u's side into
its contribution as seen from v. Identity is the neutral element for merge.
Returns `answer[u]`, the DP result when u is considered the root.
"""
def rerooting(n, graph, identity, merge, vertex, edge):
if n == 0:
return []
parent = [-1] * n
parent_edge = [None] * n
order = [0]
parent[0] = 0
for u in order:
for v, data in graph[u]:
if v == parent[u]:
continue
if parent[v] != -1:
continue
parent[v] = u
parent_edge[v] = data
order.append(v)
if len(order) != n:
raise ValueError("graph must be a connected tree")
# down[u]: result for the subtree rooted at u, excluding parent side.
down = [None] * n
for u in reversed(order):
agg = identity
for v, data in graph[u]:
if parent[v] == u:
agg = merge(agg, edge(down[v], v, u, data))
down[u] = vertex(agg, u)
# up[u] is the message from parent[u] to u (already converted across edge).
up = [None] * n
answer = [None] * n
for u in order:
contributions = []
for v, data in graph[u]:
if v == parent[u] and u != 0:
contributions.append(up[u])
else:
contributions.append(edge(down[v], v, u, data))
m = len(contributions)
pref = [identity] * (m + 1)
suff = [identity] * (m + 1)
for i in range(m):
pref[i + 1] = merge(pref[i], contributions[i])
for i in range(m - 1, -1, -1):
suff[i] = merge(contributions[i], suff[i + 1])
answer[u] = vertex(pref[m], u)
for i, (v, data) in enumerate(graph[u]):
if parent[v] == u:
without_v = merge(pref[i], suff[i + 1])
up[v] = edge(vertex(without_v, u), u, v, data)
return answer
"""Classic Mo's algorithm for offline range queries [l, r).
Example:
mo = Mo(n, queries) # queries is [(l, r), ...]
answers = mo.run(add, remove, get_answer)
`add(i)` / `remove(i)` mutate the maintained window state. `get_answer()`
returns the answer for the current window. Queries are returned in input order.
"""
from math import isqrt
class Mo:
def __init__(self, n, queries, block_size=None):
self.n = n
self.queries = [(l, r, i) for i, (l, r) in enumerate(queries)]
if any(not (0 <= l <= r <= n) for l, r, _ in self.queries):
raise ValueError("queries must satisfy 0 <= l <= r <= n")
q = len(queries)
if block_size is None:
block_size = max(1, n // max(1, isqrt(max(1, q))))
self.block_size = max(1, block_size)
b = self.block_size
self.ordered = sorted(
self.queries,
key=lambda x: (x[0] // b, x[1] if (x[0] // b) % 2 == 0 else -x[1]),
)
def run(self, add, remove, get_answer):
ans = [None] * len(self.queries)
left = right = 0
for l, r, qi in self.ordered:
while left > l:
left -= 1
add(left)
while right < r:
add(right)
right += 1
while left < l:
remove(left)
left += 1
while right > r:
right -= 1
remove(right)
ans[qi] = get_answer()
return ans
"""Lowlink for an undirected graph: bridges and articulation points.
Input edges is a list [(u,v), ...]. Parallel edges are supported because DFS
tracks edge IDs, not just parent vertices. Vertices are 0-indexed.
"""
import sys
class LowLink:
def __init__(self, n, edges):
self.n = n
self.edges = edges
self.g = [[] for _ in range(n)]
for eid, (u, v) in enumerate(edges):
self.g[u].append((v, eid))
self.g[v].append((u, eid))
self.timer = 0
self.tin = [-1] * n
self.low = [-1] * n
self.bridges = [] # edge IDs
self.articulation = [] # vertex IDs
self._art = [False] * n
sys.setrecursionlimit(max(1_000_000, n * 2 + 10))
for v in range(n):
if self.tin[v] == -1:
self._dfs(v, -1)
self.bridges.sort()
self.articulation = [v for v, yes in enumerate(self._art) if yes]
def _dfs(self, v, parent_eid):
self.tin[v] = self.low[v] = self.timer
self.timer += 1
children = 0
for to, eid in self.g[v]:
if eid == parent_eid:
continue
if self.tin[to] != -1:
self.low[v] = min(self.low[v], self.tin[to])
else:
self._dfs(to, eid)
self.low[v] = min(self.low[v], self.low[to])
if self.low[to] > self.tin[v]:
self.bridges.append(eid)
if parent_eid != -1 and self.low[to] >= self.tin[v]:
self._art[v] = True
children += 1
if parent_eid == -1 and children > 1:
self._art[v] = True
def bridge_edges(self):
return [self.edges[eid] for eid in self.bridges]
"""Link-Cut Tree for a dynamic forest with vertex values.
Supports link/cut/connectivity, point assignment, and path-sum queries.
Vertices are 0-indexed. `link(u,v)` / `cut(u,v)` return False if the operation
would be invalid (cycle / non-edge respectively).
"""
class LinkCutTree:
def __init__(self, values):
self.n = len(values)
self.ch = [[-1, -1] for _ in values]
self.fa = [-1] * self.n
self.rev = [False] * self.n
self.val = list(values)
self.sm = list(values)
self.mx = list(values)
self.mn = list(values)
def _is_aux_root(self, x):
p = self.fa[x]
return p == -1 or (self.ch[p][0] != x and self.ch[p][1] != x)
def _apply_rev(self, x):
if x != -1:
self.ch[x][0], self.ch[x][1] = self.ch[x][1], self.ch[x][0]
self.rev[x] = not self.rev[x]
def _push(self, x):
if self.rev[x]:
self._apply_rev(self.ch[x][0])
self._apply_rev(self.ch[x][1])
self.rev[x] = False
def _pull(self, x):
self.sm[x] = self.val[x]
self.mx[x] = self.val[x]
self.mn[x] = self.val[x]
left, right = self.ch[x]
if left != -1:
self.sm[x] += self.sm[left]
self.mx[x] = max(self.mx[x], self.mx[left])
self.mn[x] = min(self.mn[x], self.mn[left])
if right != -1:
self.sm[x] += self.sm[right]
self.mx[x] = max(self.mx[x], self.mx[right])
self.mn[x] = min(self.mn[x], self.mn[right])
def _rotate(self, x):
p = self.fa[x]
g = self.fa[p]
d = 1 if self.ch[p][1] == x else 0
b = self.ch[x][d ^ 1]
if not self._is_aux_root(p):
self.ch[g][1 if self.ch[g][1] == p else 0] = x
self.fa[x] = g
self.ch[x][d ^ 1] = p
self.fa[p] = x
self.ch[p][d] = b
if b != -1:
self.fa[b] = p
self._pull(p)
self._pull(x)
def _splay(self, x):
stack = [x]
y = x
while not self._is_aux_root(y):
y = self.fa[y]
stack.append(y)
for y in reversed(stack):
self._push(y)
while not self._is_aux_root(x):
p = self.fa[x]
if not self._is_aux_root(p):
g = self.fa[p]
zigzig = (self.ch[p][0] == x) == (self.ch[g][0] == p)
self._rotate(p if zigzig else x)
self._rotate(x)
def _access(self, x):
last = -1
y = x
while y != -1:
self._splay(y)
self.ch[y][1] = last
if last != -1:
self.fa[last] = y
self._pull(y)
last = y
y = self.fa[y]
self._splay(x)
def make_root(self, x):
self._access(x)
self._apply_rev(x)
def find_root(self, x):
self._access(x)
while True:
self._push(x)
left = self.ch[x][0]
if left == -1:
break
x = left
self._splay(x)
return x
def connected(self, u, v):
if u == v:
return True
return self.find_root(u) == self.find_root(v)
def link(self, u, v):
self.make_root(u)
if self.find_root(v) == u:
return False
self.fa[u] = v
return True
def cut(self, u, v):
self.make_root(u)
self._access(v)
if self.ch[v][0] != u or self.ch[u][1] != -1:
return False
self.ch[v][0] = -1
self.fa[u] = -1
self._pull(v)
return True
def set_value(self, x, value):
self._access(x)
self.val[x] = value
self._pull(x)
def path_sum(self, u, v):
if not self.connected(u, v):
raise ValueError("u and v are disconnected")
self.make_root(u)
self._access(v)
return self.sm[v]
def path_max(self, u, v):
if not self.connected(u, v):
raise ValueError("u and v are disconnected")
self.make_root(u)
self._access(v)
return self.mx[v]
def path_min(self, u, v):
if not self.connected(u, v):
raise ValueError("u and v are disconnected")
self.make_root(u)
self._access(v)
return self.mn[v]
"""Discrete Li Chao tree for minimum of lines y = m*x + b.
Pass all possible query x-coordinates at construction time. Query coordinates
must be present in xs. For maximum queries, negate m, b, and the returned value.
"""
from bisect import bisect_left
class LiChaoTree:
def __init__(self, xs, inf=10**100):
self.xs = sorted(set(xs))
if not self.xs:
raise ValueError("xs must not be empty")
self.n = len(self.xs)
self.inf = inf
self.tree = [None] * (4 * self.n)
@staticmethod
def _eval(line, x):
return line[0] * x + line[1]
def add_line(self, m, b):
self._add(1, 0, self.n, (m, b))
def _add(self, node, lo, hi, line):
cur = self.tree[node]
if cur is None:
self.tree[node] = line
return
mid = (lo + hi) >> 1
x_l, x_m = self.xs[lo], self.xs[mid]
if self._eval(line, x_m) < self._eval(cur, x_m):
self.tree[node], line = line, cur
cur = self.tree[node]
if hi - lo == 1:
return
# After the midpoint winner is fixed in the node, the other line can
# beat it on at most one side because both functions are linear.
if self._eval(line, x_l) < self._eval(cur, x_l):
self._add(node * 2, lo, mid, line)
elif self._eval(line, self.xs[hi - 1]) < self._eval(cur, self.xs[hi - 1]):
self._add(node * 2 + 1, mid, hi, line)
def query(self, x):
idx = bisect_left(self.xs, x)
if idx == self.n or self.xs[idx] != x:
raise ValueError("query x must be included in xs")
node, lo, hi = 1, 0, self.n
ans = self.inf
while True:
line = self.tree[node]
if line is not None:
ans = min(ans, self._eval(line, x))
if hi - lo == 1:
break
mid = (lo + hi) >> 1
if idx < mid:
node, hi = node * 2, mid
else:
node, lo = node * 2 + 1, mid
return ans
class MonotoneCHT:
"""Minimum CHT with strictly increasing slopes and arbitrary x queries.
Lines are inserted in nondecreasing slope order. Duplicate slopes are
handled by keeping only the smaller intercept. Queries may be in any order;
binary search makes each query O(log number_of_lines).
"""
def __init__(self):
self.lines = []
@staticmethod
def _value(line, x):
return line[0] * x + line[1]
@staticmethod
def _redundant(a, b, c):
# slopes a.m < b.m < c.m; b is redundant if x_ab <= x_bc
return (a[1] - b[1]) * (c[0] - b[0]) <= (b[1] - c[1]) * (b[0] - a[0])
def add_line(self, m, b):
if self.lines and m < self.lines[-1][0]:
raise ValueError("slopes must be added in nondecreasing order")
if self.lines and m == self.lines[-1][0]:
if b >= self.lines[-1][1]:
return
self.lines.pop()
new = (m, b)
while len(self.lines) >= 2 and self._redundant(self.lines[-2], self.lines[-1], new):
self.lines.pop()
self.lines.append(new)
def query(self, x):
if not self.lines:
raise ValueError("no lines have been inserted")
lo, hi = 0, len(self.lines) - 1
while lo < hi:
mid = (lo + hi) >> 1
if self._value(self.lines[mid], x) <= self._value(self.lines[mid + 1], x):
hi = mid
else:
lo = mid + 1
return self._value(self.lines[lo], x)
"""Heavy-Light Decomposition for a tree.
Vertices are 0-indexed. All segment intervals are half-open [l, r).
`path_segments(u, v)` returns (l, r, reversed) pieces in the order from u to v.
For commutative queries, the `reversed` flag can be ignored.
"""
class HLD:
def __init__(self, n, graph, root=0):
self.n = n
self.g = graph
self.root = root
self.parent = [-1] * n
self.depth = [0] * n
self.size = [1] * n
self.heavy = [-1] * n
order = [root]
self.parent[root] = root
for v in order:
for to in graph[v]:
if to == self.parent[v]:
continue
self.parent[to] = v
self.depth[to] = self.depth[v] + 1
order.append(to)
if len(order) != n:
raise ValueError("graph must be a connected tree")
self.parent[root] = -1
for v in reversed(order):
best_size = 0
for to in graph[v]:
if self.parent[to] == v:
self.size[v] += self.size[to]
if self.size[to] > best_size:
best_size = self.size[to]
self.heavy[v] = to
self.head = [-1] * n
self.pos = [-1] * n
self.inv = [-1] * n
cur = 0
stack = [(root, root)]
while stack:
v, h = stack.pop()
while v != -1:
self.head[v] = h
self.pos[v] = cur
self.inv[cur] = v
cur += 1
# Light subtrees are postponed; heavy child is walked immediately.
for to in graph[v]:
if self.parent[to] == v and to != self.heavy[v]:
stack.append((to, to))
v = self.heavy[v]
self.out = [self.pos[v] + self.size[v] for v in range(n)]
def is_ancestor(self, u, v):
return self.pos[u] <= self.pos[v] < self.out[u]
def subtree_interval(self, v):
"""Return the Euler-order interval of v's subtree: [pos[v], out[v])."""
return self.pos[v], self.out[v]
def lca(self, u, v):
while self.head[u] != self.head[v]:
if self.depth[self.head[u]] > self.depth[self.head[v]]:
u = self.parent[self.head[u]]
else:
v = self.parent[self.head[v]]
return u if self.depth[u] < self.depth[v] else v
def distance(self, u, v):
w = self.lca(u, v)
return self.depth[u] + self.depth[v] - 2 * self.depth[w]
def path_segments(self, u, v, edge=False):
"""Return ordered path pieces (l, r, reversed) from u to v.
A piece covers base-array positions [l, r). If `reversed` is True,
traverse the piece from r-1 down to l. With edge=True, each edge is
represented by its deeper endpoint, so the LCA position is excluded.
"""
left, right = [], []
while self.head[u] != self.head[v]:
if self.depth[self.head[u]] >= self.depth[self.head[v]]:
left.append((self.pos[self.head[u]], self.pos[u] + 1, True))
u = self.parent[self.head[u]]
else:
right.append((self.pos[self.head[v]], self.pos[v] + 1, False))
v = self.parent[self.head[v]]
if self.depth[u] >= self.depth[v]:
l = self.pos[v] + (1 if edge else 0)
r = self.pos[u] + 1
if l < r:
left.append((l, r, True))
else:
l = self.pos[u] + (1 if edge else 0)
r = self.pos[v] + 1
if l < r:
right.append((l, r, False))
return left + right[::-1]
def path_intervals(self, u, v, edge=False):
"""Return unordered path intervals; intended for commutative operations."""
return [(l, r) for l, r, _ in self.path_segments(u, v, edge)]