Overview

This problem asks us to efficiently compute the number of “distinct values (species numbers)” contained in each query interval \([L,R]\), under the constraints \(N,Q \le 10^5\).

Analysis

Key Insight

The “number of distinct species” in an interval can be determined by counting only the last occurrence position of each species within that interval.

For example, when \(P = [1,2,1,3,2]\) and we look up to \(R=5\): - Last occurrence of species 1: position 3 - Last occurrence of species 2: position 5 - Last occurrence of species 3: position 4

At this point, the number of distinct species in the interval \([L,5]\) equals “the number of species whose last occurrence position is at least \(L\).”

Why a Naive Solution Doesn’t Work

If we scan \([L,R]\) for each query and count using a set, it costs \(O((R-L+1))\) per query, and with up to \(Q\) queries this becomes \(O(NQ)\), which is on the order of \(10^{10}\) and will result in TLE.

How to Solve It

We sort the queries in ascending order of the right endpoint \(R\), then scan the array from left to right while updating the “last occurrence position” information. By managing these “last occurrence positions” as points on a 1-dimensional line and counting them via prefix sums, we can answer queries efficiently.

Algorithm

We use a Fenwick Tree (BIT) to achieve the following:

• Each position \(i\) in the BIT holds a value of \(1\) or \(0\):
  • “\(1\) if position \(i\) is the current last occurrence position of some species”
  • \(0\) otherwise
• Therefore, at any point (after processing up to some \(R\)), the number of distinct species in \([L,R]\) can be obtained as the range sum \(\sum_{i=L}^{R} \text{BIT}[i]\).

The processing steps are as follows:

1. Sort queries \((L_i,R_i)\) in ascending order of \(R_i\) (keeping the original index to restore the output order).
2. Iterate \(i=1\) to \(N\) in order (with \(i\) as the current position).
3. For the value \(v=P_i\), check the previous occurrence position prev = last[v]:
   • If prev > 0, that position is no longer the “last occurrence,” so perform add(prev, -1) on the BIT.
   • Mark the new last occurrence position by performing add(i, +1) on the BIT.
   • Update last[v] = i.
4. Process all queries whose right endpoint is exactly \(R=i\), and compute the answer as \(\text{BIT.range\_sum}(L, R)\).

Small Example

Processing \(P=[1,2,1,3,2]\) from left to right, at \(i=5\) the BIT has \(1\)s only at the last occurrence positions (3, 4, 5). Therefore, the answer for query \([2,5]\) is the sum over BIT positions \(2..5\), which gives \(3\) (species 1, 2, 3).

Complexity

• Time complexity: \(O\big((N+Q)\log N\big)\) (Each element update costs \(\log N\), and each query answer costs \(\log N\))
• Space complexity: \(O(N+Q)\) (BIT array, last array, query array, answer array)

Implementation Notes

• Sort queries by \(R\) and scan the array from left to right, answering “all queries that can be processed now” together (offline processing).

• last[v] stores “the position where species \(v\) last appeared.” When the same species appears again, subtract \(-1\) at the old position and add \(+1\) at the new position.

• Implementing the BIT as 1-indexed is standard and less error-prone (in the code, this is handled by adjusting with P=[0]+...).

• Since the input is large, reading all at once with sys.stdin.buffer.read() improves speed.

  Source Code

import sys

class Fenwick:
    __slots__ = ("n", "bit")
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        n = self.n
        bit = self.bit
        while i <= n:
            bit[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        bit = self.bit
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l - 1)

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)
    P = [0] + [next(it) for _ in range(N)]

    queries = []
    for idx in range(Q):
        l = next(it); r = next(it)
        queries.append((r, l, idx))
    queries.sort()

    fw = Fenwick(N)
    last = [0] * (N + 1)
    ans = [0] * Q

    qi = 0
    for i in range(1, N + 1):
        v = P[i]
        prev = last[v]
        if prev:
            fw.add(prev, -1)
        fw.add(i, 1)
        last[v] = i

        while qi < Q and queries[qi][0] == i:
            r, l, idx = queries[qi]
            ans[idx] = fw.range_sum(l, r)
            qi += 1

    sys.stdout.write("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.