LeetCode 1157 - Online Majority Element In Subarray

https://leetcode.com/problems/online-majority-element-in-subarray/

Implementing the class MajorityChecker, which has the following API:

• MajorityChecker(int[] arr) constructs an instance of MajorityChecker with the given array arr;
• int query(int left, int right, int threshold) has arguments such that:
  • 0 <= left <= right < arr.length representing a subarray of arr;
  • 2 * threshold > right - left + 1, ie. the threshold is always a strict majority of the length of the subarray

Each query(...) returns the element in arr[left], arr[left+1], ..., arr[right] that occurs at least threshold times, or -1 if no such element exists.

Example:

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // returns 1
majorityChecker.query(0,3,3); // returns -1
majorityChecker.query(2,3,2); // returns 2

Constraints:

• 1 <= arr.length <= 20000
• 1 <= arr[i] <= 20000
• For each query, 0 <= left <= right < len(arr)
• For each query, 2 * threshold > right - left + 1
• The number of queries is at most 10000

https://leetcode.com/problems/online-majority-element-in-subarray/discuss/356227/C%2B%2B-Codes-of-different-approaches-(Random-Pick-Trade-off-Segment-Tree-Bucket)

Some basic knowledge to understand the following methods and codes:

1. For a given interval [l, r] and threshold, we would like to find the majority which occurs at least threshold times. The problem also gives an inequality 2 * threshold > right - left + 1, which means the majority must occur more than half. We denote the majority which satisfies the inequality as "more than half" majority.
2. For the "more than half" majority, the following theorem always holds: if we split the interval [l, r] into consecutive sub-intervals [l, a_1], [a_1+1, a_2], ..., [a_{n-1}+1, a_n], [a_n+1, r], the "more than half" majority of interval [l, r] (if it exists) should be also the "more than half" majority of at least one sub-interval. This can be proved by contradiction.
3. By the theorem in 2, we can split the interval [l, r] into sub-intervals and find the "more than half" majority of each sub-interval and check whether it is the "more than half" majority of the interval [l, r].
4. We can use Boyer–Moore majority vote algorithm to find the "more than half" majority in O(n) time.
5. We can use a unordered_map<int, vector<int>> to store the positions of each number in [l, r]. The key in the unordered_map represents a number and the value represents the positions of that number in increasing order. Thus we can count the occurrences of a number in a given interval [l, r] in O(log(n)) time by using binary search (in C++ we can use lower_bound and upper_bound to simplify the code).
6. We can combine 4 and 5 together to check whether the "more than half" majority occurs at least threshold times. The time complexity is the same as 4, since O(n + log(n)) = O(n) holds.

I will show 4 different method with brief explanations below. I will use the sign No.x to reference the basic knowledge with number x. No.6 is often used to find the "more than half" majority in a short sub-interval, while No.5 is often used to find the "more than half" majority in a long interval after finishing the sub-interval calculations, as No.3 states.

Random Pick:
As the majority occurs more than half in the interval [l, r], we will have the probability of more than 1/2 to find the "more than half" majority if we randomly pick a number in the interval. Thus, if we randomly pick try_bound times, we will have the probability of (1-(1/2)) ** try_bound not to find the "more than half" majority. The probability will be less than 1e-6 if we set try_bound as 20. If we find nothing in try_bound times, we can claim that there is no "more than half" majority.
Here we use No.5 to count the occurrences of a randomly picked number.

Runtime: ~200 ms
Pre-calculation: O(n)
Query: O(try_bound * log(n))

class MajorityChecker {
private:
    unordered_map<int, vector<int>> pos;
    vector<int> a;
    int try_bound;
    
public:
    MajorityChecker(vector<int>& arr): a(arr) {
        srand(time(nullptr));
        for (int i = 0; i < arr.size(); ++i) {
            pos[arr[i]].push_back(i);
        }
        try_bound = 20;
    }
    
    int get_occurrence(int num, int l, int r) {
        auto iter = pos.find(num);
        if (iter == pos.end()) {
            return 0;
        }
        const auto& vec = iter->second;
        auto iter_l = lower_bound(vec.begin(), vec.end(), l);
        if (iter_l == vec.end()) {
            return 0;
        }
        auto iter_r = upper_bound(vec.begin(), vec.end(), r);
        return iter_r - iter_l;
    }
    
    int get_random(int l, int r) {
        return rand() % (r - l + 1) + l;
    }
    
