区間と最頻値

2 secs 1024 MB

値 $x$ が区間 $[L,R]$ に何個含まれるかを高速に数える方法を考えます。

$A_{\max}$ を $\max{A_i}$ とします。

Fenwick Treeを $A_{\max}$ 個持てば $O(\log{A_{\max}})$ で数えることができますが、サイズが $10^3 \times 5 \times 10^5$ と巨大になりMLEします。

そこで、平方分割を用います。配列を長さ $\sqrt{N}$ のバケットの分割します。各バケット内で各数値が何回出現するかをFenwick Treeで管理します。

区間 $[L, R]$ が与えられた時、その範囲に含まれるバケットが完全に含まれる場合と一部だけ含まれる場合でそれぞれ数えます。

値の更新は、数列の更新とその要素が属するバケットの個数を更新すれば良いです。

最頻値は一部だけ含まれるバケットの数え上げるのに $O(\sqrt{N})$ 、完全に含まれるバケットの数え上げるのに $O(A_{\max}\log{\sqrt{N}})$ となり、合計で $O(\sqrt{N} + A_{\max}\log{\sqrt{N}})$ となります。

更新操作はFenwick Treeを使っているので $O(\log N)$ 時間で行えます。

解説