コンテンツにスキップ

AALC001 L - Swap between Arrays

サイト
AtCoder
コンテスト
AALC001
問題
L - Swap between Arrays
難易度
-

長さ NN の整数列 AA, BB, CC に対して、次の 4 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤1051 \le N, Q \le 10^5, −109≤Ai,Bi,Ci≤109-10^9 \le A_i, B_i, C_i \le 10^9)。

  • 1 l r:l≤k≤rl \le k \le r のすべての kk について、AkA_k と BkB_k を入れ替える。
  • 2 l r:同様に BkB_k と CkC_k を入れ替える。
  • 3 l r:同様に CkC_k と AkA_k を入れ替える。
  • 4 i:∑k=ijAk>0\sum_{k=i}^{j} A_k > 0 となる jj(i≤j≤Ni \le j \le N)の最小値を出力する。なければ N+1N + 1 を出力する。

まず、入れ替えがない場合のクエリ 4 を考えます。∑k=ijAk>0\sum_{k=i}^{j} A_k > 0 となる最小の jj は、「区間 [i,j][i, j] の接頭辞の和がすべて 00 以下である間、右に伸ばす」という二分探索で求まります。セグメント木の各ノードに区間の和と接頭辞の和の最大値を持たせれば、セグメント木上の二分探索(ACL の max_right に当たる操作)で O(log⁡N)O(\log N) で求まります。接頭辞の和の最大値は、区間 XX(左)と YY(右)について max⁡(preX,sumX+preY)\max(\mathrm{pre}^X, \mathrm{sum}^X + \mathrm{pre}^Y) で合成できます。

入れ替えに対応するために、AA, BB, CC の 3 本それぞれについて、和と接頭辞の和の最大値をノードに持たせます。区間内の AkA_k と BkB_k をすべて入れ替えると、ノードが持つ AA の値と BB の値もそのまま入れ替わります。そのため、入れ替えは「3 本の情報を並べ替える」作用として遅延評価セグメント木に載せられます。作用は (0,1,2)(0, 1, 2) の置換 ff で表し、新しい ii 本目には元の fif_i 本目の値が入るとします。作用 gg の後に ff を行うと、新しい ii 本目には元の gfig_{f_i} 本目の値が入るので、合成は (gf0,gf1,gf2)(g_{f_0}, g_{f_1}, g_{f_2}) です。

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

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) が値 xx の 1 要素を表します。max は空の接頭辞(和 00)も含めた接頭辞の和の最大値なので、単位元では 00 になります。acted_monoid::Rearrange<M, 3> は、これを 3 つ並べた std::array に「成分の並べ替え」を作用させる作用付きモノイドで、A::swap(i, j) が成分 ii と jj を入れ替える作用です。入力は AA, BB, CC の順に 1 本ずつ読み、kk 番目の要素の成分 0, 1, 2 に入れています。LazySegTree の max_right は ACL と同じ仕様です。

max_right(i - 1, f) は、0 始まりの半開区間 [i−1,r′)[i - 1, r') の接頭辞の和がすべて 00 以下となる最大の r′r' を返します。0 始まりで r′r' 番目(1 始まりで r′+1r' + 1 番目)の要素まで足すと初めて和が正になるので、答えは r′+1r' + 1 です。r′=Nr' = N のときは N+1N + 1 になり、「存在しない」場合の出力とも一致します。

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