    int query(int left, int right, int threshold) {
        for (int i = 0; i < try_bound; ++i) {
            int elem = a[get_random(left, right)];
            if (get_occurrence(elem, left, right) >= threshold) {
                return elem;
            }
        }
        return -1;
    }
};

Trade-off:
This method is based on the fact that number of "popular" numbers (i.e. a number which occurs at least t times) cannot exceed n/t. Thus, if the threshold in a given query is not less than t, there is only n/t candidate "more than half" majorities.
We can design an algorithm to handle different queries with different methods. For the queries with threshold less than t, the length of interval [l, r] will also smaller than 2t, so we can simply use No.6 to find the "more than half" majority in O(t) time. For the queries with threshold more than t, we iterate through the "popular" numbers and use No.5 to check whether it is a "more than half" majority in [l, r]. This is solved in O((n/t) * log(n/t)) time, O(n/t) for the iteration and O(log(n/t)) for No.5. Thus, the total time complexity is the maximum of O(t) and O((n/t) * log(n/t)). We can do a trade-off by solving the equation t = (n/t) * log(n/t), but it is too difficult. However, we can simply set t as sqrt(n) to get a pretty good trade-off, and the time complexity will be O(sqrt(n) * log(n)).

Runtime: ~200 ms
Pre-calculation: O(n)
Query: O(sqrt(n) * log(n))

class MajorityChecker {
private:
    unordered_map<int, vector<int>> pos;
    unordered_set<int> popular;
    vector<int> a;
    int lookup_bound;
    
public:
    MajorityChecker(vector<int>& arr): a(arr) {
        for (int i = 0; i < arr.size(); ++i) {
            pos[arr[i]].push_back(i);
        }
        lookup_bound = round(sqrt(arr.size()));
        for (const auto& [key, value]: pos) {
            if (value.size() >= lookup_bound) {
                popular.insert(key);
            }
        }
    }
    
    int vote(int l, int r) {
        int target = a[l], occ = 1;
        for (int i = l + 1; i <= r; ++i) {
            if (a[i] == target) {
                ++occ;
            }
            else {
                --occ;
                if (occ < 0) {
                    target = a[i];
                    occ = 1;
                }
            }
        }
        int cnt = 0;
        for (int i = l; i <= r; ++i) {
            if (a[i] == target) {
                ++cnt;
            }
        }
        if (cnt * 2 > r - l + 1) {
            return target;
        }
        return -1;
    }
    
    int get_occurrence(int num, int l, int r) {
        auto iter = pos.find(num);
        if (iter == pos.end()) {
            return 0;
        }
        const auto& vec = iter->second;
        auto iter_l = lower_bound(vec.begin(), vec.end(), l);
        if (iter_l == vec.end()) {
            return 0;
        }
        auto iter_r = upper_bound(vec.begin(), vec.end(), r);
        return iter_r - iter_l;
    }
    
    int query(int left, int right, int threshold) {
        if (threshold <= lookup_bound) {
            int candidate = vote(left, right);
            if (candidate != -1 && get_occurrence(candidate, left, right) >= threshold) {
                return candidate;
            }
            return -1;
        }
        else {
            for (const int& elem: popular) {
                if (get_occurrence(elem, left, right) >= threshold) {
                    return elem;
                }
            }
            return -1;
        }
    }
};

Segment tree:
Segment tree is a perfect data structure for this problem because it can divide an interval into consecutive sub-intervals. The nodes in the segment tree store the "more than half" majority (if it exists) or -1 of the corresponding interval [l, r]. We use No.5 to merge the interval [l, mid] and [mid + 1, r] in the "build tree" process.
During the query process, we can search the interval [l, r] on the segment tree and get O(log(n)) sub-intervals. For each sub-interval, we use No.5 to check if it is the "more than half" majority of [l, r], which is another O(log(n)) time.

Runtime: ~200ms
Pre-calculation: O(n * log(n))
Query: O(log(n) * log(n))

class MajorityChecker {
private:
    unordered_map<int, vector<int>> pos;
    vector<int> tree;
    vector<int> a;
    
public:
    MajorityChecker(vector<int>& arr): a(arr) {
        for (int i = 0; i < arr.size(); ++i) {
            pos[arr[i]].push_back(i);
        }
        tree = vector<int>(arr.size() * 4, -1);
        build_tree(1, 0, arr.size() - 1);
    }
    
