Mo法：質問の順番を変える

配列が更新されず、区間の端を1つ動かすと答えを更新できるなら、質問を並べ替えて移動回数を減らします。

言語：Python / 計算量：端移動 O(N²/B+QB)、ソート O(Q log Q)

前提：座標圧縮で値を順位に変える

考え方

1. 左端を長さBのブロックで分類します。
2. 同じブロック内は右端の順に処理。
3. 区間に入れる・外す関数を用意し、元の質問番号に答えを保存します。

具体例

種類数なら頻度が0→1で種類数+1、1→0で-1。和とは違って単純な累積和の引き算では求まりません。

実装

from collections import Counter
f=Counter();distinct=0
for x in [2,2,5]:
    if f[x]==0:distinct+=1
    f[x]+=1
f[2]-=1
if f[2]==0:distinct-=1
print(distinct)

注意する条件

オンラインで直ちに答える必要があると並べ替えられません。Pythonでは移動回数と関数呼び出しの定数倍にも注意。

確認問題

[2,2,5]から左の2を1つ取り除いた種類数は？

実装課題

N Q、配列 A、Q行の[l,r)。各区間の種類数。まず愚直解で確認する。N,Q≤200。大規模版ではMo法への置換が練習課題。

入力:
3 2
2 2 5
0 3
0 2
出力:
2
1

n,q=map(int,input().split());a=list(map(int,input().split()))
for _ in range(q):
    l,r=map(int,input().split());print(len(set(a[l:r])))

読了の記録・下書き・メモへ