Python, Segment tree
The key of this problem is 2 * threshold > right - left + 1 this condition given in the statement. So, the majority element should occur more than half of the t
The key of this problem is `2 * threshold > right - left + 1` this condition given in the statement. So, the majority element should occur more than half of the times. Key insight is that if we divide subarray into any two subarrays:\n`[left, middle], [middle + 1, right]` then majority element must be "major" in one of these two subarrays as well. Otherwise, it is less than half of the times in the first and the second array, and in sum it won\'t be majority element in a bigger array. So, solving two subproblems, we get two candidates for majority element, now we just need to fast check for both of them. We use bisect to count number of occurences of any value (using some precomputed things). This subarray divisions naturally implies that we need to have precomputed segment tree as well.\n\n\n```\nimport bisect\n\nclass MajorityChecker:\n    def __init__(self, arr):\n        self.n = len(arr)\n        self.arr = arr\n        self.v2sl = {v: [] for v in arr}\n        for i, v in enumerate(arr):\n            self.v2sl[v].append(i)\n        self.t = {}\n        self.build(1, 0, self.n - 1)\n\n    def count(self, v, i, j):\n        if v == -1:\n            return 0\n\n        l = bisect.bisect_left(self.v2sl[v], i)\n        r = bisect.bisect_right(self.v2sl[v], j)\n        return r - l\n\n    def build(self, v, tl, tr):\n        if tl == tr:\n            self.t[v] = self.arr[tl]\n            return\n\n        tm = (tl + tr) // 2\n        self.build(2 * v, tl, tm)\n        self.build(2 * v + 1, tm + 1, tr)\n\n        c1 = self.t[2 * v]\n        c2 = self.t[2 * v + 1]\n        if c1 != -1 and 2 * self.count(c1, tl, tr) > tr - tl + 1:\n            self.t[v] = c1\n        elif c2 != -1 and 2 * self.count(c2, tl, tr) > tr - tl + 1:\n            self.t[v] = c2\n        else:\n            self.t[v] = -1\n\n    def max_occurence(self, left, right, v, tl, tr):\n        if left > right:\n            return -1, 0\n        if left == tl and right == tr:\n            return self.t[v], self.count(self.t[v], left, right)\n\n        tm = (tl + tr) // 2\n        c1, _ = self.max_occurence(left, min(right, tm), 2 * v, tl, tm)\n        c2, _ = self.max_occurence(max(left, tm + 1), right, 2 * v + 1, tm + 1, tr)\n        ct1, ct2 = self.count(c1, left, right), self.count(c2, left, right)\n\n        if 2 * ct1 > right - left + 1:\n            return c1, ct1\n        elif 2 * ct2 > right - left + 1:\n            return c2, ct2\n        else:\n            return -1, 0\n\n\n    def query(self, left: int, right: int, threshold: int) -> int:\n        c, ct = self.max_occurence(left, right, 1, 0, self.n - 1)\n        return c if ct >= threshold else -1\n```
[]