\(f(A)\) を求める操作の見通しをよくします．

便利のため，\(y_0,y_{M+1}\) を考えることにします． \(y_0\) は常に \(0\) で，\(y_{M+1}\) は操作の度に必ず \(1\) 増えます．

\(y\) は常に広義単調増加です． そこで，\(y\) そのものではなくその差分を保持することを考えます．整数 \(i\) を \((y_{i+1}-y_i)\) 個含む多重集合 \(s\) によって \(y\) を表すことにします．

\(1\) 回の操作により \(s\) がどのように変化するか考えると，結局以下のようになります．

• \(s\) に \(A_i\) を \(2\) 個追加する．その後 \(s\) の最小値を \(1\) つ削除する．

これを最小費用流の問題として捉え直してみます．

頂点 \(S,T,V_1,\cdots,V_N\) を用意し，以下のような辺を貼ったグラフを考えます．

• \(S \to V_i\) に容量 \(2\)，コスト \(A_i\) の辺を貼る．
• \(V_i \to V_{i+1}\) に容量 \(\infty\)，コスト \(0\) の辺を貼る．
• \(V_i \to T\) に容量 \(1\)，コスト \(0\) の辺を貼る．

このグラフで \(S \to T\) の容量 \(N\) の最小費用流を流し，そのコストを \(c\) とおけば，\(f(x)=2 \times (\sum A_i)-c\) です．

\(A_i\) が変化する度に最小費用流を計算し直すことはできないので，最適なフローの差分に注目します．

今，ある \(A\) に対して最適なフローが求まっており，ここで \(A_p\) の値を変化させたとします．

このとき，今保持しているフローは最適解とは限りません． 具体的には，コストが負のサイクルが発生している場合，これを押し戻す必要があります． ところで，\(A_p\) が変化する前のグラフにはコストが負のサイクルは存在しません．つまり，押し戻すべきサイクルは，必ず \(S \to V_p\) 辺を(いずれかの向きで)通ることになります．

また，押し戻すサイクルは，必ず以下の \(2\) パターンのうちいずれかの形になります．

• いずれかの \(q\) に対して \(S \to V_p \to V_q \to S\) と流れるサイクル．
• いずれかの \(q\) に対して \(S \to V_q \to V_p \to S\) と流れるサイクル．

ここで，どの \(q\) を使うかを愚直に調べている時間はありません． そこで，この部分を高速化することにします．

まず \(1\) 種類目のサイクルについて考えます． \(V_q \to S\) と押し流すには，\(S \to V_q\) の現在の流量が \(1\) 以上であるべきです．そこでまずこれを満たす \(q\) の集合を保持しておくことにします． この集合の中で，\(q\) として選べる値の範囲は区間になっています． まず \(p<q\) であれば必ず使えます． また \(q<p\) であっても，\(V_q \to V_{q+1} \to \cdots \to V_p\) の流量がすべて \(1\) 以上なら押し流せます．

\(V_i \to V_{i+1}\) の流量を Segment Tree で管理しておくことで，この \(q\) の区間を \(O(\log N)\) 時間で計算できます． そして区間の中で最も押し戻すコストの小さい \(q\) を探してくればよいです． これも Segment Tree で行えます．より具体的には，\(S \to V_q\) の流量が \(0\) の場合は押し戻すコストとして \(\infty\) を保持するようにすればよいです．

\(2\) 種類目のサイクルも同様に Segment Tree を作ることで高速に調べることができます． そして，コストが負のサイクルを見つけた場合は実際に押し戻しを行いますが，その結果生じた流量の変化も，すべて Segment Tree のクエリとして処理できます． 特に，\(V_i \to V_{i+1}\) 辺の流量の変化は区間加算クエリになります．

\(S \to V_p\) 辺の容量は \(2\) なので，押し戻しも高々 \(2\) 回です． よって \(1\) クエリあたり \(O(\log N)\) 時間で変化を計算できます．

以上をまとめると，この問題は全体計算量 \(O((N+Q) \log N)\) で解けます．

解答例