Overview

This is a problem where we need to efficiently determine the number of distinct flower varieties within a given interval, for multiple queries.

Analysis

In this problem, the row of flower beds is fixed, and each flower bed is assigned a variety number \(P_i\). For each query, we need to answer the number of distinct varieties that appear within the specified interval \([L, R]\).

A naive approach would be to scan the elements within the interval for each query and count the number of varieties by managing occurrences using a set or similar data structure. However, the time complexity of this method is \(O(N)\) per query in the worst case, resulting in \(O(QN)\) overall. Under the constraints \(N, Q \leq 10^5\), this requires up to \(10^{10}\) operations, which will result in TLE.

Instead, by using Mo’s Algorithm, we can efficiently process multiple interval queries. This algorithm sorts queries in a specific order and updates the answer by gradually shifting the current interval, thereby reducing the overall computation.

Algorithm

The basic idea of Mo’s Algorithm is to process queries efficiently while maintaining the “answer for the current interval” in a reusable form.

Algorithm Flow:

1. Sort the queries based on a block size \(B = \sqrt{N}\) as follows:
   • Group by the quotient of dividing the left endpoint \(L\) by \(B\) (block number)
   • Within the same block, sort by right endpoint \(R\) in ascending order
2. Starting from an initial interval (e.g., an empty set at first), update the answer by “expanding and shrinking” the interval in the order of queries
3. Use an array (or dictionary) to manage variety counts as the interval expands and shrinks, tracking the number of occurrences
4. Manage the number of distinct varieties as the number of keys with a count of 1 or more

Concrete Example:

For example, suppose the flower variety sequence is [1, 2, 1, 3] and the query is [1, 3] (1-indexed). This refers to the interval [1, 2, 1], and the distinct varieties are {1, 2}, which gives 2 types.

Complexity

• Time complexity: \(O((N + Q) \sqrt{N})\)
• Space complexity: \(O(N + Q)\)

This accounts for the fact that each element addition/removal is \(O(1)\), along with the time required for sorting queries and moving the interval endpoints.

Implementation Notes

• Note that the interval is converted to 0-indexed (the input is 1-indexed)

• The add() and remove() functions must correctly manage both the counts and the number of distinct varieties

• When sorting queries, use (L // BLOCK_SIZE, R) as the key

• Use an answers array to record the results, and output them later in the original query order

  Source Code

import sys
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    Q = int(data[1])
    P = list(map(int, data[2:2+N]))
    
    queries = []
    for i in range(Q):
        L = int(data[2 + N + 2*i]) - 1  # 0-indexed
        R = int(data[2 + N + 2*i + 1]) - 1
        queries.append((L, R, i))
    
    # Mo's algorithm
    BLOCK_SIZE = int(N**0.5) + 1
    queries.sort(key=lambda x: (x[0] // BLOCK_SIZE, x[1]))
    
    # Initialize
    count = defaultdict(int)
    distinct = 0
    answers = [0] * Q
    
    current_l = 0
    current_r = -1
    
    def add(idx):
        nonlocal distinct
        count[P[idx]] += 1
        if count[P[idx]] == 1:
            distinct += 1
            
    def remove(idx):
        nonlocal distinct
        count[P[idx]] -= 1
        if count[P[idx]] == 0:
            distinct -= 1
            
    for L, R, idx in queries:
        # Expand to the right
        while current_r < R:
            current_r += 1
            add(current_r)
        # Shrink from the right
        while current_r > R:
            remove(current_r)
            current_r -= 1
        # Expand to the left
        while current_l > L:
            current_l -= 1
            add(current_l)
        # Shrink from the left
        while current_l < L:
            remove(current_l)
            current_l += 1
            
        answers[idx] = distinct
        
    print('\n'.join(map(str, answers)))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.