    void build_tree(int tree_pos, int l, int r) {
        if (l == r) {
            tree[tree_pos] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build_tree(tree_pos * 2, l, mid);
        build_tree(tree_pos * 2 + 1, mid + 1, r);
        if (tree[tree_pos * 2] != -1 && get_occurrence(tree[tree_pos * 2], l, r) * 2 > r - l + 1) {
            tree[tree_pos] = tree[tree_pos * 2];
        }
        else if (tree[tree_pos * 2 + 1] != -1 && get_occurrence(tree[tree_pos * 2 + 1], l, r) * 2 > r - l + 1) {
            tree[tree_pos] = tree[tree_pos * 2 + 1];
        }
    }
    
    pair<int, int> query(int tree_pos, int l, int r, int queryl, int queryr) {
        if (l > queryr || r < queryl) {
            return make_pair(-1, -1);
        }
        if (queryl <= l && r <= queryr) {
            if (tree[tree_pos] == -1) {
                return make_pair(-1, -1);
            }
            int occ = get_occurrence(tree[tree_pos], queryl, queryr);
            if (occ * 2 > queryr - queryl + 1) {
                return make_pair(tree[tree_pos], occ);
            }
            else {
                return make_pair(-1, -1);
            }
        }
        int mid = (l + r) >> 1;
        pair<int, int> res_l = query(tree_pos * 2, l, mid, queryl, queryr);
        if (res_l.first > -1) {
            return res_l;
        }
        pair<int, int> res_r = query(tree_pos * 2 + 1, mid + 1, r, queryl, queryr);
        if (res_r.first > -1) {
            return res_r;
        }
        return make_pair(-1, -1);
    }
    
    int get_occurrence(int num, int l, int r) {
        auto iter = pos.find(num);
        if (iter == pos.end()) {
            return 0;
        }
        const auto& vec = iter->second;
        auto iter_l = lower_bound(vec.begin(), vec.end(), l);
        if (iter_l == vec.end()) {
            return 0;
        }
        auto iter_r = upper_bound(vec.begin(), vec.end(), r);
        return iter_r - iter_l;
    }
    
    int query(int left, int right, int threshold) {
        pair<int, int> ans = query(1, 0, a.size() - 1, left, right);
        if (ans.second >= threshold) {
            return ans.first;
        }
        return -1;
    }
};

Bucket:
The bucket method also focus on splitting [l, r] into sub-intervals. We break the interval into t buckets with size n/t. We pre-calculate the "more than half" majority of each bucket by No.6. For a given query [l, r], we find the bucket id b_l and b_r which contains l and r. If b_l equals to b_r, it means the whole interval lies in one bucket, we can use No.6 to find the "more than half" majority in O(t) time. If b_l is not equal to b_r, we can divide the interval into [l, r_border(b_l)], b_{l+1}, ..., b_{r-1}, [l_border(b_r), r], where l_border and r_border represent the left and right border of a bucket. We find the "more than half" majority of complete buckets by the pre-calculation and the first & last sub-interval by No.6. We get no more than n/t candidates now and we check each by No.5 to find the "more than half" majority. The time complexity is O(t + (n/t) * log(t)), which is more than the previous O(t). Thus we come to the trade-off to minimize O(t + (n/t) * log(t)). We can set t as sqrt(n) to get a pretty good trade-off O(sqrt(n) * log(n)).

Runtime: ~400ms
Pre-calculation: O(n)
Query: O(sqrt(n) * log(n))

class MajorityChecker {
private:
    unordered_map<int, vector<int>> pos;
    vector<int> a;
    vector<int> bucket;
    int bucket_size;
    
    
public:
    MajorityChecker(vector<int>& arr): a(arr) {
        for (int i = 0; i < arr.size(); ++i) {
            pos[arr[i]].push_back(i);
        }
        bucket_size = round(sqrt(a.size()));
        int l = 0;
        while (l < a.size()) {
            int r = min(l + bucket_size, (int)a.size()) - 1;
            bucket.push_back(vote(l, r));
            l += bucket_size;
        }
    }
    
    int vote(int l, int r) {
        int target = a[l], occ = 1;
        for (int i = l + 1; i <= r; ++i) {
            if (a[i] == target) {
                ++occ;
            }
            else {
                --occ;
                if (occ < 0) {
                    target = a[i];
                    occ = 1;
                }
            }
        }
        int cnt = 0;
        for (int i = l; i <= r; ++i) {
            if (a[i] == target) {
                ++cnt;
            }
        }
        if (cnt * 2 > r - l + 1) {
            return target;
        }
        return -1;
    }
    
