1
class MajorityChecker {
2
 public:
3
  MajorityChecker(vector<int> &arr) {
4
    this->arr = arr;
5
    map<int, int> cnt;
6
    for (auto &v : arr) {
7
      cnt[v]++;
8
    }
9
    val_idx = vector<int>(20001, -1);
10
    for (auto it = cnt.begin(); it != cnt.end(); ++it) {
11
      if (it->second >= 250) {
12
        val_idx[it->first] = elems.size();
13
        elems.push_back(it->first);
14
      }
15
    }
16
    n = elems.size();
17
    pre = vector<vector<int>>(n, vector<int>(arr.size(), 0));
18
    if (val_idx[arr[0]] != -1) pre[val_idx[arr[0]]][0]++;
19
    for (int i = 1; i < arr.size(); ++i) {
20
      for (int j = 0; j < n; ++j) {
21
        pre[j][i] = pre[j][i - 1];
22
      }
23
      if (val_idx[arr[i]] != -1) pre[val_idx[arr[i]]][i]++;
24
    }
25
  }
26

27
  int query(int left, int right, int threshold) {
28
    int width = right - left + 1;
29
    if (width < 500) {
30
      map<int, int> cnt;
31
      int most_frequent = 0;
32
      int most_frequent_val;
33
      while (left <= right) {
34
        if (++cnt[arr[left++]] > most_frequent) {
35
          most_frequent = cnt[arr[left - 1]];
36
          most_frequent_val = arr[left - 1];
37
        }
38
        // early end condition, there are not enough elements left
39
        if (right + most_frequent + 1 < threshold + left) return -1;
40
      }
41
      return most_frequent >= threshold ? most_frequent_val : -1;
42
    }
43

44
    for (int i = 0; i < n; ++i) {
45
      if (pre[i][right] - (left - 1 >= 0 ? pre[i][left - 1] : 0) >= threshold) {
46
        return elems[i];
47
      }
48
    }
49
    return -1;
50
  }
51

52
 private:
53
  vector<int> arr;
54
  vector<int> elems;
55
  vector<int> val_idx;
56
  int n;
57
  vector<vector<int>> pre;
58
};