[1] 絶対値の最大化

まず，絶対値を最大化する問題では，次の変形が有用な場合があります．

\[ |x|=\max(x,-x) \]

今回の問題では，答えは次の値として解釈することができます．

• \((A_L, \ldots, A_R)\) の長さ \(3\) 以上の部分列 \((B_0,B_1, \ldots, B_{M-1})\) を選び，
• さらに符号 \(s_0,s_1,\ldots,s_{M-3}\) （\(s_i\in \lbrace -1,1\rbrace\)）を選び，
• \(\sum_{k=0}^{M-3}s_k(B_k+2B_{k+1}+3B_{k+2})\) をスコアとしたとき，スコアとしてありうる最大値．

つまり，\(B_k + 2B_{k+1} + 3B_{k+2}\) の符号によらず，\(s_k\in \lbrace -1,1\rbrace\) を自由に選ぶことを認めます．

---

[2] dp による解法

まず列 \(A\) に対する問題を一度だけ解くことを考えましょう．

問題を部分列 \(B\) と，\(\pm 1\) からなる符号列 \((s_i)\) を選ぶ問題だと考えると，本問題は dp で解くことができます．\(s_i,B_i\) まで選んだ時点で，最後に選んだ \(2\) つの符号 \((s_{i-1},s_i)\) を状態として保持し，\(B_i\) までのスコアがすべて計算済みとなるようにします．

ただし，先頭や末尾付近での例外処理が必要で，それを踏まえると，例えば次のような \(10\) 状態を用意することになります．

• 開始前：まだ要素を選んでいないことに対応する \(1\) 状態．
• 開始直後：最初の \(s_i\) を選んだことに対応する \(2\) 状態．
• 通常状態：直近の \(s_i\) を \(2\) 個覚えている \(4\) 状態．
• 終了直前：最後の \(s_i\) を選んだあと，\(B_{i+1}\) まで選んだ状態に対応する \(2\) 状態．
• 終了状態：すべての \(s_i, B_i\) を選び終えたことに対応する \(1\) 状態

---

[3] セグメント木によるクエリ処理

この考え方により，求値クエリがひとつの場合は \(K=10\) 状態の dp で解くことができます．各要素を処理する dp 遷移は \(10\times 10\) の max-plus 行列で表せるため，各要素に対応する遷移行列をセグメント木にのせることで本問題を解くことができます．計算量は \(O(NK^3 + QK^3\log N)\) 時間です．

• 解答例：https://atcoder.jp/contests/aalc001/submissions/79886290

---

[4] 参考：求値クエリの高速化

求値クエリで最終的に必要なのは，参照するセグメント木のノードが保持している行列を \(M_1, \ldots, M_n\) とすると，行列積

\[ M_1M_2\cdots M_n \]

のひとつの成分だけです．ここで \(M_i\) はセグメント木の各ノードに格納されている \(K\times K\) 行列です．

よって答えを求めるには行列積そのものは不要で，行ベクトル \(v\) について

\[ vM_1M_2\cdots M_n \]

が求められれば十分です．この積を

\[ v(M_1M_2\cdots M_n) \]

と計算するのではなく，左から順に

\[ (\cdots((vM_1)M_2)\cdots M_n) \]

と計算してみましょう．すると，求値クエリは「行列と行列の積」ではなく「ベクトルと行列の積」の反復によって処理できます．このことにより，求値クエリの計算量を \(O(K^3\log N)\) 時間から \(O(K^2\log N)\) 時間へと改善することが可能です．

\(K\) が本問より大きく，クエリの大部分が求値クエリであるなど，このような高速化が問われた事例は過去にもあります．

ただし，AtCoder Library の標準的な API ではこのような高速化はできません．

• 解答例：https://atcoder.jp/contests/aalc001/submissions/79887193