    int get_occurrence(int num, int l, int r) {
        auto iter = pos.find(num);
        if (iter == pos.end()) {
            return 0;
        }
        const auto& vec = iter->second;
        auto iter_l = lower_bound(vec.begin(), vec.end(), l);
        if (iter_l == vec.end()) {
            return 0;
        }
        auto iter_r = upper_bound(vec.begin(), vec.end(), r);
        return iter_r - iter_l;
    }
    
    int query(int left, int right, int threshold) {
        int bucket_l = left / bucket_size;
        int bucket_r = right / bucket_size;
        if (bucket_l == bucket_r) {
            int candidate = vote(left, right);
            if (candidate != -1 && get_occurrence(candidate, left, right) >= threshold) {
                return candidate;
            }
            return -1;
        }
        else {
            int vote_l = vote(left, (bucket_l + 1) * bucket_size - 1);
            int vote_r = vote(bucket_r * bucket_size, right);
            if (vote_l != -1 && get_occurrence(vote_l, left, right) >= threshold) {
                return vote_l;
            }
            if (vote_r != -1 && get_occurrence(vote_r, left, right) >= threshold) {
                return vote_r;
            }
            for (int i = bucket_l + 1; i < bucket_r; ++i) {
                int occ = get_occurrence(bucket[i], left, right);
                if (occ >= threshold) {
                    return bucket[i];
                }
            }
            return -1;
        }
    }
};

X. https://henryyangblogger.blogspot.com/2019/09/online-majority-element-in-subarray.html
3. segment tree
提到线段的题目，经典算法包括BIT和segment tree。 BIT多用于计算某一线段的元素之和，segment tree适用场景比较多。所以直觉上这个题目应该可以使用segment tree来解。这个解法还是用到了上面提到的二分搜索算法。

class MajorityChecker {
    int[] data, tree;
    Map<Integer, List<Integer>> map;
    public MajorityChecker(int[] arr) {
        this.data = arr;
        tree = new int[arr.length * 4];
        map = new HashMap<>();
        for(int i = 0; i < arr.length; i++) {
            if(!map.containsKey(arr[i])) {
                List<Integer> list = new ArrayList<>();
                map.put(arr[i], list);
            }
            map.get(arr[i]).add(i);
        }
        buildTree(0, arr.length-1, 0);
    }

    private void buildTree(int start, int end, int treeIdx) {
        if(start == end) {
            tree[treeIdx] = data[start];
            return;
        }

        int leftTreeIdx = treeIdx * 2 + 1, rightTreeIdx = treeIdx * 2 + 2;
        int mid = (start + end) / 2;
        buildTree(start, mid, leftTreeIdx);
        buildTree(mid+1, end, rightTreeIdx);

        if(tree[leftTreeIdx] != 0 && getOccurrence(tree[leftTreeIdx], start, end) * 2 > end - start + 1) {
            tree[treeIdx] = tree[leftTreeIdx];
        } else if(tree[rightTreeIdx] != 0 && getOccurrence(tree[rightTreeIdx], start, end) * 2 > end - start + 1) {
            tree[treeIdx] = tree[rightTreeIdx];
        }
    }

    private int[] query(int treeIdx, int left, int right, int targetL, int targetR) {
        if(left >= targetL && right <= targetR) {
            if(tree[treeIdx] == 0)
                return new int[]{0, 0};
            return new int[] {tree[treeIdx], getOccurrence(tree[treeIdx], targetL, targetR)};
        }

        int mid = (left + right) / 2, leftTreeIdx = treeIdx * 2 + 1, rightTreeIdx = treeIdx * 2 + 2;
        if(targetL > mid)
            return query(rightTreeIdx, mid+1, right, targetL, targetR);
        else if (targetR <= mid)
            return query(leftTreeIdx, left, mid, targetL, targetR);
        else {
            int[] ans1 = query(leftTreeIdx, left, mid, targetL, targetR);
            if(ans1[0] > 0 && ans1[1] * 2 > targetR - targetL + 1) return ans1;
            int[] ans2 = query(rightTreeIdx, mid+1, right, targetL, targetR);
            if(ans2[0] > 0) return ans2;
            return new int[] {0, 0};
        }
    }

    private int getOccurrence(int num, int left, int right) {
        List<Integer> list = map.get(num);
        int start = Collections.binarySearch(list, left);
        if(start < 0)   start = -(start + 1);
        int end = Collections.binarySearch(list, right);
        if(end < 0) end = -(end + 1) - 1;
        return end - start + 1;
    }

