AALC001 I - Subarray
- サイト
- AtCoder
- コンテスト
- AALC001
- 問題
- I - Subarray
- 難易度
- -
長さ の整数列 に対して、次の 2 種類のクエリを合計 個処理する問題です(, )。
1 i x: を に変更する。2 l r: から、互いに重ならない空でない連続部分列を 個以上 個以下選ぶ。選んだ部分列の要素の総和の最大値を出力する。
連続部分列を 1 個選ぶ場合(最大部分配列問題)は、セグメント木の各ノードに「区間全体の和」「接頭辞の和の最大値」「接尾辞の和の最大値」「連続部分列の和の最大値」を持たせる方法が知られています。これを 2 個まで選べるように広げます。
ここで、長さ の連続部分列(和は )も選べることにします。すると「 個以上 個以下選ぶ」は「長さ も含めてちょうど 個選ぶ」と同じになり、個数の場合分けが要らなくなります。
選ぶ連続部分列の個数 ()と、区間の端に接する部分列があるかどうかで、次の 8 つの値を持たせます。いずれも和の最大値です。
| 値 | 左端から始まる部分列 | 右端で終わる部分列 |
|---|---|---|
| あり | あり | |
| あり | なくてもよい | |
| なくてもよい | あり | |
| なくてもよい | なくてもよい |
「左端から始まる部分列」は長さ でもよいので、たとえば は空の接頭辞も含めた接頭辞の和の最大値です。 で左端から始まり右端で終わるのは区間全体なので、 は区間全体の和です。
隣り合う区間 (左)と (右)をつなげるときは、境目をまたぐ部分列があるかどうかで場合分けします。またぐ部分列は、 の右端で終わる部分列と の左端から始まる部分列がつながったものです。そのため、個数は 側と 側の合計より 1 少なくなります。たとえば は次の候補の最大値です。
- 境目をまたがない:、、
- 境目をまたぐ:、
ほかの値も同じように、「 側で左端の条件を満たし、 側で右端の条件を満たす」組み合わせを列挙すれば求まります。すべての部分列を長さ にすれば和は なので、 以外の値は 以上です。
全体の計算量は です。
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 では結果を (すべて長さ を選んだ場合)で初期化してから、chmax で候補を入れています。長さ のノードでは、区間全体である だけが で、ほかの値は長さ も選べるので です。
使用ライブラリ:cpp_include@402f0cf