static_RmQ¶
ソースコード¶
from titan_pylib.data_structures.static_array_query.static_RmQ import StaticRmQ
展開済みコード¶
1# from titan_pylib.data_structures.static_array_query.static_RmQ import StaticRmQ
2from typing import Iterable
3from array import array
4
5
6class StaticRmQ:
7
8 class SparseTableRmQ:
9
10 def __init__(self, a: list[int], INF: int):
11 size = len(a)
12 log = size.bit_length() - 1
13 data = [a] + [[]] * log
14 for i in range(log):
15 pre = data[i]
16 l = 1 << i
17 data[i + 1] = [min(pre[j], pre[j + l]) for j in range(len(pre) - l)]
18 self.size = size
19 self.data = data
20 self.INF = INF
21
22 def prod(self, l: int, r: int) -> int:
23 if l >= r:
24 return self.INF
25 u = (r - l).bit_length() - 1
26 return min(self.data[u][l], self.data[u][r - (1 << u)])
27
28 def __init__(self, a: Iterable[int], INF=10**9):
29 a = list(a)
30 n = len(a)
31 bucket_size = n.bit_length() // 2 + 1
32 bucket_size = 31
33 bucket_cnt = (n + bucket_size - 1) // bucket_size
34 bucket = [a[bucket_size * i : bucket_size * (i + 1)] for i in range(bucket_cnt)]
35 bucket_data = StaticRmQ.SparseTableRmQ([min(b) for b in bucket], INF)
36 bucket_bit = array("I", bytes(4 * bucket_size * bucket_cnt))
37
38 for i, b in enumerate(bucket):
39 stack = []
40 for j, e in enumerate(b):
41 g = -1
42 while stack and b[stack[-1]] > e:
43 stack.pop()
44 if stack:
45 g = stack[-1]
46 stack.append(j)
47 if g == -1:
48 continue
49 bucket_bit[i * bucket_size + j] = bucket_bit[i * bucket_size + g] | (
50 1 << g
51 )
52 self.n = n
53 self.INF = INF
54 self.bucket_size = bucket_size
55 self.bucket_data = bucket_data
56 self.bucket = bucket
57 self.bucket_bit = bucket_bit
58
59 def prod(self, l: int, r: int) -> int:
60 assert (
61 0 <= l <= r <= self.n
62 ), f"IndexError: {self.__class__.__name__}.prod({l}, {r}), n={self.n}"
63 if l == r:
64 return self.INF
65 k1 = l // self.bucket_size
66 k2 = r // self.bucket_size
67 l -= k1 * self.bucket_size
68 r -= k2 * self.bucket_size + 1
69 if k1 == k2:
70 bit = self.bucket_bit[k1 * self.bucket_size + r] >> l
71 return self.bucket[k1][(bit & (-bit)).bit_length() + l - 1 if bit else r]
72 ans = self.INF
73 if l < len(self.bucket[k1]):
74 bit = self.bucket_bit[k1 * self.bucket_size + len(self.bucket[k1]) - 1] >> l
75 ans = self.bucket[k1][(bit & (-bit)).bit_length() + l - 1 if bit else -1]
76 ans = min(ans, self.bucket_data.prod(k1 + 1, k2))
77 if r >= 0:
78 bit = self.bucket_bit[k2 * self.bucket_size + r]
79 ans = min(
80 ans, self.bucket[k2][(bit & (-bit)).bit_length() - 1 if bit else r]
81 )
82 return ans