C++ Segment Tree
Remember to change l and r in the "operator + part".. \n\nclass MajorityChecker {\npublic:\n    struct Node{\n        int l, r;\n        int val, cnt;\n        
Remember to change l and r in the "operator + part".. \n```\nclass MajorityChecker {\npublic:\n    struct Node{\n        int l, r;\n        int val, cnt;\n        Node operator + (const Node node) const {\n            Node t;\n            if(val == node.val)\n            {\n                t.val = val;\n                t.cnt = cnt + node.cnt;\n            }else if(cnt > node.cnt)\n            {\n                t.val = val;\n                t.cnt = cnt - node.cnt;\n            }\n            else{\n                t.val = node.val;\n                t.cnt = node.cnt - cnt;\n            }\n            t.l = l, t.r = node.r;\n            return t;\n        } \n    };\n    static const int N = 2e4+10;\n    Node tr[4*N];\n    int a[N], n;\n    vector<int> s[N];\n    void pushup(int u){\n        tr[u] = tr[u<<1] + tr[u<<1|1];\n    }\n    void build(int u,  int l, int r){\n        if(l == r)\n            tr[u] = {l, r, a[l], 1};\n        else{\n            int mid = l+r>>1;\n            tr[u].l = l, tr[u].r = r;\n            build(u<<1, l, mid), build(u<<1|1, mid+1, r);\n            pushup(u);\n        }\n    }\n    Node ask(int u, int l, int r){\n        if(tr[u].l >= l&&tr[u].r <= r)\n            return tr[u];\n        else{\n            int mid = tr[u].l + tr[u].r >> 1;\n            if(l>mid)\n                return ask(u<<1|1,l, r);\n            else if(r<=mid)\n                return ask(u<<1,l, r);\n            else{\n                auto left = ask(u<<1, l, r);\n                auto right = ask(u<<1|1, l, r);\n                return left + right;\n            }\n                \n        }\n    }\n    MajorityChecker(vector<int>& arr) {\n        n = arr.size();\n        for(int i = 0;i<n;i++)\n            s[a[i] = arr[i]].push_back(i);\n        build(1, 0, n-1);\n    }\n    \n    int query(int left, int right, int threshold) {\n        int val = ask(1, left, right).val;\n        if(upper_bound(s[val].begin(), s[val].end(), right) - lower_bound(s[val].begin(), s[val].end(), left) >= threshold) return val;\n        else 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```
[]