AALC001 L - Swap between Arrays
- サイト
- AtCoder
- コンテスト
- AALC001
- 問題
- L - Swap between Arrays
- 難易度
- -
長さ の整数列 , , に対して、次の 4 種類のクエリを合計 個処理する問題です(, )。
1 l r: のすべての について、 と を入れ替える。2 l r:同様に と を入れ替える。3 l r:同様に と を入れ替える。4 i: となる ()の最小値を出力する。なければ を出力する。
まず、入れ替えがない場合のクエリ 4 を考えます。 となる最小の は、「区間 の接頭辞の和がすべて 以下である間、右に伸ばす」という二分探索で求まります。セグメント木の各ノードに区間の和と接頭辞の和の最大値を持たせれば、セグメント木上の二分探索(ACL の max_right に当たる操作)で で求まります。接頭辞の和の最大値は、区間 (左)と (右)について で合成できます。
入れ替えに対応するために、, , の 3 本それぞれについて、和と接頭辞の和の最大値をノードに持たせます。区間内の と をすべて入れ替えると、ノードが持つ の値と の値もそのまま入れ替わります。そのため、入れ替えは「3 本の情報を並べ替える」作用として遅延評価セグメント木に載せられます。作用は の置換 で表し、新しい 本目には元の 本目の値が入るとします。作用 の後に を行うと、新しい 本目には元の 本目の値が入るので、合成は です。
全体の計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/data_structures/lazy-segtree.hpp"
void solve() { using M = monoid::PrefixSumMax<ll>; using A = acted_monoid::Rearrange<M, 3>; LL(N, Q); vec<A::S> init(N); rep(j, 3) rep(i, N) { LL(x); init[i][j] = M::S(x); } LazySegTree<A> seg(init); rep(Q) { LL(q); if (q == 1) { LL(l, r); seg.apply(l - 1, r, A::swap(0, 1)); } else if (q == 2) { LL(l, r); seg.apply(l - 1, r, A::swap(1, 2)); } else if (q == 3) { LL(l, r); seg.apply(l - 1, r, A::swap(0, 2)); } else { LL(i); print(1 + seg.max_right(i - 1, [](const auto &p) { return p[0].max <= 0; })); } }}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}monoid::PrefixSumMax<ll> は区間の和 sum と接頭辞の和の最大値 max をもつモノイドで、M::S(x) が値 の 1 要素を表します。max は空の接頭辞(和 )も含めた接頭辞の和の最大値なので、単位元では になります。acted_monoid::Rearrange<M, 3> は、これを 3 つ並べた std::array に「成分の並べ替え」を作用させる作用付きモノイドで、A::swap(i, j) が成分 と を入れ替える作用です。入力は , , の順に 1 本ずつ読み、 番目の要素の成分 0, 1, 2 に入れています。LazySegTree の max_right は ACL と同じ仕様です。
max_right(i - 1, f) は、0 始まりの半開区間 の接頭辞の和がすべて 以下となる最大の を返します。0 始まりで 番目(1 始まりで 番目)の要素まで足すと初めて和が正になるので、答えは です。 のときは になり、「存在しない」場合の出力とも一致します。
使用ライブラリ:cpp_include@397a51d