I - 連続部分列/Subarray 解説
by 
maspy
[1] 解法 1：結合に必要な情報を追加する
結合に必要な情報を追加する考え方でモノイド設計します．この場合，例えば次のようにします．
状態 \((k,a,b)\) に，次の条件を満たす場合に選んだ要素の総和の最大値を持たせます．
- \(k\) 個の区間を選んでいる（\(1\leq k\leq 2\)）
- \(a\in \lbrace 0,1\rbrace\)：左端の要素を選んでいるかどうか
- \(b\in \lbrace 0,1\rbrace\)：右端の要素を選んでいるかどうか
フラグ \(a,b\) は区間 \(X,Y\) の情報を結合する際に，\(2\) つの隣り合う連続部分列が結合可能であるかを判別するために利用可能です．
この \(8\) 状態に加えて，セグメント木の単位元となる空列を扱うための is_empty フラグを持たせると，実装しやすいと思います．
[2] 解法 2：動的計画法を行列で表す
求値クエリひとつを，列の要素を左から順に処理する動的計画法として表します．連続部分列を高々 \(2\) 個選ぶことは，各要素を \(0,1,2,3,4\) の \(5\) 色で塗り，
- 色は左から右へ非減少になるようにする．
- 色 \(1,3\) の要素を選んだ要素とする．
ことと対応します．
この考え方により，求値クエリがひとつの場合は \(5\) 状態の dp で解くことができます．各要素を処理する dp 遷移は \(5\times 5\) の max-plus 行列で表せるため，各要素に対応する遷移行列をセグメント木にのせることで本問題を解くことができます．
dp の遷移を行列で表し，その行列をセグメント木にのせる考え方については，詳しくは 区間クエリのためのモノイド設計 第 7 章で解説されています．特に本問は，7.6 節で扱う 3 状態の dp を 5 状態に拡張したものと考えられます．
[3] 行列を使う場合の実装上の注意
状態数を定数 \(K\) として，セグメント木の各ノードに \(K\times K\) 行列を持たせることを考えます．このとき，実装によってパフォーマンスに大きな差が付くこともあります．
データの持ち方
セグメント木の各ノードに vector<vector<long long>> のようなデータ構造を持たせると，多数の動的メモリ確保やポインタ参照が発生します．\(K=5\) は固定なので，C++ では array<array<long long, K>, K> などの固定長配列を用いるとよいでしょう．
他の言語でも，固定長の配列を用いたり，配列を \(1\) 次元化することなどでパフォーマンスが改善する場合があります．
上三角性の利用
今回現れる行列はすべて上三角行列です．このことは上で述べた dp の状態設計で，状態 \(i\) から状態 \(j\) に遷移するのは \(i\leq j\) の場合に限られることに対応します．
したがって，行列積 \(z=xy\) を計算する際に，
- 通常の行列積：\(0\leq a,b,c < K\) に対して \(x[a][b]\) と \(y[b][c]\) から \(z[a][c]\) への計算を行う．
- 上三角の場合の行列積：\(0\leq a\leq b\leq c < K\) に対して \(x[a][b]\) と \(y[b][c]\) から \(z[a][c]\) への計算を行う．
のようにすることで，行列積に必要な演算回数を削減できます．例えば \(K=5\) の場合には，ループの回数が \(125\) 回から \(35\) 回へ減ります．
この削減が実際の実行時間にどの程度影響するかは，\(K\) の大きさや使用言語に加えて，行列の成分に対して行う演算の重さにも依存します．
本問では自明な対角成分や常に同一の成分などが他にもあり，より演算回数を削減することも可能です．そのような高速化の中でも，上三角性の利用は使える場面が多く，また手軽なのでおすすめです．
なお，上三角成分のみを保持することで，行列を格納するためのメモリ量も削減できます．ただし，添字管理などがやや複雑になるため，ここでは扱いません．