segment_tree_RmQ¶
ソースコード¶
from titan_pylib.data_structures.segment_tree.segment_tree_RmQ import SegmentTreeRmQ
展開済みコード¶
1# from titan_pylib.data_structures.segment_tree.segment_tree_RmQ import SegmentTreeRmQ
2# from titan_pylib.data_structures.segment_tree.segment_tree_interface import (
3# SegmentTreeInterface,
4# )
5from abc import ABC, abstractmethod
6from typing import TypeVar, Generic, Union, Iterable, Callable
7
8T = TypeVar("T")
9
10
11class SegmentTreeInterface(ABC, Generic[T]):
12
13 @abstractmethod
14 def __init__(self, n_or_a: Union[int, Iterable[T]], op: Callable[[T, T], T], e: T):
15 raise NotImplementedError
16
17 @abstractmethod
18 def set(self, k: int, v: T) -> None:
19 raise NotImplementedError
20
21 @abstractmethod
22 def get(self, k: int) -> T:
23 raise NotImplementedError
24
25 @abstractmethod
26 def prod(self, l: int, r: int) -> T:
27 raise NotImplementedError
28
29 @abstractmethod
30 def all_prod(self) -> T:
31 raise NotImplementedError
32
33 @abstractmethod
34 def max_right(self, l: int, f: Callable[[T], bool]) -> int:
35 raise NotImplementedError
36
37 @abstractmethod
38 def min_left(self, r: int, f: Callable[[T], bool]) -> int:
39 raise NotImplementedError
40
41 @abstractmethod
42 def tolist(self) -> list[T]:
43 raise NotImplementedError
44
45 @abstractmethod
46 def __getitem__(self, k: int) -> T:
47 raise NotImplementedError
48
49 @abstractmethod
50 def __setitem__(self, k: int, v: T) -> None:
51 raise NotImplementedError
52
53 @abstractmethod
54 def __str__(self):
55 raise NotImplementedError
56
57 @abstractmethod
58 def __repr__(self):
59 raise NotImplementedError
60# from titan_pylib.my_class.supports_less_than import SupportsLessThan
61from typing import Protocol
62
63
64class SupportsLessThan(Protocol):
65
66 def __lt__(self, other) -> bool: ...
67from typing import Generic, Iterable, TypeVar, Union
68
69T = TypeVar("T", bound=SupportsLessThan)
70
71
72class SegmentTreeRmQ(SegmentTreeInterface, Generic[T]):
73 """RmQ セグ木です。"""
74
75 def __init__(self, _n_or_a: Union[int, Iterable[T]], e: T) -> None:
76 self._e = e
77 if isinstance(_n_or_a, int):
78 self._n = _n_or_a
79 self._log = (self._n - 1).bit_length()
80 self._size = 1 << self._log
81 self._data = [self._e] * (self._size << 1)
82 else:
83 _n_or_a = list(_n_or_a)
84 self._n = len(_n_or_a)
85 self._log = (self._n - 1).bit_length()
86 self._size = 1 << self._log
87 _data = [self._e] * (self._size << 1)
88 _data[self._size : self._size + self._n] = _n_or_a
89 for i in range(self._size - 1, 0, -1):
90 _data[i] = (
91 _data[i << 1]
92 if _data[i << 1] < _data[i << 1 | 1]
93 else _data[i << 1 | 1]
94 )
95 self._data = _data
96
97 def set(self, k: int, v: T) -> None:
98 if k < 0:
99 k += self._n
100 assert (
101 0 <= k < self._n
102 ), f"IndexError: {self.__class__.__name__}.set({k}: int, {v}: T), n={self._n}"
103 k += self._size
104 self._data[k] = v
105 for _ in range(self._log):
106 k >>= 1
107 self._data[k] = (
108 self._data[k << 1]
109 if self._data[k << 1] < self._data[k << 1 | 1]
110 else self._data[k << 1 | 1]
111 )
112
113 def get(self, k: int) -> T:
114 if k < 0:
115 k += self._n
116 assert (
117 0 <= k < self._n
118 ), f"IndexError: {self.__class__.__name__}.get({k}: int), n={self._n}"
119 return self._data[k + self._size]
120
121 def prod(self, l: int, r: int) -> T:
122 assert (
123 0 <= l <= r <= self._n
124 ), f"IndexError: {self.__class__.__name__}.prod({l}: int, {r}: int)"
125 l += self._size
126 r += self._size
127 res = self._e
128 while l < r:
129 if l & 1:
130 if res > self._data[l]:
131 res = self._data[l]
132 l += 1
133 if r & 1:
134 r ^= 1
135 if res > self._data[r]:
136 res = self._data[r]
137 l >>= 1
138 r >>= 1
139 return res
140
141 def all_prod(self) -> T:
142 return self._data[1]
143
144 def max_right(self, l: int, f=lambda lr: lr):
145 assert (
146 0 <= l <= self._n
147 ), f"IndexError: {self.__class__.__name__}.max_right({l}, f) index out of range"
148 assert f(
149 self._e
150 ), f"{self.__class__.__name__}.max_right({l}, f), f({self._e}) must be true."
151 if l == self._n:
152 return self._n
153 l += self._size
154 s = self._e
155 while True:
156 while l & 1 == 0:
157 l >>= 1
158 if not f(min(s, self._data[l])):
159 while l < self._size:
160 l <<= 1
161 if f(min(s, self._data[l])):
162 if s > self._data[l]:
163 s = self._data[l]
164 l += 1
165 return l - self._size
166 s = min(s, self._data[l])
167 l += 1
168 if l & -l == l:
169 break
170 return self._n
171
172 def min_left(self, r: int, f=lambda lr: lr):
173 assert (
174 0 <= r <= self._n
175 ), f"IndexError: {self.__class__.__name__}.min_left({r}, f) index out of range"
176 assert f(
177 self._e
178 ), f"{self.__class__.__name__}.min_left({r}, f), f({self._e}) must be true."
179 if r == 0:
180 return 0
181 r += self._size
182 s = self._e
183 while True:
184 r -= 1
185 while r > 1 and r & 1:
186 r >>= 1
187 if not f(min(self._data[r], s)):
188 while r < self._size:
189 r = r << 1 | 1
190 if f(min(self._data[r], s)):
191 if s > self._data[r]:
192 s = self._data[r]
193 r -= 1
194 return r + 1 - self._size
195 s = min(self._data[r], s)
196 if r & -r == r:
197 break
198 return 0
199
200 def tolist(self) -> list[T]:
201 return [self.get(i) for i in range(self._n)]
202
203 def show(self) -> None:
204 print(
205 f"<{self.__class__.__name__}> [\n"
206 + "\n".join(
207 [
208 " "
209 + " ".join(
210 map(str, [self._data[(1 << i) + j] for j in range(1 << i)])
211 )
212 for i in range(self._log + 1)
213 ]
214 )
215 + "\n]"
216 )
217
218 def __getitem__(self, k: int) -> T:
219 assert (
220 -self._n <= k < self._n
221 ), f"IndexError: {self.__class__.__name__}.__getitem__({k}: int), n={self._n}"
222 return self.get(k)
223
224 def __setitem__(self, k: int, v: T):
225 assert (
226 -self._n <= k < self._n
227 ), f"IndexError: {self.__class__.__name__}.__setitem__{k}: int, {v}: T), n={self._n}"
228 self.set(k, v)
229
230 def __str__(self):
231 return "[" + ", ".join(map(str, (self.get(i) for i in range(self._n)))) + "]"
232
233 def __repr__(self):
234 return f"{self.__class__.__name__}({self})"
仕様¶
- class SegmentTreeRmQ(_n_or_a: int | Iterable[T], e: T)[source]¶
Bases:
SegmentTreeInterface,Generic[T]RmQ セグ木です。