SPOJ DQUERY问题：修改BIT解法实现区间去重求和查询

Hey there! Let's walk through how to fix and adapt that efficient solution for SPOJ's DQUERY so it correctly counts only unique elements in each range—plus why replacing -1 with 0 caused issues.

First, a quick recap of the original solution's core logic #

@kraskevich's approach uses an offline strategy with a Binary Indexed Tree (BIT) to handle range queries efficiently. Here's the key idea:

• We sort all queries by their right endpoint.
• We keep track of the last occurrence index of each element in the array.
• As we iterate through the array from left to right:
  1. If the current element has appeared before, we subtract 1 from its last occurrence position in the BIT (this "removes" the old occurrence from our count).
  2. We add 1 to the current position in the BIT (marking this as the active, latest occurrence of the element).
  3. Update the last occurrence index to the current position.
• When we reach the right endpoint of a query, we query the BIT for the sum from the query's left endpoint to the current right endpoint—this gives the number of unique elements in that range.

Why replacing -1 with 0 broke things #

The original solution initializes the last_occurrence array to -1 (a value smaller than the smallest valid index in the array, assuming 1-based indexing). This ensures that when we process the first occurrence of an element, we skip the "subtract 1" step (since -1 isn't a valid position in the BIT).

If you replaced -1 with 0, here's what goes wrong:

• For the first occurrence of an element, last_occurrence[x] is 0. If your array uses 1-based indexing, 0 isn't a valid position in the BIT, but your code would still try to subtract 1 from it. This corrupts the BIT's internal state, leading to incorrect prefix sums for subsequent queries.

The correct adjustments to make #

You don't need to change the core logic—just fix the handling of the initial last_occurrence values to avoid invalid BIT updates:

1. Keep last_occurrence initialized to -1 (for 1-based arrays) or a value that's definitely outside your array's index range. This ensures the first occurrence of any element skips the subtract step entirely.
2. If you must use 0 as the initial value (for some reason), add a check to only perform the subtract operation when last_occurrence[x] is a valid array index:

   // For 1-based arrays
   if (last_occurrence[x] >= 1) {
       updateBIT(last_occurrence[x], -1);
   }
   

   This way, the initial 0 value won't trigger an invalid update to the BIT.

Example to clarify #

Suppose we have the array [1, 2, 1, 3] (1-based):

• Processing index 1 (element 1): last_occurrence[1] is -1, so we skip subtracting, add 1 to index 1. BIT now has [0,1,0,0,0].
• Processing index 2 (element 2): last_occurrence[2] is -1, add 1 to index 2. BIT: [0,1,1,0,0].
• Processing index 3 (element 1): last_occurrence[1] is 1, so subtract 1 from index 1, add 1 to index 3. BIT: [0,0,1,1,0].
• Processing index 4 (element 3): last_occurrence[3] is -1, add 1 to index4. BIT: [0,0,1,1,1].

A query for [1,3] would sum indices 1-3: 0+1+1=2, which is correct (unique elements are 2 and 1).

Final notes #

The rest of @kraskevich's solution (sorting queries, processing in order, BIT sum queries) stays exactly the same. The only fix is ensuring we don't perform invalid BIT updates when handling the first occurrence of elements.

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