解説

クエリ問題であるので、クエリ無しで解くことを考えましょう。

ある値 $T$ が達成できるかどうかを考えます。

この時,、

$b _ {0} = a _ {0} - T$

$c _ {0} = T$

としていいです。

そうすると、

$b _ {i + 1} = b _ {i} + a _ {i + 1} - a _ {i}$

$c _ {i + 1} = c _ {i}$

$b _ {i + 1} = b _ {i}$

$c _ {i + 1} = c _ {i} - (a _ {i} - a _ {i + 1})$

とすればいいことに気づきます。

よって、最大値のみ注目すればいいので、 $b _ {n - 1} \leq T$ が達成できれば大丈夫です。

これは、

$b _ {0} + (a _ {i + 1} - a _ {i}の正の部分の和) \leq T$

が満たされることであり、 $b _ {0} = a _ {0} - T$ なので、

$T \geq (a _ {0} + (a _ {i+1} - a _ {i}の正の部分の和)) / 2$

となり、クエリ無しは解けました。

クエリは区間加算ですが、差分に注目するとただの2点更新にほかなりません

よって、特にデータ構造を用いず、 $(a _ {0} + (a _ {i+1} - a _ {i}の正の部分の和)) / 2$ が $O(1)$ で求めることができます

全体の計算量は $O(n + q)$ です

提出コード