Overview

Given an array of \(N\) elements, we need to answer \(Q\) queries, each asking how many distinct values are contained within a specified range \([L, R]\). This is a classic problem known as the “Range Distinct Elements Query,” and it can be solved efficiently using an “offline query” technique where queries are read in advance and processed together.

Analysis

Naive Approach

For each query, one could scan the elements in the range \([L, R]\) and count the number of distinct values using a data structure such as a set. However, this method takes up to \(O(N)\) time per query, resulting in \(O(NQ)\) overall. Given the constraints \(N, Q \leq 10^5\), this would require approximately \(10^{10}\) operations in the worst case, which will not fit within the time limit (TLE).

Hint for an Efficient Approach

The key insight of this problem is: “When a value appears multiple times within a range, we only need to count the rightmost occurrence (the one with the largest index).”

For example, if the array is [1, 2, 1, 3] and the range is \([1, 3]\) (1-indexed), the value 1 appears at indices 1 and 3. When focusing up to the right endpoint \(R=3\), we can ignore the 1 at index 1 and mark only the 1 at index 3 as “counted toward the distinct count,” and the result remains the same.

To leverage this “fix the right endpoint” idea, an offline query technique that sorts queries in ascending order of the right endpoint \(R\) is effective.

Algorithm

1. Sort the queries: Sort all queries \((L_i, R_i)\) in ascending order of the right endpoint \(R_i\).
2. Prepare the data structure: Prepare a Binary Indexed Tree (BIT / Fenwick Tree) that supports efficient point updates and prefix sum queries.
3. Scan the array:
   • Advance index \(r\) from \(1\) to \(N\), performing the following operations:
   • If the current value \(P_r\) previously appeared at index \(prev\), subtract -1 at position \(prev\) in the BIT (removing the count at the old position).
   • Add +1 at the current position \(r\) in the BIT (marking the latest position as counted).
   • Update the latest occurrence position of value \(P_r\) to \(r\).
   • If the current \(r\) matches the right endpoint \(R_i\) of some query, compute the answer for that query. The answer is the range sum over \([L_i, R_i]\) in the BIT (i.e., query(R_i) - query(L_i - 1)).

With this method, the BIT maintains a state where only the “latest occurrence position” of each value has a 1. Therefore, by taking the sum over the interval \([L, R]\), we can correctly count the number of distinct values whose latest occurrence falls within that range.

Complexity

• Time complexity: \(O((N + Q) \log N + Q \log Q)\)
  • Sorting the queries takes \(O(Q \log Q)\).
  • Scanning the array \(N\) times and answering \(Q\) queries each involve BIT operations (\(O(\log N)\)), giving \(O((N + Q) \log N)\) overall.
• Space complexity: \(O(N + Q)\)
  • The array \(P\), BIT, stored queries, and the array (or hash map) recording the last occurrence position of each value use \(O(N + Q)\) memory.

Implementation Notes

• Offline processing: Since queries are sorted for processing, we need to preserve the original order (in the code, the original index i is stored as (r, l, i)).

• Fast I/O: Since \(N, Q\) can be large, in Python it is common to use sys.stdin.read().split() and sys.stdout.write to speed up input and output.

• BIT indexing: The BIT is typically implemented with 1-indexing, so care must be taken when converting from the array’s 0-indexed representation.

  Source Code

import sys

def solve():
    # 入力の高速化
    input = sys.stdin.read().split()
    if not input:
        return
    
    N = int(input[0])
    Q = int(input[1])
    P = list(map(int, input[2:N+2]))
    
    queries = []
    idx = N + 2
    for i in range(Q):
        l = int(input[idx])
        r = int(input[idx+1])
        queries.append((r, l, i))
        idx += 2
    
    # クエリを右端 R の昇順にソート
    queries.sort()
    
    # Binary Indexed Tree (Fenwick Tree) の実装
    bit = [0] * (N + 1)
    
    def update(i, delta):
        while i <= N:
            bit[i] += delta
            i += i & (-i)
            
    def query(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s

    ans = [0] * Q
    last_pos = {}
    current_r = 0
    
    for r, l, original_idx in queries:
        # 現在の右端 r まで BIT を更新
        while current_r < r:
            current_r += 1
            val = P[current_r - 1]
            if val in last_pos:
                # 以前に出現した位置のフラグを消す
                update(last_pos[val], -1)
            # 新しい出現位置にフラグを立てる
            update(current_r, 1)
            last_pos[val] = current_r
            
        # [L, R] の範囲にある種類の数は、BITの区間和 [L, R]
        ans[original_idx] = query(r) - query(l - 1)
        
    # 結果を出力
    sys.stdout.write('\n'.join(map(str, ans)) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.