数列 \(A_k, A_{k+1},\dots, A_r\) の平均値が \(m\) 以上であることと、\(A_k-m+A_{k+1}-m + \dots + A_r-m \geq 0\) であることは同値です。この性質を用いてこの問題を解きます。

\(k\) の値ごとに上記の性質を用いて二分探索をすることを考えます。この性質をそのまま使っても高速化は難しいので、この性質をより使いやすく言い換えます。

\(\displaystyle B_i = \sum_{j= 1}^{i} A_j\) とおいた数列 \(B\) を考えます。言い換えれば、\(B\) は \(A\) の累積和をとったものです。便利のため、\(B_0 = 0\) と決めておきます。

\(A_k-m+A_{k+1}-m + \dots + A_r-m \geq 0\) という条件は、 \(B\) を用いると \(B_r - rm - (B_{k-1} - (k-1)m) \geq 0\) として表せます。よって、\(k\) を固定したときの答えが \(m\) 以上であることは、次と同値です。

• \((B_{k-1} - (k-1)m) \leq B_r - rm\) を満たす \(r\) \((k \leq r \leq N)\) が少なくとも一つ存在する。すなわち、 \(k \leq r \leq N\) を満たす \(r\) に対する \(B_r - rm\) の最大値が \((B_{k-1} - (k-1)m)\) 以上である。

これは、次のクエリが高速に処理できれば十分です。

• 直線の集合 \(S\) に一次関数 \(B_r - rx\) を追加する。
• \(m\) が与えられたとき、\(S\) に含まれる一次関数それぞれに \(m\) を代入したときの最大値を求める。

これは、CHT によって処理できるクエリそのものです。今回の問題では傾きに単調性があるので、deque を用いた実装がうまくいきます(私は本番提出においてLuzhiled’s memoの実装 https://ei1333.github.io/luzhiled/snippets/structure/convex-hull-trick-add-monotone.html を利用しました）。計算量は全体で \(O(N \log^2N)\) となり、高速な言語ではACできます。