c++ | easy | short
\n# Code\n\nclass MajorityChecker {\n  const int kMax = 2e4+5;\n    struct Node {\n        int majority; \n        int count;  \n    };\n    int n;\n    vector<
\n# Code\n```\nclass MajorityChecker {\n  const int kMax = 2e4+5;\n    struct Node {\n        int majority; \n        int count;  \n    };\n    int n;\n    vector<Node> tree;\n    vector<int> nums;\n    vector<vector<int>> indice;\n\n    \n    Node merge(const Node& a, const Node& b) {\n        if (a.majority == b.majority) return {a.majority, a.count + b.count};\n        if (a.count > b.count) return {a.majority, a.count - b.count};\n        return {b.majority, b.count - a.count};\n    }\n\n    void build(int i, int l, int r) {\n        if (l == r) {  \n            tree[i] = {nums[l-1], 1}; \n            return;\n        }\n        int mid = l+(r-l)/2;\n        build(i*2, l, mid);\n        build(i*2+1, mid+1, r);\n        tree[i] = merge(tree[i*2], tree[i*2+1]);\n    }\n\n    Node query_majority(int i, int l, int r, int L, int R) {\n        if (L > r || R < l) return {0, 0};\n        if (L <= l && R >= r) return tree[i];\n        int mid = l+(r-l)/2;\n        Node a = query_majority(i*2, l, mid, L, R);\n        Node b = query_majority(i*2+1, mid+1, r, L, R);\n        return merge(a, b);\n    }\n\npublic:\n    MajorityChecker(vector<int>& arr) {\n        n = arr.size();\n        tree.resize(kMax<<2);\n        nums = arr;\n        indice.resize(kMax);\n        for (int i = 0; i < n; ++i) indice[arr[i]].push_back(i);\n        build(1, 1, n);\n    }\n\n    int query(int left, int right, int threshold) {\n        int num = query_majority(1, 1, n, left+1, right+1).majority;\n        if (num == 0) return -1;\n        const auto& ni = indice[num];\n        int l = lower_bound(ni.begin(), ni.end(), left)-ni.begin();\n        int r = upper_bound(ni.begin(), ni.end(), right)-ni.begin();\n        if (r-l >= threshold) return num;\n        return -1;\n    }\n};\n\n/**\n * Your MajorityChecker object will be instantiated and called as such:\n * MajorityChecker* obj = new MajorityChecker(arr);\n * int param_1 = obj->query(left,right,threshold);\n */\n```
['C++']