コンテンツにスキップ

AALC001 I - Subarray

サイト
AtCoder
コンテスト
AALC001
問題
I - Subarray
難易度
-

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

  • 1 i x:AiA_i を xx に変更する。
  • 2 l r:(Al,…,Ar)(A_l, \dots, A_r) から、互いに重ならない空でない連続部分列を 00 個以上 22 個以下選ぶ。選んだ部分列の要素の総和の最大値を出力する。

連続部分列を 1 個選ぶ場合(最大部分配列問題)は、セグメント木の各ノードに「区間全体の和」「接頭辞の和の最大値」「接尾辞の和の最大値」「連続部分列の和の最大値」を持たせる方法が知られています。これを 2 個まで選べるように広げます。

ここで、長さ 00 の連続部分列(和は 00)も選べることにします。すると「00 個以上 22 個以下選ぶ」は「長さ 00 も含めてちょうど 22 個選ぶ」と同じになり、個数の場合分けが要らなくなります。

選ぶ連続部分列の個数 kk(k=1,2k = 1, 2)と、区間の端に接する部分列があるかどうかで、次の 8 つの値を持たせます。いずれも和の最大値です。

値左端から始まる部分列右端で終わる部分列
lrk\mathrm{lr}_kありあり
lk\mathrm{l}_kありなくてもよい
rk\mathrm{r}_kなくてもよいあり
zk\mathrm{z}_kなくてもよいなくてもよい

「左端から始まる部分列」は長さ 00 でもよいので、たとえば l1\mathrm{l}_1 は空の接頭辞も含めた接頭辞の和の最大値です。k=1k = 1 で左端から始まり右端で終わるのは区間全体なので、lr1\mathrm{lr}_1 は区間全体の和です。

隣り合う区間 XX(左)と YY(右)をつなげるときは、境目をまたぐ部分列があるかどうかで場合分けします。またぐ部分列は、XX の右端で終わる部分列と YY の左端から始まる部分列がつながったものです。そのため、個数は XX 側と YY 側の合計より 1 少なくなります。たとえば z2\mathrm{z}_2 は次の候補の最大値です。

  • 境目をまたがない:z2X\mathrm{z}_2^X、z2Y\mathrm{z}_2^Y、z1X+z1Y\mathrm{z}_1^X + \mathrm{z}_1^Y
  • 境目をまたぐ:r2X+l1Y\mathrm{r}_2^X + \mathrm{l}_1^Y、r1X+l2Y\mathrm{r}_1^X + \mathrm{l}_2^Y

ほかの値も同じように、「XX 側で左端の条件を満たし、YY 側で右端の条件を満たす」組み合わせを列挙すれば求まります。すべての部分列を長さ 00 にすれば和は 00 なので、lr1\mathrm{lr}_1 以外の値は 00 以上です。

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

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
struct AALC0001I {
struct S {
ll lr1, l1, r1, z1, lr2, l2, r2, z2;
S() {
lr1 = l1 = r1 = z1 = lr2 = l2 = r2 = z2 = 0;
}
S(ll a) {
lr1 = a;
l1 = r1 = z1 = lr2 = l2 = r2 = z2 = max(a, 0LL);
}
ll ans() const {
ll res = 0;
chmax(res, lr1);
chmax(res, l1);
chmax(res, r1);
chmax(res, z1);
chmax(res, lr2);
chmax(res, l2);
chmax(res, r2);
chmax(res, z2);
return res;
}
};
static S op(const S &a, const S &b) {
S res{};
res.lr1 = a.lr1 + b.lr1;
chmax(res.l1, a.l1);
chmax(res.l1, a.lr1 + b.l1);
chmax(res.r1, b.r1);
chmax(res.r1, a.r1 + b.lr1);
chmax(res.z1, a.z1);
chmax(res.z1, b.z1);
chmax(res.z1, a.r1 + b.l1);
chmax(res.lr2, a.l1 + b.r1);
chmax(res.lr2, a.lr1 + b.lr2);
chmax(res.lr2, a.lr2 + b.lr1);
chmax(res.l2, a.l2);
chmax(res.l2, a.lr1 + b.l2);
chmax(res.l2, a.lr2 + b.l1);
chmax(res.l2, a.l1 + b.z1);
chmax(res.r2, b.r2);
chmax(res.r2, a.r2 + b.lr1);
chmax(res.r2, a.r1 + b.lr2);
chmax(res.r2, a.z1 + b.r1);
chmax(res.z2, a.z2);
chmax(res.z2, b.z2);
chmax(res.z2, a.z1 + b.z1);
chmax(res.z2, a.r2 + b.l1);
chmax(res.z2, a.r1 + b.l2);
return res;
}
static S e() { return S(); }
};
void solve() {
LL(N, Q);
VL(A, N);
vec<AALC0001I::S> init;
init.reserve(N);
rep(i, N)
init.emplace_back(A[i]);
SegTree<AALC0001I> seg(init);
rep(Q) {
LL(q);
if (q == 1) {
LL(i, x);
seg.set(i - 1, {x});
} else if (q == 2) {
LL(l, r);
print(seg.prod(l - 1, r).ans());
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

SegTree には、要素の型 S、演算 op、単位元 e をまとめた構造体を渡します。op では結果を 00(すべて長さ 00 を選んだ場合)で初期化してから、chmax で候補を入れています。長さ 11 のノードでは、区間全体である lr1\mathrm{lr}_1 だけが AiA_i で、ほかの値は長さ 00 も選べるので max⁡(Ai,0)\max(A_i, 0) です。

使用ライブラリ:cpp_include@402f0cf