問題
長さ $N$ の整数列 $A = (a_1, \dots, a_N)$ が与えられる。$Q$ 個のクエリ $(l_i, r_i)$ に対し、区間 $[l_i, r_i]$ に含まれる相異なる値の総和を答えよ。
例: 区間が $[2, 2, 3, 3, 5]$ なら相異なる値 $\{2, 3, 5\}$ の和 $= 10$。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N, Q$ | $\le 2 \times 10^5$ | 列長・クエリ数 |
| $a_i$ | $1 \le a_i \le 10^9$ | 要座標圧縮 |
| $l_i, r_i$ | $1 \le l_i \le r_i \le N$ | 閉区間 |
入出力例
入力例1
6 3
2 2 3 3 5 2
1 5
3 6
1 6出力例1
10
10
10概念図: Mo's のブロック並べ替えと差分更新
ヒント
ヒント1（方向性）
オフラインで全クエリを平方分割順（Mo's）に並べ替え、区間端を1つずつ動かしながら「現在の相異なる値の和」を差分更新する。
ヒント2（アプローチ）
cnt[v] を区間内の出現回数とし、追加で 0→1 のとき cur += v、削除で 1→0 のとき cur -= v。値が大きいので座標圧縮して cnt を配列化する。
ヒント3（ほぼ答え）
block = int(N / max(1, Q**0.5)) + 1
queries.sort(key=lambda q: (q.l//block,
q.r if (q.l//block)%2==0 else -q.r))
def add(i):
v = comp[i]
if cnt[v]==0: cur += val[v]
cnt[v]+=1
def remove(i):
v = comp[i]; cnt[v]-=1
if cnt[v]==0: cur -= val[v]模範解答
import sys
input = sys.stdin.readline
def solve():
N, Q = map(int, input().split())
A = list(map(int, input().split()))
srt = sorted(set(A))
idx = {v: i for i, v in enumerate(srt)}
comp = [idx[a] for a in A]
val = srt
qs = []
for qi in range(Q):
l, r = map(int, input().split())
qs.append((l-1, r-1, qi))
block = max(1, int(N / max(1.0, Q**0.5)))
def key(q):
b = q[0] // block
return (b, q[1] if b % 2 == 0 else -q[1])
qs.sort(key=key)
cnt = [0] * len(srt)
cur = 0
ans = [0] * Q
cl, cr = 0, -1
for l, r, qi in qs:
while cr < r:
cr += 1; c = comp[cr]
if cnt[c] == 0: cur += val[c]
cnt[c] += 1
while cl > l:
cl -= 1; c = comp[cl]
if cnt[c] == 0: cur += val[c]
cnt[c] += 1
while cr > r:
c = comp[cr]; cnt[c] -= 1
if cnt[c] == 0: cur -= val[c]
cr -= 1
while cl < l:
c = comp[cl]; cnt[c] -= 1
if cnt[c] == 0: cur -= val[c]
cl += 1
ans[qi] = cur
sys.stdout.write('\n'.join(map(str, ans)) + '\n')
solve()計算量: $O((N+Q)\sqrt N)$ 時間、$O(N)$ 空間。
Step-by-Step 解説
Step 1: 座標圧縮
$a_i \le 10^9$ なので cnt を直接配列化できない。ソート済みユニーク値へ圧縮し、val[c] で元の値を復元する。
Step 2: Mo's のソート順
ブロック幅 $\approx N/\sqrt Q$。左端のブロック番号を第一キー、右端を第二キーとし、奇偶で右端の昇降を反転する zigzag で定数倍を削減。
Step 3: add / remove の差分
| 遷移 | 操作 |
|---|---|
| $\text{cnt}[v]: 0 \to 1$ | cur += val[v] |
| $\text{cnt}[v]: 1 \to 0$ | cur -= val[v] |
Step 4: ポインタ移動順序
拡張（cr++ / cl--）を先、縮小（cr-- / cl++）を後に行い、区間が空を跨ぐときの一時的な負出現を防ぐ。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| cnt を値そのもので確保 | 値域 $10^9$ で MLE | 座標圧縮して圧縮値でカウント |
| 拡張と縮小の順序ミス | ポインタ交差で不整合 | 拡大 → 縮小の順 |
| zigzag ソート未適用 | 右端が往復し TLE | 奇偶で右端キー反転 |
次のステップ
- 発展問題: 区間 distinct 個数を BIT オフラインで $O((N+Q)\log N)$
- 発展問題: 更新付き区間 distinct 和（Mo's with Updates・$O(Q^{5/3})$）
自己評価
理解度: / /
自分の回答:
気づき・メモ: