[1] 関数合成による座標変化

移動は次のような規則です：\(x\) に \(\pm A[i]\) を足したあと，\([0,M]\) に clamp する．より細分化すれば，

• ADD：\(x\) に \(\pm A[i]\) を加える．
• CHMAX：\(x < 0\) ならば \(x := 0\) とする．
• CHMIN：\(M < x\) ならば \(x := M\) とする．

という関数からなります．このような関数を合成した結果は，次のような折れ線グラフで表される関数になります．

\(L,R\) はおおよそ

• \(x < L\) ならば，一度以上 CHMAX による変更対象となる．
• \(L\leq x\leq R\) ならば，CHMIN, CHMAX の対象となることはない．
• \(R < x\) ならば，一度以上 CHMIN による変更対象となる．

ということに対応します．ただし，合成結果が定数関数となる場合には，上の通りの意味に \(L,R\) を定められなくなります．そのような場合は任意の値を \(L=R\) として同じ規則で関数を記述できます．ただし後述する利得まで考えると，\(L=R\) とする場合にも，標準的な値が一意に定まります．

---

[2] 関数合成による利得

次に，初期座標 \(x\) に対して，得られる利得がどのように変化するかを考えます．

各移動で得られる利得は，\(A[i]\) から，clamp によって失われた移動量を引いたものです．この総利得を初期座標 \(x\) の関数として考えると，次のような折れ線グラフになります．

---

[3] 区間情報の \(O(1)\) データでの表現

[1][2] から，連続する移動操作について，初期座標 \(x\) に対する最終座標 \(f(x)\) と総利得 \(g(x)\) は，\(4\) つの整数

\[ (L,R,a,b) \]

を使って，次のように表すことができます．

\[ \begin{aligned} f(x)&= \begin{cases} L+a&(x<L),\\ x+a&(L\leq x\leq R),\\ R+a&(R<x), \end{cases},\\ g(x)&= \begin{cases} b-(L-x)&(x<L),\\ b&(L\leq x\leq R),\\ b-(x-R)&(R<x). \end{cases} \end{aligned} \]

この形の操作の合成がこの形で書けることを確かめて実際に実装する部分は，各自考えてみてください．

ここまで分かれば，この \(4\) 整数の組をモノイドとしてセグメント木に載せることで，セグメント木によって各クエリを \(O(\log N)\) 時間で処理できます．

---

[4] 解答例

• https://atcoder.jp/contests/aalc001/submissions/79891601

---

[5] 出題例

この問題で扱ったモノイド設計は何度か出題されています．日本では 「時をかけるビ太郎」（JOI 2018 / 2019 春合宿 Day3 問題3） が有名だと思います．