ishikado https://blog.hatena.ne.jp/ishikado/ ishikadoのアルゴリズム勉強録 https://ishikado.hatenadiary.org/ xorの演算はビットごとに独立に行えるので、ビットごとにデータ構造を用意して、クエリの処理を行う。 ここで必要なのは ある範囲のビットを反転する ある範囲において１であるビットの数を数える の２種類の演算を処理するデータ構造を定義すること。範囲の集約処理なのでSegmentTreeを用いるとうまくいく。 範囲の値の和は、SegmentTreeの各ノードに、子ノードの値の和を持つことによって計算可能。 ではある範囲のビットを反転する操作はどのように行うか？ このために、各ノードが反転しているかどうかのフラグを導入する。 範囲のビット反転を行うとき、完全にクエリ領域に含まれる領域は、フラグを反転す… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fishikado.hatenadiary.org%2Fentry%2F20130303%2F1362272708" title="Codeforces Round #149 E - ishikadoのアルゴリズム勉強録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2013-03-03 10:05:08 rich https://ishikado.hatenadiary.org/entry/20130303/1362272708 1.0 100%