Twilio's IT team is trying to send two new USB Cables to all the Software Engineers. The problem is that there are a lot of USB standards and they are mostly not compatible with each other. For this reason, the team has labeled all the n cables with a numerical tag. They come in a list of tags like tags=[0,1,2,...] where the i^th cable has the tags[i]. For example, if tags= [2,3,1,2], the cable number 2 would have the tag 3. Now we want to group them in pairs taking into account that they must be of the same type. The restrictions for grouping are: Two cables can be formed together if they have the same tag. A group is always formed by 2 cables. One cable can only be in one 1 or 0 groups. To do the most efficient distribution we want to create queries. A query has the form [left, right] and represents an interval in the list of cables. As a result of the query we want to retrieve the number of groups that can be formed. For example, if tags=[2,3,2,1] and the query=[1,3] we would take into consideration only the interval [2, 3, 2] and the number of groups would be 1 because we have two "2". The queries come in a list of q queries like [[l1, r1], [l2, r2]...q times]. They are all independent of each other. The result must be in a list of groups formed for each query [r1,r2...q times]. Function Description Complete the function countGroups in the editor. countGroups has the following parameters:

• int tags[n]: the tags of the cables
• int queries[q][2]: the queries in the form (l, r) Returns int[]: the number of groups that can be formed for each query

Constraints

• 1 ≤ n ≤ 10^5
• 1 ≤ tags[i] ≤ 10^9
• 1 ≤ q ≤ 10^5
• 1 ≤ l ≤ r ≤ n

Example 1

Input:

tags = [2, 3, 4, 2]
queries = [[1, 4], [3, 4]]

Output:

[1, 0]

Explanation:

• For the first query, all cables are considered. Cables 1 and 4 can be grouped as their tags are the same.
• The tag of the cable number 1 is 2 and the tag of the cable number 4 is also 2.
• There are no other group formations possible. So, the number of groups is 1.
• For the second query, cables 3 and 4 are considered, and their tags are [4, 2].
• The tag of the cable number 3 is 4 and the tag of the cable number 4 is 2.
• Since they are different, no groups can be formed. So, the number of groups is 0. Hence, the answer is [1, 0].

Example 2

Input:

tags = [2, 2, 2, 2]
queries = [[1, 4]]

Output:

[2]

Explanation:

• We only have 1 query, all cables are considered.
• The tag of the cable number 1 is 2, and the tag of the cable number 2 is also 2.
• The tag of the cable number 3 is 2, and the tag of the cable number 4 is also 2.
• There are no other group formations possible. So, the number of groups is 2. Hence, the answer is [2].

解法

区间内每个 tag 的出现次数 cnt[t]，能组成的对数为 cnt[t] // 2 之和。直接对每个查询 O(r-l+1) 计数即可(题目数据规模小)；若需更快可对每个 tag 用前缀计数 + 公式 (cnt_r - cnt_l) // 2。这里给出前缀计数版。时间复杂度 O(n + q · T)，T 为不同 tag 数。

from typing import List
from collections import defaultdict

def countGroups(tags: List[int], queries: List[List[int]]) -> List[int]:
    n = len(tags)
    pref = defaultdict(lambda: [0] * (n + 1))
    distinct = set(tags)
    for i, t in enumerate(tags):
        for d in distinct:
            pref[d][i + 1] = pref[d][i]
        pref[t][i + 1] += 1
    res = []
    for l, r in queries:
        total = 0
        for d in distinct:
            cnt = pref[d][r] - pref[d][l - 1]
            total += cnt // 2
        res.append(total)
    return res

class Solution {
    int[] countGroups(int[] tags, int[][] queries) {
        int n = tags.length;
        Map<Integer, int[]> pref = new HashMap<>();
        for (int t : tags) pref.computeIfAbsent(t, k -> new int[n + 1]);
        for (int i = 0; i < n; i++) {
            for (Map.Entry<Integer, int[]> e : pref.entrySet()) {
                e.getValue()[i + 1] = e.getValue()[i];
            }
            pref.get(tags[i])[i + 1]++;
        }
        int[] res = new int[queries.length];
        for (int q = 0; q < queries.length; q++) {
            int l = queries[q][0], r = queries[q][1];
            int total = 0;
            for (int[] arr : pref.values()) {
                int cnt = arr[r] - arr[l - 1];
                total += cnt / 2;
            }
            res[q] = total;
        }
        return res;
    }
}

class Solution {
public:
    vector<int> countGroups(vector<int>& tags, vector<vector<int>>& queries) {
        int n = tags.size();
        unordered_map<int, vector<int>> pref;
        for (int t : tags) if (!pref.count(t)) pref[t] = vector<int>(n + 1, 0);
        for (int i = 0; i < n; i++) {
            for (auto& [k, v] : pref) v[i + 1] = v[i];
            pref[tags[i]][i + 1]++;
        }
        vector<int> res;
        for (auto& q : queries) {
            int l = q[0], r = q[1];
            int total = 0;
            for (auto& [k, v] : pref) {
                int cnt = v[r] - v[l - 1];
                total += cnt / 2;
            }
            res.push_back(total);
        }
        return res;
    }
};

Given an array arr, we can rearrange it to form another array, let's call it rearranged_arr. The greatness of the array is defined as the number of indices i, 0 ≤ i arr[i]. That is, the element placed after rearrangement is greater than the initial value present at that index. Given the initial array arr, find the maximum possible greatness which can be achieved by some rearrangement of the array. Function Description Complete the function findMaximumGreatness in the editor. findMaximumGreatness has the following parameter:

• int arr[n]: an array of integers Returns int: the maximum possible greatness

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ arr[i] ≤ 10⁹