    public int query(int left, int right, int threshold) {
        int[] ans = query(0, 0, data.length-1, left, right);
        if(ans[1] >= threshold) return ans[0];
        return -1;
    }
}

这个算法初始化复杂度O(nlgn)。查询复杂度是O(lgnlgn) -> 我们会递归lgn次，每次都可能做一次binary search。
X.
https://leetcode.com/problems/online-majority-element-in-subarray/discuss/355848/Python-Binary-Search-%2B-Find-the-Majority-Element

Basic Idea

For each a in A, save its index of occurrence to list a2i[a].
When we want to get the exact occurrence of a in a range,
we can use binary search in a2i[a].

In the general good cases,
the numbers in A should be various,
each number should appear 1 time in average,
making the time complexity only O(1).

In the specific worst cases to this binary search solution,
the cases will be something like [1,2,1,2,1,2,1,2....],
making the binary search O(logN), (search in a list of length N / 2).

Now the only problem we need to solve,
is that how to find the majority element if it exists.

Solution 1: Random Pick

Random Pick number a from the range of query.
If there is a majority element,
we have >50% chance to get it for each pick.

Here I random pick 20 times,
because there are at most 10000 queries and 2^20 = 1048576 is much bigger than 10000.

If there is a majority element,
I only have 1/(2^20) possibility to miss it.
And we'll query at most 10000 times,
the expectation of fail times is about 0.01 time,
which sounds good.

I have used the same idea in 961. N-Repeated Element in Size 2N Array
The funny thing that, I was criticized this idea is misleading earlier this week.
Well thanks this guy and I recalled this idea immediately.

Complexity of function query:
Time O(20logN) for binary searching
Space O(1)

Actually O(20lgn) is the same as O(logNlogN).
We just need to pick k times and then let 2^k >> n.

Solution 2: Bucket

For each bucket of size sqrt(N),
find the majority candidate.

Then for any range of query,
there are at most sqrt(N) bucket involved,
and we can merge these candidates.

About the merger of majority,
you need first to know how to solve 169. Majority Element.
Then apply the idea of Boyer–Moore majority vote algorithm.

Complexity of function query:
Time O(sqrt(N))
Space O(1)

Solution 3: Segment Tree

For any range,
find the majority candidate of half range,
then merge the two majority candidates.

Complexity of function query:
Time O(logN)
Space O(1)

https://henryyangblogger.blogspot.com/2019/09/online-majority-element-in-subarray.html
2. 近似算法
假设我们要计算[l, r]中majority元素，如果这个数字存在，我们随机选择一个数字，那么这个数字就是majority元素的概率至少是1/2。如果我们重复20次，那么我们没有选择到majority元素的概率是 (1/2）^20，这个是非常小的概率。我们利用这个近似的算法来计算。那么问题变成了已知l,r且对于一个随机选择的val，怎么才能高效判断这个val是不是majority元素呢，我们可以二分搜索。代码如下：

class MajorityChecker {
    // store val -> set of idx
    Map<Integer, List<Integer>> map;
    Random random;
    int[] arr;
    public MajorityChecker(int[] arr) {
        map = new HashMap<>();
        random = new Random();
        for(int i = 0; i < arr.length; i++) {
            int val = arr[i];
            if(!map.containsKey(val)) {
                List<Integer> list = new ArrayList<>();
                map.put(val, list);
            }
            map.get(val).add(i);
        }
        this.arr = arr;
    }

    public int query(int left, int right, int threshold) {
        for(int times = 0; times < 20; times++) {
            int num = random.nextInt(right - left + 1);
            int idx = left + num;
            int val = arr[idx];
            int start = Collections.binarySearch(map.get(val), left);
            if(start < 0)   start = -(start + 1);
            int end = Collections.binarySearch(map.get(val), right);
            if(end < 0) end = -(end + 1) - 1;
            if(end - start + 1 >= threshold)
                return val;
        }
        return -1;
    }
}

X. https://yyzhou95.github.io/2019/08/lc-1157-online-majority-element-in-subarray/
* Boyer-Moore voting algorithm. * Traverse array twice. First time find the majority and second time count if it is satisfied with threshold. * Majority element in array will be at least 2/n times. * Therefore, use a count and a temp to traverse the array. * If current element in array is temp, count++, otherwise, count--. * And if count == 0, replace temp with current element in array. * The majority element will be the last element in temp when traverse completed.

https://www.acwing.com/solution/LeetCode/content/2450/

实现一个MajorityChecker的类，它应该具有下述几个 API：

• MajorityChecker(int[] arr)会用给定的数组 arr来构造一个 MajorityChecker 的实例。
• int query(int left, int right, int threshold)有这么几个参数：
  • 0 <= left <= right < arr.length 表示数组arr的子数组的长度。
  • 2 * threshold > right - left + 1，也就是说阈值 threshold始终比子序列长度的一半还要大。
    每次查询query(...)会返回在arr[left], arr[left+1], ..., arr[right]中至少出现阈值次数threshold的元素，如果不存在这样的元素，就返回-1。

(摩尔投票) 实例化: $O(1)$, 查询$O(n)$ (n为查询长度)

由于threshold严格大于查询区间长度的一半, 所以我们可以先用摩尔投票法求出majority element, 再遍历整个区间求出 majority element 个数并判断是否 >= threshold.

class MajorityChecker {
    int[] arr;

    public MajorityChecker(int[] arr) {
        this.arr = arr;
    }

    public int query(int left, int right, int threshold) {

        int res = -1;
        int count = 0;

        for (int i = left; i <= right; i++) {
            if (count == 0) {
                res = arr[i];
                count++;
            }
            else {
                if (arr[i] == res) count ++;
                else count--;
            }
        }

        count = 0;

        for (int i = left; i <= right; i++) {
            if (arr[i] == res) count++;
        }

        return count >= threshold ? res : -1;
    }
}




这个算是比较暴力的做法了。

更好的暴力算法可以考虑分块。

https://xindubawukong.github.io/2019/08/14/Leetcode-1157-Online-Majority-Element-In-Subarray/

给定一个长度为n的数组，m次查询，每次查询[l, r]区间内出现次数>=threshold的数是哪个。保证 threshold * 2 > r - l + 1 。强制在线。n, m <= 20000。

暴力做法：对于每个query，扫描l到r区间中的数，用hash表存下每个数的出现次数。时间复杂度O(n*m)。

这个题中要求的数是majority，也就是出现次数大于总次数的一半。这是一个很强的限制。我们可以发现，暴力算法处理慢的地方在于区间较长的时候，也就是threshold较大的时候。而threshold较大时，满足条件的数的个数就会很少！

于是可以取n−−√$\sqrt{n}$作为阈值，分两种情况讨论：

• 若threshold<n−−√$\sqrt{n}$，则区间长度<2n−−√$2\sqrt{n}$，按照暴力做法求解，每次询问时间复杂度O(n−−√$\sqrt{n}$)。
• 若threshold>n−−√$\sqrt{n}$，满足这样条件的数不超过nn√=n−−√$\frac{n}{\sqrt{n}}=\sqrt{n}$个。因此在开始时进行预处理，求出这n−−√$\sqrt{n}$个数，那么只需要在查询时知道每一个数在[l, r]中出现了多少次。我的方法是对每个数维护一个长度为n的前缀和数组，这样O(1)的时间即可得到其在[l, r]中的出现次数，每次询问的时间复杂度为O(n−−√$\sqrt{n}$)。

总时间复杂度O(nn−−√$n\sqrt{n}$)。代码如下：

vector<int> arr; vector<int> frequent; vector<vector<int>> sum; MajorityChecker(vector<int>& arr) { this->arr = arr; map<int, int> count; for (int x : arr) { count[x]++; } for (auto it = count.begin(); it != count.end(); it++) { if (it->second > 100) { frequent.push_back(it->first); } } sum.resize(frequent.size()); for (int i = 0; i < frequent.size(); i++) { int x = frequent[i]; sum[i].resize(arr.size()); for (int j = 0; j < arr.size(); j++) { if (x == arr[j]) { sum[i][j] = 1; } if (j > 0) { sum[i][j] += sum[i][j-1]; } } } } int work1(int left, int right, int threshold) { unordered_map<int, int> count; for (int i = left; i <= right; i++) { if (++count[arr[i]] >= threshold) { return arr[i]; } } return -1; } int work2(int left, int right, int threshold) { for (int i = 0; i < frequent.size(); i++) { int cnt = sum[i][right] - (left == 0 ? 0 : sum[i][left - 1]); if (cnt >= threshold) { return frequent[i]; } } return -1; } int query(int left, int right, int threshold) { if (threshold <= 100) { return work1(left, right, threshold); } else { return work2(left, right, threshold); } } };