1
class MajorityChecker {
2

3
  private final int digits = 15;
4
  private int[][] presum;
5
  private ArrayList<Integer>[] pos;
6

7
  public MajorityChecker(int[] arr) {
8
    int len = arr.length;
9
    presum = new int[len + 1][digits];
10
    pos = new ArrayList[20001];
11

12
    for (int i = 0; i < len; i++) {
13
      int n = arr[i];
14
      if (pos[n] == null) pos[n] = new ArrayList();
15
      pos[n].add(i);
16

17
      for (int j = 0; j < digits; j++) {
18
        presum[i + 1][j] = presum[i][j] + (n & 1);
19
        n >>= 1;
20
      }
21
    }
22
  }
23

24
  public int query(int left, int right, int threshold) {
25
    int ans = 0;
26
    for (int i = digits - 1; i >= 0; i--) {
27
      int cnt = presum[right + 1][i] - presum[left][i];
28
      int b = 1;
29
      if (cnt >= threshold) b = 1;
30
      else if (right - left + 1 - cnt >= threshold) b = 0;
31
      else return -1;
32
      ans = (ans << 1) + b;
33
    }
34

35
    // check
36
    ArrayList<Integer> list = pos[ans];
37
    if (list == null) return -1;
38
    int L = floor(list, left - 1);
39
    int R = floor(list, right);
40
    if (R - L >= threshold) return ans;
41
    return -1;
42
  }
43

44
  private int floor(ArrayList<Integer> list, int n) {
45
    int left = 0, right = list.size() - 1, mid;
46
    while (left <= right) {
47
      mid = left + (right - left) / 2;
48
      int index = list.get(mid);
49
      if (index == n) return mid;
50
      else if (index < n) left = mid + 1;
51
      else right = mid - 1;
52
    }
53
    return right;
54
  }
55
}