sparse_table_RmQ¶
ソースコード¶
from titan_pylib.data_structures.sparse_table.sparse_table_RmQ import SparseTableRmQ
展開済みコード¶
1# from titan_pylib.data_structures.sparse_table.sparse_table_RmQ import SparseTableRmQ
2# from titan_pylib.my_class.supports_less_than import SupportsLessThan
3from typing import Protocol
4
5
6class SupportsLessThan(Protocol):
7
8 def __lt__(self, other) -> bool: ...
9from typing import Generic, TypeVar, Iterable
10
11T = TypeVar("T", bound=SupportsLessThan)
12
13
14class SparseTableRmQ(Generic[T]):
15 """
16 2項演算を :math:`\\min` にしたものです。
17 """
18
19 def __init__(self, a: Iterable[T], e: T):
20 if not isinstance(a, list):
21 a = list(a)
22 self.size = len(a)
23 log = self.size.bit_length() - 1
24 data = [a] + [[]] * log
25 for i in range(log):
26 pre = data[i]
27 l = 1 << i
28 data[i + 1] = [
29 pre[j] if pre[j] < pre[j + l] else pre[j + l]
30 for j in range(len(pre) - l)
31 ]
32 self.data = data
33 self.e = e
34
35 def prod(self, l: int, r: int) -> T:
36 assert 0 <= l <= r <= self.size
37 if l == r:
38 return self.e
39 u = (r - l).bit_length() - 1
40 return (
41 self.data[u][l]
42 if self.data[u][l] < self.data[u][r - (1 << u)]
43 else self.data[u][r - (1 << u)]
44 )
45
46 def __getitem__(self, k: int) -> T:
47 assert 0 <= k < self.size
48 return self.data[0][k]
49
50 def __len__(self):
51 return self.size
52
53 def __str__(self):
54 return str(self.data[0])
55
56 def __repr__(self):
57 return f"{self.__class__.__name__}({self.data[0]}, {self.e})"