求支持三类多重集查询（查询1最频繁）且单查询复杂度≤O(√N)的算法

Alright, let's tackle this problem head-on—since query type 1 is the most frequent, our design will prioritize optimizing it while ensuring all operations stay at O(√N) complexity or better. Here's a practical, efficient approach using a combination of hash tables and sqrt decomposition (blocking):

We'll use three key components to handle all operations smoothly:

1. num_to_freq Hash Map: A dictionary that maps each integer in the multiset to its current frequency. This gives O(1) time for lookups, updates, and deletions.
2. freq_to_nums Sorted Collections: For each frequency value, we maintain a sorted set (in descending order) of integers that have that frequency. This lets us quickly grab the largest integer for any given frequency.
3. Sqrt-Decomposed Frequency Blocks: We group frequency values into blocks of size roughly √N (where N is the current size of the multiset). Each block keeps track of the total number of integers across all frequencies in the block. This allows us to quickly locate which block contains the k-th smallest frequency.

Query Type 1: Find the Largest Integer with the k-th Smallest Frequency #

This is our priority operation, so we optimize it for speed:

1. Locate the target block: Iterate through each frequency block, accumulating the total number of integers in each block. Stop when the accumulated count is ≥ k—this means the k-th smallest frequency is in this block.
2. Find the exact frequency: Within the target block, iterate through frequencies in ascending order, accumulating the number of integers for each frequency. Stop when the accumulated count reaches k. This gives us the target frequency f.
3. Fetch the largest integer: Look up freq_to_nums[f] (the sorted set for frequency f) and take the first element (since we sorted in descending order—this is the largest integer with frequency f).

Example Walkthrough #

For the multiset {1,2,2,2,3,3} and k=3:

• num_to_freq = {1:1, 2:3, 3:2}
• freq_to_nums = {1: {1}, 2: {3}, 3: {2}}
• Blocks (size √6 ≈ 2): Block 1 contains frequencies 1,2 (total integers: 1+1=2), Block 2 contains frequency 3 (total integers:1)
• Accumulate block totals: 2 < 3, so move to Block 2. The accumulated count hits 3 here.
• Within Block 2, the frequency is 3. The largest integer in freq_to_nums[3] is 2—this is our answer.

Query Type 2: Add an Integer x #

1. Check num_to_freq for x's current frequency f (default to 0 if x isn't present).
2. If f > 0:
   • Remove x from freq_to_nums[f]. If the set becomes empty, delete the frequency key f from freq_to_nums.
   • Update the corresponding frequency block's total count by subtracting 1.
3. Update x's frequency to f+1:
   • Add x to freq_to_nums[f+1] (create the set if it doesn't exist).
   • Update the corresponding frequency block's total count by adding 1.
4. Update num_to_freq to reflect x's new frequency (or add x to the map if it was new).

Query Type 3: Delete an Integer x #

1. Get x's current frequency f from num_to_freq (we assume the input is valid, so x exists in the multiset).
2. Remove x from freq_to_nums[f]. If the set becomes empty, delete the frequency key f from freq_to_nums.
3. Update the corresponding frequency block's total count by subtracting 1.
4. If f-1 > 0:
   • Add x to freq_to_nums[f-1] (create the set if it doesn't exist).
   • Update the corresponding frequency block's total count by adding 1.
   • Update num_to_freq[x] to f-1.
5. If f-1 == 0:
   • Delete x from num_to_freq entirely.

• Query Type 1: Locating the block takes O(√N) time, finding the exact frequency takes O(√N) time, and fetching the largest integer is O(1) (from the sorted set). Total: O(√N).
• Query Type 2/3: Hash map operations are O(1). Sorted set insertions/deletions take O(log S) time (where S is the number of integers with that frequency—log S ≤ log N). Updating block counts is O(1). Since log N grows slower than √N, these operations are O(√N) or better.

This design ensures all queries meet the required complexity constraints, with query type 1 optimized for its high frequency of use.

内容的提问来源于stack exchange，提问作者Frou-Frou Fox