競技プログラミング用知識集積所

ABC442D - Swap and Range Sum

最終更新：2026年01月31日 03:24

sport_programming

- view

管理者のみ編集可

問題

B以下レベルの内容は省略

高速に和を求めるといえば、とりあえず思い浮かぶのは累積和。
通常なら累積和は中身の変更にO(N)かかるため、中身が固定のものにしか使えない。

しかし今回は隣接項を入れ替えるだけなので更新が1ヶ所で済む。
つまり、a.at(i)がxでa.at(i+1)がyだった場合、この2つの入れ替えではi番目までの和がy-x増えるだけである。
そのため、通常の累積和でO(N+Q)で非常に高速に解ける。

Fenwick木※なら、「中身を自由に変更できる」「和を高速に出せる」が両立できるため、普通に解ける。
O((N+Q)*logN)に悪化するが、十分間に合う。
（解答例略）

タグ：

累積和

競技プログラミング用知識集積所

記事メニュー

最近更新されたスレッド

人気記事ランキング

最近更新されたページ

急上昇Wikiランキング

急上昇中のWikiランキングです。今注目を集めている話題をチェックしてみよう！

新規Wikiランキング

最近作成されたWikiのアクセスランキングです。見るだけでなく加筆してみよう！

人気Wikiランキング

atwikiでよく見られているWikiのランキングです。新しい情報を発見してみよう！

全体ページランキング

最近アクセスの多かったページランキングです。話題のページを見に行こう！