誤読

文字通りくそコード

数列の好きな範囲で大きいほうからk個のsumをO(1)で求める

追記;若干のタイトル詐欺が含まれています
追記2;これはメモリがすごい

WaveletMatrixをします。

解説をします。


まずWaveletを理解していない人は↓を読んでください。

これ見てからウェーブレット木の世界 | Preferred Research

これ読んでwww.scribd.com

上からk番目の値を求める操作を知ってるとイメージしやすそうなので上のに合わせて理解してください。




ARC074Dについて、某さんが上からk個のsumライブラリほしいみたいなことを言っていたので、書いてみたら書けた。

もやし先輩 on Twitter: "上からn個の和、WaveletでめっちゃくまくやればO(1)でできそう"


基本的にはk番目の値を求める操作と同じく潜っていきます(この場合は再帰でやっていきます)。その過程で、bit桁ごとに2のべき乗ずつ合算していくことで、最終的に全体のsumを出すイメージです。

図解

f:id:akihiro1001:20170523205307p:plain

↑な感じに行列があったとする。(オレンジ枠は緑枠の数字のnbit目、紫線は0,1のボーダー)

・n桁目のみでのsum

popc(立ってるビットの数) * 2^n であり、さらにこれに下位bitでのsumを加算する。(pow使うな)

・下位bitでのsumの出し方

本題の操作をmore_Kthsum(start, end, kth, n桁目)(kth >= 1)

ランクはrank(start,end, 0 or 1)で閉区間 (0か1のbit数)

n桁目の段階で、popc > kth の場合は、more_Kthsum(ボーダー + rank(0,s,1), ボーダー + rank(0,e,1), kth, n-1)であり、これはk番目の値を求めるときの操作とおんなじでまあ普通

そうでない場合がミソで、ナイーブな方法だと、

    more_Kthsum(rank(0,s,0), rank(0,e,0), kth - cou, n-1) + more_Kthsum(ボーダー + rank(0,s,1), ボーダー + rank(0,e,1), cou, n-1)

だが、ここで分岐してしまうのは計算量大爆発なのでなんとかして一本化したい。

注目すべきは→のほうで、範囲内の立ってるビット全てのsumを求めている。

ここで各桁において、立ってるbitの場所だけ 現在の桁以上の桁を削った後 の累積和をあらかじめ取っておくと、→が[end,start)の和に置き換わって計算量爆下げO(1)である。(↓図)

※現在の桁については n桁目のみでのsum で加算されてしまっているので、n桁目のみでのsumを出す時点で引くなりなんなり上手い感じに処理して

f:id:akihiro1001:20170523213754p:plain




例えば、

[2,7)で大きいほうから4個のsumを求めたいとする

・2bit目 popc = 3 kth = 4 popc <= kthなので、popc*2^2 + [2,7)の和 + more_Kthsum(0, 2, 1, 1)である。

・1bit目 popc = 2 kth = 1 popc > kthなので、popc*2^1 + moreKthsum(4, 6, 1, 0)

・0bit目 popc = 1 終わりなのでpopcを返す。

みたいな感じになります。


これでARC074Dを通しました(説明と若干違ったり、bitvectorがゴミ実装だったり)
Submission #1304562 - AtCoder Regular Contest 074 | AtCoder



備考:

WaveletMatrixの計算量O(1)を真に受けてはいけない。これは競プロ

これを利用したら小さいほうからk個もできます。(普通の累積和-大きいほうから(end-start)-k個 てきな)

(完)