[yukicoder] No.925 紲星 Extra

スポンサーリンク

概要

問題文 →
公式解説 →
自分の提出 →

実装が易しめの平方分割解。あまり他の提出になさそうだったので一応書きます。

解法

列の平方分割により解きます。

数列 $A$ を、長さ $s$ の区間に区切ることにします。$n = \lceil N/s\rceil$ 個の区間に区切ります。各区間に対して、

  • その区間内の要素をすべてソートして得られる列
  • その列の累積和

を管理することにします。以下、クエリ処理について述べます。

変更クエリについては、変更した要素の属するバケットの情報を新しく作り直します。これは $O(s\log s)$ 時間で行えます。なお、ソート前後のインデックスの対応も管理しておけば、ここでのソートは $O(s)$ 時間でできます(変更した 1 要素を、左右にスワップしていけばよいです)。私の実装は $O(s\log s)$ 時間です。

中央値クエリは、二分探索により、$[L,R)$ 内の $x$ 以下の要素の個数や和を求める問題に帰着します。完全に $[L,R)$ に含まれている区間についてはソート列に対する二分探索を用いることで、二分探索の判定問題が $O(s + n\log s)$ 時間で解けます。

結局、クエリあたり $O(s\log s + (s + n\log n)\log A)$ 時間で解けることが分かりました。

$(s,n) = (\sqrt{N\log A}, \sqrt{N/\log A})$ 程度にとれば、この計算量は $O(\sqrt{N\log A}\log N)$ 程度になります。あまり余裕はありませんが、これで AC することができます。

なお、二分探索の $40$ 回のループを、これまで $A_i$ として現れたことのある $\log_2(N+Q)$ ループに削減することで、さらなる高速化が期待できます。

タイトルとURLをコピーしました