seg tree | binary search | c++
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass SegTree{\n    vector<pair<int, int>> st;\n    public:\n    SegTree(int n){\n        st.resize(4*n);\n    }\n    void merge(pair<int, int> &res,  pair<int, int> &l, pair<int, int> &r){\n        if(l.first == r.first){\n            res =  make_pair(l.first, l.second + r.second);\n        }\n        else if(l.second >= r.second){\n            res =  make_pair(l.first, l.second - r.second);\n        }\n        else{\n            res = make_pair(r.first, r.second - l.second);\n        }\n    }\n    void buildTree(int ss, int se, int si, vector<int> &arr){\n\n        if(ss == se){\n            st[si] = make_pair(arr[ss], 1);\n            return;\n        }\n        int m = ss + (se-ss)/2;\n        buildTree(ss, m, 2*si+1, arr);\n        buildTree(m+1, se, 2*si+2, arr);\n\n        merge(st[si], st[2*si+1], st[2*si+2]);\n    }\n\n    pair<int, int> findMajority(int ss, int se, int &qs, int &qe, int si){\n        if(qe < ss || se < qs) return {0, 0};\n        if(qs<=ss && se<=qe) return st[si];\n\n        int m = ss + (se-ss)/2;\n        auto l = findMajority(ss, m, qs, qe, 2*si+1);\n        auto r = findMajority(m+1, se, qs, qe, 2*si+2);\n        pair<int, int> res;\n        merge(res, l, r);\n        return res; \n    }\n};\n\n\nclass MajorityChecker {\n   SegTree root;\n    int n;\n    unordered_map<int, vector<int>> elementToPos;\npublic:\n\n    MajorityChecker(vector<int>& arr): root(arr.size()), n(arr.size()){\n        root.buildTree(0, n-1, 0, arr);\n        for(int i=0; i<arr.size(); i++){\n            elementToPos[arr[i]].push_back(i);\n        }\n    }\n    \n    int query(int left, int right, int threshold) {\n        pair<int, int> t = root.findMajority(0, n-1, left, right, 0);\n        if(t.first == 0) return -1;\n        int l = lower_bound(elementToPos[t.first].begin(), elementToPos[t.first].end(), left) - elementToPos[t.first].begin();\n        int r = upper_bound(elementToPos[t.first].begin(), elementToPos[t.first].end(), right) - elementToPos[t.first].begin();\n        \n        if(r-l >= threshold) return t.first;\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++']