Consider an array of N colored elements where some colors may repeat. We need to support two operations efficiently: query the number of distinct colors in a given range [L, R], and update a single position to a new color. This problem, known as "Color/Queue Maintenance" on BZOJ, requires a careful balance between query and update operations.

Problem Constraints

With n, m ≤ 10000 and color values up to 10^6, we need a solution that handles both operations reasonably fast. A pure segment tree approach fails because tracking distinct elements in a range isn't easily composable. This leads us to a block decomposition strategy.

Core Data Structures

The solution maintains three key arrays to enable efficient queries and updates:

cnt[block][color]: Cumulative frequency table where cnt[i][c] stores how many times color c appears in all elements from the start up to block i. This allows O(1) retrieval of any color's frequency within any block range.

distinct[blockL][blockR]: Precomputed value representing the number of distinct colors appearing in the inclusive range from blockL to blockR. This is the primary structure for answering queries.

colorMap[original]: Coordinate compression mapping original color values to compact indices [1, m], reducing space requirements from 10^6 to approximately n.

Discretization

Since color values can reach 10^6 but only n colors are actually present (plus potential new colors during updates), we compress all values to a manageable range:

void compressColors() {
    vector<int> allValues(arr, arr + n);
    sort(allValues.begin(), allValues.end());
    int uniqCount = unique(allValues.begin(), allValues.end()) - allValues.begin();
    for (int i = 0; i < n; i++) {
        arr[i] = lower_bound(allValues.begin(), allValues.end(), arr[i]) - allValues.begin() + 1;
    }
    for (int i = 1; i <= uniqCount; i++) {
        colorMap[allValues[i-1]] = i;
    }
    currentColorCount = uniqCount;
}

Block Initialization

Seting the block size appropriately is crucial. After extensive testing, a fixed block size of 1000 works well for the given constraints. The initialization phase builds both the frequency table and the distinct color table:

void buildBlocks() {
    blockSize = 1000;
    blockCount = (n - 1) / blockSize + 1;
    
    // Set block boundaries
    for (int i = 1; i <= blockCount; i++) {
        blockStart[i] = blockEnd[i-1] + 1;
        blockEnd[i] = blockStart[i] + blockSize - 1;
    }
    blockEnd[blockCount] = n;
    
    // Build frequency tables per block
    for (int i = 1; i <= blockCount; i++) {
        for (int j = blockStart[i]; j <= blockEnd[i]; j++) {
            blockId[j] = i;
            freq[i][arr[j]]++;
        }
        for (int c = 1; c <= currentColorCount; c++) {
            freq[i][c] += freq[i-1][c];
        }
    }
    
    // Precompute distinct counts for all block pairs
    for (int i = 1; i <= blockCount; i++) {
        for (int j = i; j <= blockCount; j++) {
            distinct[i][j] = distinct[i][j-1];
            for (int k = blockStart[j]; k <= blockEnd[j]; k++) {
                int col = arr[k];
                if (getColorCount(i, j-1, col) == 0 && !seen[col]) {
                    seen[col] = true;
                    distinct[i][j]++;
                }
            }
            for (int k = blockStart[j]; k <= blockEnd[j]; k++) {
                seen[arr[k]] = false;
            }
        }
    }
}

Query Operation

For a query [l, r], we handle three cases:

1. When both endpoints fall in the same or adjacent blocks: scan directly (O(blockSize))

2. When l and r are in different blocks: combine precomputed data from middle blocks with edge scanning

int queryRange(int l, int r) {
    int result = 0;
    int leftBlock = blockId[l];
    int rightBlock = blockId[r];
    
    if (rightBlock - leftBlock <= 1) {
        for (int i = l; i <= r; i++) {
            if (!seen[arr[i]]) {
                seen[arr[i]] = true;
                result++;
            }
        }
        for (int i = l; i <= r; i++) {
            seen[arr[i]] = false;
        }
        return result;
    }
    
    result = distinct[leftBlock + 1][rightBlock - 1];
    
    for (int i = l; i <= blockEnd[leftBlock]; i++) {
        if (getColorCount(leftBlock + 1, rightBlock - 1, arr[i]) == 0 && !seen[arr[i]]) {
            seen[arr[i]] = true;
            result++;
        }
    }
    for (int i = blockStart[rightBlock]; i <= r; i++) {
        if (getColorCount(leftBlock + 1, rightBlock - 1, arr[i]) == 0 && !seen[arr[i]]) {
            seen[arr[i]] = true;
            result++;
        }
    }
    for (int i = l; i <= blockEnd[leftBlock]; i++) seen[arr[i]] = false;
    for (int i = blockStart[rightBlock]; i <= r; i++) seen[arr[i]] = false;
    
    return result;
}

Udpate Operation

Point updates require careful modification of both freq and distinct tables. The key insight is that changes only affect block pairs where the modified position's block is within the range.

Step 1: Handle new color values that don't yet exist in our compression map:

if (colorMap.find(newColor) == colorMap.end()) {
    colorMap[newColor] = ++currentColorCount;
}

Step 2: Update the distinct table based on whether the new color was absent and whether the old color becomes unique after removal:

int posBlock = blockId[position];
int oldColor = arr[position];
arr[position] = newColor;

// If new color wasn't present in this block, increment all affected block pairs
if (getColorCount(posBlock, posBlock, newColor) == 0) {
    for (int i = posBlock; i >= 1; i--) {
        for (int j = posBlock; j <= blockCount; j++) {
            if (getColorCount(i, j, newColor) > 0) break;
            distinct[i][j]++;
        }
    }
}

// If old color becomes unique (exactly one occurrence after change), decrement affected pairs
if (getColorCount(posBlock, posBlock, oldColor) == 1) {
    for (int i = posBlock; i >= 1; i--) {
        for (int j = posBlock; j <= blockCount; j++) {
            if (getColorCount(i, j, oldColor) != 1) break;
            distinct[i][j]--;
        }
    }
}

Step 3: Update the frequency tables:

for (int i = posBlock; i <= blockCount; i++) {
    freq[i][newColor]++;
    freq[i][oldColor]--;
}

Complexity Analysis

Preprocessing: O(n × blockCount + blockCount² × blockSize) which evaluates to approximately O(n√n) for the given constraints.

Query: O(blockSize) for edge cases, O(√n) for general cases due to scanning boundaries.

Update: O(blockCount²) in worst case, approximately O(n^(2/3)) when optimized.

Alternative Approach

An alternative solution uses Mo's algorithm with modifications (Mo's algorithm with updates). This approach achieves O((n+q)^(5/3)) time complexity by treating updates as an additional dimension and applying 3D block decomposition. While asymptotically faster, the block decomposition approach offers simpler implementation and reasonable constant factors for these problem constraints.

Implementation Notes

Careful attetnion to block size selection is important. Testing revealed that different block sizes (√n, n^(2/3), or fixed constants like 1000) produce varying results depending on the judge's time limits. The fixed 1000 block size provides consistent performance for n ≤ 20000.