Source code for titan_pylib.data_structures.static_array_query.static_RmQ

 1from typing import Iterable
 2from array import array
 3
 4

[docs]
 5class StaticRmQ:
 6

[docs]
 7    class SparseTableRmQ:
 8
 9        def __init__(self, a: list[int], INF: int):
10            size = len(a)
11            log = size.bit_length() - 1
12            data = [a] + [[]] * log
13            for i in range(log):
14                pre = data[i]
15                l = 1 << i
16                data[i + 1] = [min(pre[j], pre[j + l]) for j in range(len(pre) - l)]
17            self.size = size
18            self.data = data
19            self.INF = INF
20

[docs]
21        def prod(self, l: int, r: int) -> int:
22            if l >= r:
23                return self.INF
24            u = (r - l).bit_length() - 1
25            return min(self.data[u][l], self.data[u][r - (1 << u)])


26
27    def __init__(self, a: Iterable[int], INF=10**9):
28        a = list(a)
29        n = len(a)
30        bucket_size = n.bit_length() // 2 + 1
31        bucket_size = 31
32        bucket_cnt = (n + bucket_size - 1) // bucket_size
33        bucket = [a[bucket_size * i : bucket_size * (i + 1)] for i in range(bucket_cnt)]
34        bucket_data = StaticRmQ.SparseTableRmQ([min(b) for b in bucket], INF)
35        bucket_bit = array("I", bytes(4 * bucket_size * bucket_cnt))
36
37        for i, b in enumerate(bucket):
38            stack = []
39            for j, e in enumerate(b):
40                g = -1
41                while stack and b[stack[-1]] > e:
42                    stack.pop()
43                if stack:
44                    g = stack[-1]
45                stack.append(j)
46                if g == -1:
47                    continue
48                bucket_bit[i * bucket_size + j] = bucket_bit[i * bucket_size + g] | (
49                    1 << g
50                )
51        self.n = n
52        self.INF = INF
53        self.bucket_size = bucket_size
54        self.bucket_data = bucket_data
55        self.bucket = bucket
56        self.bucket_bit = bucket_bit
57

[docs]
58    def prod(self, l: int, r: int) -> int:
59        assert (
60            0 <= l <= r <= self.n
61        ), f"IndexError: {self.__class__.__name__}.prod({l}, {r}), n={self.n}"
62        if l == r:
63            return self.INF
64        k1 = l // self.bucket_size
65        k2 = r // self.bucket_size
66        l -= k1 * self.bucket_size
67        r -= k2 * self.bucket_size + 1
68        if k1 == k2:
69            bit = self.bucket_bit[k1 * self.bucket_size + r] >> l
70            return self.bucket[k1][(bit & (-bit)).bit_length() + l - 1 if bit else r]
71        ans = self.INF
72        if l < len(self.bucket[k1]):
73            bit = self.bucket_bit[k1 * self.bucket_size + len(self.bucket[k1]) - 1] >> l
74            ans = self.bucket[k1][(bit & (-bit)).bit_length() + l - 1 if bit else -1]
75        ans = min(ans, self.bucket_data.prod(k1 + 1, k2))
76        if r >= 0:
77            bit = self.bucket_bit[k2 * self.bucket_size + r]
78            ans = min(
79                ans, self.bucket[k2][(bit & (-bit)).bit_length() - 1 if bit else r]
80            )
81        return ans