解説 PDF の方法のほうが遥かに筋のよい方法ですが、せっかく全然違うやり方（クエリ平方分割 + 双対セグメント木）で解けたことですし、一筆執らせていただきます。

関数 \(\mathtt { dp }\) の定義と基本的な性質

\(t\) 回目の加算クエリ直後の時刻を \(t \ ( 0 \le t \le A )\) 、\(1\) 回目の加算クエリ直前の時刻を \(0\) と呼ぶことにします。時刻 \(t\) おける \(a _ i\) の値を \(a _ i ( t )\) とおき、\(0 \le l \le r \le A\) に対して \(\mathtt { dp } ^ 0 _ i ( l, r ), \ \mathtt { dp } ^ 1 _ i ( l, r ) \in \mathbb Z\) を

\[ \mathtt { dp } ^ 0 _ i ( l, r ) = \min _ { l \le t \le r } a _ i ( t ), \quad\mathtt { dp } ^ 1 _ i ( l, r ) = a _ i ( r ) - a _ i ( l ) \]

により定めます。さらに \(\mathtt { dp } ^ 0, \mathtt { dp } ^ 1\) を束ねて \(\mathtt { dp } _ i ( l, r ) = ( \mathtt { dp } ^ 0 _ i ( l, r ), \mathtt { dp } ^ 1 ( l, r ) )\) と書くことにして、ペア同士の結合的な演算 \(f: \mathbb Z ^ 2 \times \mathbb Z ^ 2 \rightarrow \mathbb Z ^ 2\) を

\[ f ( ( a, b ), ( c, d ) ) = ( \min \lbrace a, b + c \rbrace , \min \lbrace b, d \rbrace ) \]

で定義すると、\(0 \le l \le c \le r \le A\) に対して

\[ \mathtt { dp } _ i ( l, r ) = f \left ( \mathtt { dp } _ i ( l, c ), \mathtt { dp } _ i ( c, r ) \right ) \]

が成り立ちます。

クエリ平方分割による、最小値クエリの言い換え

最小値クエリで問われているものは \(\mathtt { dp } ^ 0 _ i ( l, r )\) 型の値ですが、これを予め全通り計算しておくことは難しいです。そこで更新クエリを \(C = \Theta \left ( \sqrt Q \right )\) 個ずつに切って、

\[ \mathtt { dp } _ i ( l, l + 1 ) \ \left ( l \in [ 0, A [ \right), \quad \mathtt { dp } _ i ( j C, ( j + 1 ) C ) \ \left ( j \in \left \lbrack 0, \left \lfloor \frac A C \right \rfloor \right \lbrack \right ) \]

型のもののみを前計算することを考えます。これは \(\Theta ( N \sqrt Q )\) 個の値ですから、計算が十分に速ければ前計算ができそうです。

双対セグメント木などによる高速な前計算

\(a ( t )\) の代わりに \(\mathtt { dp } \left ( \left \lfloor \frac t C \right \rfloor, t \right )\) を管理することを考えましょう。すると加算クエリは \(f\) による区間への作用になるわけですが、これは双対セグメント木や遅延セグメント木などで実現できます。

以上により、全体で \(O \left ( (N + Q) \left ( \lg N + \sqrt Q \right ) \right )\) 時間で解くことができました。