問題
長さ $N$ の数列 $A$、$Q$ 個のクエリ $(l_i, r_i)$ に対して、区間 $[l_i, r_i]$ に含まれる要素の種類数を答えよ。
制約
$1 \le N, Q \le 10^5$
$1 \le A_i \le 10^5$
$1 \le l_i \le r_i \le N$
入出力例
入力例 1
7 3
1 2 1 3 2 1 4
1 5
3 7
2 4出力例 1
3
4
3ヒント (段階的開示)
ヒント1: 方向性
各クエリ独立で $O(NQ)$ は TLE。Mo's algorithm でソートすると全体 $O((N+Q)\sqrt{N})$。
ヒント2: アプローチ
現在の区間 $[\text{cur\_l}, \text{cur\_r}]$ を管理し、$l$・$r$ を 1 ずつ伸縮。$l$ をブロック幅 $\sqrt{N}$ で分け、同ブロック内では $r$ を昇順ソート。
ヒント3: 誘導
蛇腹ソート: 奇数ブロックは $r$ 降順、偶数ブロックは昇順。
模範解答 (Python)
import sys
from collections import defaultdict
input = sys.stdin.readline
def solve():
N, Q = map(int, input().split())
A = list(map(int, input().split()))
queries = []
for i in range(Q):
l, r = map(int, input().split())
queries.append((l - 1, r - 1, i))
block = max(1, int(N**0.5))
queries.sort(key=lambda q: (q[0] // block, q[1] if (q[0] // block) % 2 == 0 else -q[1]))
cnt = defaultdict(int)
distinct = 0
ans = [0] * Q
cur_l, cur_r = 0, -1
def add(idx):
nonlocal distinct
v = A[idx]
if cnt[v] == 0:
distinct += 1
cnt[v] += 1
def remove(idx):
nonlocal distinct
v = A[idx]
cnt[v] -= 1
if cnt[v] == 0:
distinct -= 1
for l, r, qi in queries:
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
ans[qi] = distinct
print('\n'.join(map(str, ans)))
solve()Step-by-Step 解説
1Mo's Algorithm の仕組み
現在の区間を管理し、目標クエリへ端点を 1 ずつ移動。
現在の区間を管理し、目標クエリへ端点を 1 ずつ移動。
2クエリのソート戦略
$l$ ブロック単位でグループ分け、同ブロック内は $r$ を蛇腹で並べる。
$l$ ブロック単位でグループ分け、同ブロック内は $r$ を蛇腹で並べる。
3add / remove
$cnt[v]$ 管理で 0→1 / 1→0 の遷移時に distinct を更新。
$cnt[v]$ 管理で 0→1 / 1→0 の遷移時に distinct を更新。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 0-indexed 変換し忘れ | 入力 1-indexed | l-1, r-1 |
| cur_r 初期値を 0 に | 初期区間が空なのに不整合 | cur_r = -1 |
| add/remove 順序ミス | $r$ 拡張は cur_r+1 してから add | 順序通りに記述 |
次のステップ
- 発展問題: 区間内の要素の分散
- オンラインなら平方分割・永続セグ木