Minimum Frequency

この問題は、Mo's Algorithm を用いることで解くことができます。

区間 $[l, r]$ に対して答えを求められたとき、この区間の両端を追加、削除するときの処理を考えてみましょう。

まず、以下の配列を定義します。

$cnt[i] :$ 区間の中にある $i$ の個数
$reach[j] :$ 区間の中にある値の個数が $j$ であるような個数 (つまり、$cnt[i]$ = $j$ を満たす $i$ の個数)

そうすると、区間の両端の追加、削除は以下のように処理できます。

• $A_x$ を区間に追加する場合:

〇 区間の長さが $0$、または $cnt[A_x] = 0$ であった場合には $1$ が答えになる。
〇 $reach[cnt[A_x]]$ が $1$ であるかつ、答えが $cnt[A_x]$ と等しい場合は答えを $1$ 増加させる。

• $A_x$ を区間から削除する場合:

〇 削除したあとに区間の長さが $0$ になる場合は何も行わない。
〇 $cnt[A_x]$ が $2$ 以上であるかつ、答えが $cnt[A_x]$ と等しい場合は答えを $1$ 減少させる。
〇 $reach[cnt[A_x]]$ が $1$ であるかつ、$cnt[A_x]$ が $1$ である場合は、答えを $1 \leq reach[i]$ を満たす最小の $i$ に変更する (二分探索などを用いる)。

上記の処理を行った後に、$cnt$、$reach$ の更新を行うことでこの問題を解くことができます。

結果として、この問題を $O(N \sqrt{Q} \log N)$ で解くことができ、十分に高速です。