AALC001 J - Long Binary String
- サイト
- AtCoder
- コンテスト
- AALC001
- 問題
- J - Long Binary String
- 難易度
- -
長さ の 0, 1 からなる文字列 があり、はじめはすべて 0 です。次の 2 種類のクエリを合計 個処理する問題です()。
1 l r: を反転する。2 l r: に含まれる1の個数を出力する。
クエリを先読みして座標圧縮します。区間を 0 始まりの半開区間 で表し、すべてのクエリの端点 , を集めてソートし、重複を除いたものを とします。すると、どのクエリの区間も小区間 をいくつか並べたものになります。また、各小区間の中の文字はつねにすべて同じように反転されます。
そこで、小区間 を 1 つの要素とする遅延評価セグメント木を作ります。各ノードには担当範囲の 0 の個数と 1 の個数を持たせます。はじめは 0 の個数が小区間の長さ で、1 の個数は です。反転はこの 2 つを入れ替える作用で、2 回反転すると元に戻るので、作用の合成は XOR です。
全体の計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/data_structures/lazy-segtree.hpp"#include "shogo-library/utility/compress.hpp"
void solve() { LL(Q); VAL(qlr, Q, 3); Compress<ll> cp; for (auto &[q, l, r] : qlr) { l--; cp.add(l); cp.add(r); } cp.build(); using A = acted_monoid::Rearrange<monoid::Sum<ll>, 2>; vec<A::S> init; init.reserve(cp.size() - 1); rep(i, 1, cp.size()) { init.push_back({cp[i] - cp[i - 1], 0}); } LazySegTree<A> seg(init); for (auto [q, l, r] : qlr) { if (q == 1) { seg.apply(cp.id(l), cp.id(r), A::swap(0, 1)); } else { print(seg.prod(cp.id(l), cp.id(r))[1]); } }}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}VAL(qlr, Q, 3) で、クエリを std::array<ll, 3> の配列として読み込んでいます。座標圧縮には Compress を使い、端点を add で登録して build した後、cp[i] で 、cp.id(x) で値 の番号を得ます。セグメント木の 番目の要素は小区間 なので、半開区間 は要素の番号の範囲 に対応します。
acted_monoid::Rearrange<monoid::Sum<ll>, 2> は、和のモノイドを 2 つ並べた std::array に「成分の並べ替え」を作用させる作用付きモノイドです。成分 0 が 0 の個数、成分 1 が 1 の個数で、A::swap(0, 1) が反転の作用です。これを LazySegTree に渡しています。
使用ライブラリ:cpp_include@397a51d