Overview

This problem asks us to efficiently answer multiple queries about the number of distinct flower species in a flower bed interval \([L, R]\). We solve it using Mo’s algorithm (square root decomposition).

Analysis

Issues with the Naive Approach

If we scan the interval \([L, R]\) for each query to count the number of species, each query takes \(O(N)\) time. With \(Q\) queries, the total complexity becomes \(O(NQ)\). When \(N, Q\) are at most \(10^5\), this requires \(10^{10}\) operations, resulting in TLE (Time Limit Exceeded).

Key Observations

• Moving an endpoint of the interval by one position (adding/removing one element) can be done in \(O(1)\)
• By reordering queries cleverly, we can reduce the total number of endpoint movements
• This is a typical problem pattern where Mo’s algorithm is effective

Algorithm

Overview of Mo’s Algorithm

Mo’s algorithm is an offline algorithm for efficiently processing range queries.

1. Block Division: Divide the array into \(\sqrt{N}\) blocks
2. Query Sorting: Sort queries by “block number containing the left endpoint”, and within the same block, sort by “right endpoint”
3. Two-pointer-like Processing: Transform the current interval \([cur\_l, cur\_r]\) into the target interval \([l, r]\) while processing

Detailed Processing Flow

Current interval: [cur_l, cur_r] (initially empty)
Target interval: [l, r]

1. If cur_r < r, extend cur_r to the right while adding elements
2. If cur_l > l, extend cur_l to the left while adding elements
3. If cur_r > r, shrink cur_r to the left while removing elements
4. If cur_l < l, shrink cur_l to the right while removing elements

Explanation with Example

For array \(P = [1, 2, 1, 3, 2]\), to find the number of species in interval \([1, 3]\): - Flower bed 1: species 1, Flower bed 2: species 2, Flower bed 3: species 1 - The species that appear are {1, 2}, so the answer is 2

Complexity

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

  • Left endpoint movement: at most \(O(\sqrt{N})\) within the same block, \(O(Q)\) movements across blocks
  • Right endpoint movement: \(O(N)\) within each block, with \(O(\sqrt{N})\) blocks
  • Total: \(O(N\sqrt{N} + Q\sqrt{N})\)

• Space Complexity: \(O(N + Q)\)

  • Array \(P\): \(O(N)\)
  • Storing queries: \(O(Q)\)
  • Species count array: \(O(N)\)

Implementation Tips

1. Converting to 0-indexed: Since the input is 1-indexed, converting to 0-indexed for internal processing makes it easier to handle

2. Odd-even Block Optimization: For even-numbered blocks, sort by right endpoint in ascending order; for odd-numbered blocks, sort in descending order. This reduces the total movement distance of the right endpoint.

   if block % 2 == 0:
      return (block, r)
   else:
      return (block, -r)
   

3. Order of Expansion and Contraction:

   • Perform expansion first (handle cur_r < r and cur_l > l first)
   • If contraction is done first, you may create an empty interval

4. Using defaultdict: Using defaultdict(int) for species counting allows implementation without worrying about initialization

5. Restoring Answers: Since queries are processed in sorted order, keep track of the original query indices and output in the correct order at the end

   Source Code

import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    
    N, Q = map(int, input().split())
    P = list(map(int, input().split()))
    
    queries = []
    for i in range(Q):
        L, R = map(int, input().split())
        queries.append((L - 1, R - 1, i))  # 0-indexed
    
    # Mo's algorithm
    block_size = max(1, int(N ** 0.5))
    
    # Sort queries by (L // block_size, R) with optimization for odd/even blocks
    def mo_cmp(q):
        l, r, idx = q
        block = l // block_size
        if block % 2 == 0:
            return (block, r)
        else:
            return (block, -r)
    
    queries.sort(key=mo_cmp)
    
    # Count array and current distinct count
    count = defaultdict(int)
    distinct = 0
    
    def add(idx):
        nonlocal distinct
        val = P[idx]
        if count[val] == 0:
            distinct += 1
        count[val] += 1
    
    def remove(idx):
        nonlocal distinct
        val = P[idx]
        count[val] -= 1
        if count[val] == 0:
            distinct -= 1
    
    answers = [0] * Q
    cur_l, cur_r = 0, -1
    
    for l, r, idx in queries:
        # Expand/shrink the range [cur_l, cur_r] to [l, r]
        while cur_r < r:
            cur_r += 1
            add(cur_r)
        while cur_l > l:
            cur_l -= 1
            add(cur_l)
        while cur_r > r:
            remove(cur_r)
            cur_r -= 1
        while cur_l < l:
            remove(cur_l)
            cur_l += 1
        
        answers[idx] = distinct
    
    print('\n'.join(map(str, answers)))

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.