数组子区间奇数频率元素和查询：求高效解决方案

Your current approach works correctly for small inputs, but it's way too slow for large datasets. The problem is that for every query, you're iterating through the entire subarray from L to R to count frequencies—this results in a time complexity of O(Q*N). When N and Q are in the range of 1e5, this will definitely time out on HackerEarth.

To fix this, we can use Mo's Algorithm (a.k.a. the Sqrt Decomposition for queries), which allows us to answer all range queries in O((N + Q) * sqrt(N)) time—this is efficient enough for large input sizes.

How Mo's Algorithm Works #

1. Offline Processing: We first read all queries, store them with their original index (so we can output results in the correct order later).
2. Sort Queries: We sort the queries based on the block their left endpoint falls into. For queries in the same block, we sort by the right endpoint (with an optional optimization: sort even blocks by ascending R and odd blocks by descending R to reduce pointer movement).
3. Sliding Window: We maintain a sliding window (curL, curR) and keep track of:
   • freq[]: The frequency of each element in the current window.
   • currentSum: The sum of elements multiplied by their frequency, but only for elements with an odd frequency in the current window.
4. Adjust Window: For each query, we expand/shrink the current window to match the query's L and R, updating freq and currentSum as we add/remove elements.
5. Store Results: After adjusting the window to the query's range, we save the currentSum as the result for that query.

Java Implementation #

import java.io.*;
import java.util.*;

public class OddFrequencySum {
    static class Query {
        int l, r, idx;
        Query(int l, int r, int idx) {
            this.l = l;
            this.r = r;
            this.idx = idx;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1]; // 1-based indexing to match query input
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int q = Integer.parseInt(br.readLine());
        Query[] queries = new Query[q];
        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            queries[i] = new Query(l, r, i);
        }

        // Mo's algorithm setup
        int blockSize = (int) Math.sqrt(n) + 1;
        // Sort queries with odd-even optimization to reduce pointer movement
        Arrays.sort(queries, (a, b) -> {
            if (a.l / blockSize != b.l / blockSize) {
                return Integer.compare(a.l / blockSize, b.l / blockSize);
            }
            return (a.l / blockSize % 2 == 0) ? Integer.compare(a.r, b.r) : Integer.compare(b.r, a.r);
        });

        long[] results = new long[q];
        int[] freq = new int[(int) 1e6 + 2]; // Adjust size based on max element value
        long currentSum = 0;
        int curL = 1, curR = 0;

        for (Query query : queries) {
            int L = query.l;
            int R = query.r;

            // Expand window to the left
            while (curL > L) {
                curL--;
                int x = arr[curL];
                int prevFreq = freq[x];
                freq[x]++;
                if (prevFreq % 2 == 0) {
                    currentSum += (long) x * freq[x];
                } else {
                    currentSum -= (long) x * prevFreq;
                }
            }

            // Expand window to the right
            while (curR < R) {
                curR++;
                int x = arr[curR];
                int prevFreq = freq[x];
                freq[x]++;
                if (prevFreq % 2 == 0) {
                    currentSum += (long) x * freq[x];
                } else {
                    currentSum -= (long) x * prevFreq;
                }
            }

            // Shrink window from the left
            while (curL < L) {
                int x = arr[curL];
                int prevFreq = freq[x];
                freq[x]--;
                if (prevFreq % 2 == 1) {
                    currentSum -= (long) x * prevFreq;
                } else {
                    currentSum += (long) x * freq[x];
                }
                curL++;
            }

            // Shrink window from the right
            while (curR > R) {
                int x = arr[curR];
                int prevFreq = freq[x];
                freq[x]--;
                if (prevFreq % 2 == 1) {
                    currentSum -= (long) x * prevFreq;
                } else {
                    currentSum += (long) x * freq[x];
                }
                curR--;
            }

            results[query.idx] = currentSum;
        }

        // Output results in original query order
        for (long res : results) {
            pw.print(res + " ");
        }
        pw.flush();
        pw.close();
        br.close();
    }
}

Key Notes #

• 1-based Indexing: We use 1-based indexing for the array to match the query input format (L and R are 1-based).
• Frequency Array Size: Adjust the size of the freq array based on the maximum possible value of elements in the input. If elements can be negative, add an offset (e.g., 1e6) to shift values to non-negative indices.
• Fast I/O: Using BufferedReader and PrintWriter instead of Scanner is critical for handling large input sizes efficiently—Scanner is significantly slower for big datasets.
• Odd-Even Optimization: Sorting even blocks by ascending R and odd blocks by descending R reduces the number of right pointer movements, speeding up the algorithm further.

Why This Works #

When adding an element:

• If its previous frequency was even, it now becomes odd—so we add the total sum of this element in the current window (x * new frequency) to currentSum.
• If its previous frequency was odd, it now becomes even—so we subtract the old total sum (x * previous frequency) from currentSum.

When removing an element:

• If its previous frequency was odd, it now becomes even—subtract the old total sum from currentSum.
• If its previous frequency was even, it now becomes odd—add the new total sum to currentSum.

This ensures currentSum always holds exactly the value we need: the sum of elements multiplied by their frequency for all elements with an odd frequency in the current window.

内容的提问来源于stack exchange，提问作者Vrijendra Singh