1
# Runtime: 1961 ms (Top 83.96%) | Memory: 47.2 MB (Top 5.66%)
2
MAX_N = 2 * 10**4
3
MAX_BIT = MAX_N.bit_length()
4

5

6
class MajorityChecker:
7

8
    def __init__(self, nums: List[int]):
9
        n = len(nums)
10
        self.bit_sum = [[0] * MAX_BIT for _ in range(n + 1)]
11
        for i in range(1, n + 1):
12
            for b in range(MAX_BIT):
13
                self.bit_sum[i][b] = self.bit_sum[i - 1][b] + ((nums[i - 1] >> b) & 1)
14
        self.num_idx = defaultdict(list)
15
        for i in range(n):
16
            self.num_idx[nums[i]].append(i)
17

18
    def query(self, left: int, right: int, threshold: int) -> int:
19
        num = 0
20
        for b in range(MAX_BIT):
21
            if self.bit_sum[right + 1][b] - self.bit_sum[left][b] >= threshold:
22
                num |= 1 << b
23
        l = bisect.bisect_left(self.num_idx[num], left)
24
        r = bisect.bisect_right(self.num_idx[num], right)
25
        if r - l >= threshold:
26
            return num
27
        return -1