問題のリンク 本当はAtCoder Libraryを使って解くことが想定されている問題ですが、全く使わず解きました。 とりあえずなんでもいいので、遅延評価セグメント木の練習がしたかったので。 転倒数について まず、これがわからないと問題が解けません。 一応問…

セグメント木 セグメント木は、区間更新・区間上の最小値や和などをO(logn)で求めることができるデータ構造です。 セグメント木を理解するために役立つリソース かつっぱさんの動画です。説明が丁寧なのでわかりやすいです。 part1では、セグメント木の雰囲…

AOJの問題 区間和の取得は普通にできるが、更新は工夫が必要。 二分木は区間和を保持する。 また、遅延配列はINFで初期化しておこう。これはフラグとして利用する。(更新後の値として与えられる可能性があるため、0はフラグの値として使えない。) 更新すべき…

AOJの問題 RMQ and RUQ、RSQ and RAQからそれぞれ関数をとってきて貼り付けただけでは解けない。 加算の際に多少工夫が必要。 RMQ and RUQでは、2分木に区間和を保持していたが、今回必要なのは区間の最小値なので、それを保持する。 加算の際には、区間の全…

AOJの問題 RSQ&RAQのコードを少し変更しただけ。 区間更新の場合は加算と違って、普通に値を代入するだけでよい。 遅延配列の要素は、更新クエリで与えられることのない値で初期化すること。これがフラグの代わりになる。 実装 #include <bits/stdc++.h> using namespace st</bits/stdc++.h>…

AOJの問題 区間加算と区間和の取得を同時にこなさないといけないので、普通のセグメント木だと難しくなってくる。 そこで、遅延評価セグメント木を導入する。 普通のセグメント木では、区間更新にO(nlogn)だけかかってしまうが(区間更新・一点取得の場合は別…