C++ O(NlogNlogN) solution using divide and conquer and segment tree with explaination
This question asks about range queries. In most cases, range queries could be solved by using\n"memorized" divide and conquer.\nThe algorithm could be described
This question asks about range queries. In most cases, range queries could be solved by using\n"memorized" divide and conquer.\nThe algorithm could be described as follows:\n1. preprocessing O(NlogN):\n\t1.1  create an "adjacency list" of all numbers and its occurence index\n\t\t\tFor example [1,1,2,1,1] would result in the "adjacency list"\n\t\t\t1: [0,1,3,4]\n\t\t\t2: [2]\n\t1.2  build the segment tree, which each nodes stores standard majority element on range \n\t\t\t[l, r]\n2. query (O(logNlogN) for each query):\n   2.1  query on segment tree and return the standard majority element on [l, r]\n   2.2  check the frequency of val returned 2.1 and see if freq(val) >= threshold\n----------------------------------------------------------------------------------------------------\nThe most difficult part of this problem is merge interval:\nsuppose that [l, mid] has majority element e1 (e1 = -1 is not exists)\n[mid, r] has majority element e2 (e2 = -1 is not exists), we want to know the majority element\ne of [l, r].\n\nWe can make the following claims:\n(1) if e1 = -1 and e2 = -1 then no majority element on [l, r]\n(2) if e1 = -1 and e2 != -1 then majority element might be e2\n(3) if e1 != -1 and e2 = -1 then majority element might be e1\n(4) otherwise, majority element might be e1 or e2\n\nFor case (2)(3)(4), we can use binary search on the "adjacency list" created on the preprocessing step to decide whether e should be e1, e2 or -1.\n\nImplementation:\n```\nclass MajorityChecker {\npublic:\n    MajorityChecker(vector<int>& a) {\n        n = a.size();\n        f = vector<vector<int>>(20001, vector<int>());\n        tree = vector<int>(65592, -1);\n        arr = a;\n        for (int i = 0 ; i < n; i++) {\n            f[a[i]].push_back(i);\n        }\n        build(0, n - 1, 1);\n    }\n    \n    int query(int left, int right, int threshold) {\n        int val = queryUtil(left, right, 0, n - 1, 1);\n        if (val == -1) return -1;\n        if (frequency(left, right, val) < threshold) return -1;\n        return val;\n    }\nprivate:\n    int n;\n    vector<vector<int>> f;\n    vector<int> tree;\n    vector<int> arr;\n    void build(int l, int r, int index) {\n        if (l > r) return;\n        if (l == r) {\n            tree[index] = arr[l];\n            return;\n        }\n        \n        int mid = l + (r - l) / 2;\n        build(l, mid, index * 2);\n        build(mid + 1, r, index * 2 + 1);\n        tree[index] = merge_interval(l, r, tree[index * 2], tree[index * 2 + 1]);\n    }\n    \n    int queryUtil(int start, int end, int l, int r, int index) {\n        if (start > end || l > r) return -1;\n        if (start == l && r == end) return tree[index];\n        if (start > r || end < l) return -1;\n        int mid = l + (r - l) / 2;\n        if (end <= mid) {\n            return queryUtil(start, end, l, mid, index * 2);\n        }\n        \n        if (start >= mid + 1) {\n            return queryUtil(start, end, mid + 1, r, index * 2 + 1);\n        }\n        \n        int q1 = queryUtil(start, mid,l, mid, index * 2);\n        int q2 = queryUtil(mid + 1, end, mid + 1, r, index * 2 + 1);\n        int ret = merge_interval(start, end, q1, q2);\n        return ret;\n    }\n    \n    int merge_interval(int l, int r, int maj1, int maj2) {\n        int fq1, fq2;\n        \n        if (maj1 == -1 && maj2 == -1) return -1;\n        if (maj1 == -1) {\n            \n            fq1 = frequency(l, r, maj2);\n            if (2 * fq1 > r - l + 1) {\n               \n                return maj2;\n            }\n            \n            return -1;\n        }\n        \n        if (maj2 == -1) {\n            fq1 = frequency(l, r, maj1);\n            if (2 * fq1 > r - l + 1) {\n                return maj1;\n            }\n            \n            return -1;\n        }\n        \n        if (maj1 == maj2) {\n            return maj1;    \n        }\n        \n        fq1 = frequency(l, r, maj1);\n        fq2 = frequency(l, r, maj2);\n        if (2 * fq1 > r - l + 1) {\n            return maj1;\n        }\n        \n        if (2 * fq2 > r - l + 1) {\n            return maj2;\n        }\n        \n        return -1;\n    }\n    \n    int frequency(int l, int r, int val) {\n        if (r < l || val < 0) return 0;\n        int low = 0, high = ((int) f[val].size()) - 1;\n        int left = 1048576, right = -1;\n        while (low <= high) {\n            int mid = low + (high - low) / 2;\n            if (f[val][mid] >= l) {\n                left = min(mid, left);\n                high = mid - 1;\n            } else {\n                low = mid + 1;\n            }\n        }\n        \n        if (left == 1048576) return 0;\n        low = 0;\n        high = ((int) f[val].size()) - 1;\n        while (low <= high) {\n            int mid = low + (high - low) / 2;\n            if (f[val][mid] <= r) {\n                right = max(mid, right);\n                low = mid + 1;\n            } else {\n                high = mid - 1;\n            }\n        }\n            \n        if (right == -1) return 0;\n        return right - left + 1;\n    }\n};\n```\n
[]