コンテンツにスキップ

AALC001 J - Long Binary String

サイト
AtCoder
コンテスト
AALC001
問題
J - Long Binary String
難易度
-

長さ 101810^{18} の 0, 1 からなる文字列 SS があり、はじめはすべて 0 です。次の 2 種類のクエリを合計 QQ 個処理する問題です(1≤Q≤2×1051 \le Q \le 2 \times 10^5)。

  • 1 l r:Sl,…,SrS_l, \dots, S_r を反転する。
  • 2 l r:Sl,…,SrS_l, \dots, S_r に含まれる 1 の個数を出力する。

クエリを先読みして座標圧縮します。区間を 0 始まりの半開区間 [l−1,r)[l - 1, r) で表し、すべてのクエリの端点 l−1l - 1, rr を集めてソートし、重複を除いたものを v0<v1<⋯<vm−1v_0 < v_1 < \dots < v_{m-1} とします。すると、どのクエリの区間も小区間 [vj−1,vj)[v_{j-1}, v_j) をいくつか並べたものになります。また、各小区間の中の文字はつねにすべて同じように反転されます。

そこで、小区間 [vj−1,vj)[v_{j-1}, v_j) を 1 つの要素とする遅延評価セグメント木を作ります。各ノードには担当範囲の 0 の個数と 1 の個数を持たせます。はじめは 0 の個数が小区間の長さ vj−vj−1v_j - v_{j-1} で、1 の個数は 00 です。反転はこの 2 つを入れ替える作用で、2 回反転すると元に戻るので、作用の合成は XOR です。

全体の計算量は O(Qlog⁡Q)O(Q \log Q) です。

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] で viv_i、cp.id(x) で値 xx の番号を得ます。セグメント木の jj 番目の要素は小区間 [vj,vj+1)[v_j, v_{j+1}) なので、半開区間 [l−1,r)[l - 1, r) は要素の番号の範囲 [id(l−1),id(r))[\mathrm{id}(l - 1), \mathrm{id}(r)) に対応します。

acted_monoid::Rearrange<monoid::Sum<ll>, 2> は、和のモノイドを 2 つ並べた std::array に「成分の並べ替え」を作用させる作用付きモノイドです。成分 0 が 0 の個数、成分 1 が 1 の個数で、A::swap(0, 1) が反転の作用です。これを LazySegTree に渡しています。

使用ライブラリ:cpp_include@397a51d