C++ using Binary Index Tree | Get's TLE though in the last 4-5 cases
class MajorityChecker {\npublic:\n    vectorl;\n\tint n;\n    MajorityChecker(vector& arr) {\n        \n\t\t  n = arr.size();\n\t\tl = new vector[arr.size() + 1
class MajorityChecker {\npublic:\n    vector<int>*l;\n\tint n;\n    MajorityChecker(vector<int>& arr) {\n        \n\t\t  n = arr.size();\n\t\tl = new vector<int>[arr.size() + 1];\n        createBIT(arr);\n        \n    }\n    \n    \n    void createBIT(vector<int>&v)\n\t{\n\t\tfor (int i = 1; i <= v.size(); i++)\n\t\t{\n\t\t\tupdateBIT(v[i - 1], i);\n\t\t}\n\t}\n\n\n\n\tint getNext(int idx)\n\t{\n\t\t/* steps:\n\t\t\t1: find 2\'s compliment of the idx;\n\t\t\t2: AND with the orignal idx\n\t\t\t3: Add with the orignal idx\n\t\t*/\n\t\treturn idx + (idx & - idx);\n\n\t}\n\tint getParent(int idx)\n\t{\n\t\t/* steps:\n\t\t\t1: find 2\'s compliment of the idx;\n\t\t\t2: AND with the orignal idx\n\t\t\t3: Subtract with the orignal idx\n\t\t*/\n\t\treturn idx - (idx & - idx);\n\n\t}\n\tvoid updateBIT(int val, int idx)\n\t{\n\n\t\twhile (idx <= n)\n\t\t{\n\n\t\t\tl[idx].push_back(val);\n\t\t\tidx = getNext(idx);\n\n\t\t}\n\n\t}\n    \n    vector<int> getAns(int idx)\n\t{\n\t\tidx += 1;\n\t\tvector<int>x;\n\t\twhile (idx > 0)\n\t\t{\n\t\t\tfor (auto p : l[idx])\n\t\t\t{\n\t\t\t\tx.push_back(p);\n\t\t\t}\n\t\t\tidx = getParent(idx);\n\t\t}\n\t\treturn x;\n\t}\n    \n    \n    int query(int a, int b, int c) {\n      \n\t\tvector<int>x = getAns(b);\n\t\tvector<int>y = getAns(a - 1);\n\t\tunordered_map<int, int>m;\n\t\tfor (auto p : x)\n\t\t{\n\t\t\tm[p]++;\n\t\t}\n\t\tfor (auto p : y)\n\t\t{\n\t\t\tm[p]--;\n\t\t}\n\t\tfor (auto z : m)\n\t\t{\n\t\t\tif (z.second == c)\n\t\t\t{\n\n\t\t\t\t\n\t\t\t\treturn z.first;\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t\treturn -1;\n\t} \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 */
[]