まずクエリなしのときを解きます． 次のような解き方が存在します．

• \(B_i\) を昇順にソートし，\(b_i = - \sum_{i \leq j < N} B_j\ (0 \leq i \leq N)\) とする． 各 \(0 \leq k \leq N\) について，\((A_i\) の Top \(k\) の和 \()+b_{N-k}\) を計算し，その max が答えになる．

これは，列 \(b\) に対して plus-max convolution を行っていると解釈できます． これを更にひねると，以下のような操作で答えを求めることができるとわかります．

• まず，列 \(b\) を上記のように初期化する． その後，各 \(A_i\) について以下の操作を行う． なおここで，操作を行う \(A_i\) の順番が任意で良い (ソートされている必要がない) ことに注意せよ．

• 現在の列 \(b\) の長さを \(k+1\) とする． 各 \(0 \leq j < k\) について同時に \(b_j = \max(b_j+A_i,b_{j+1})\) とし，\(b_k\) を削除する．

• \(N\) 回の操作のあと，\(b_0\) だけが残り，これが答えになる．

なお，各操作のあとで，列 \(b\) が常に下に凸であることが確認できます．

この解法をもとに，クエリが全部先読みできる場合の問題を解きます．

時系列 segtree を作り，葉を \(t=0,1,\cdots,Q\) に対応させます． 各 AtCoder 社員について，対応する区間にその id (\(1\) から \(N+Q\) までの番号だと思って良い)を push します． segtree の各ノードに id の列が置かれることになります．

列 \(b\) を持って segtree 上で dfs を行いましょう．

まず segtree の根には，\(b_i = - \sum_{i \leq j < N} B_j\) とした列 \(b\) を持って入ります． その後，根に置かれている id のリストを \(i_1,i_2,\cdots\) として，\(b\) に対して各 \(a_{i_j}\) で更新を走らせます． こうして得た \(b\) を持って，左右の子に潜り，同様の操作を繰り返せばよいです．

この解法の計算量を評価します． まず，各 segtree node について，その node 上の id 列を強さ順にソートしてやることにします． \(b\) の更新は愚直にやると \(O(|a| \times |b|)\) ですが，\(b\) が常に下凸であることを用い，差分列を管理することにすれば，\(O(|a|+|b|)\) での更新が可能です．

各 node での \(O(|a|+|b|)\) の合計が \(O((N+Q) \log Q)\) になることが示せます． まず \(O(|a|)\) のパートは簡単に抑えられます． \(O(|b|)\) のパートが非自明ですが，これは任意のnodeに対して，「\(|b| \leq \) その node の部分木内に id を置いた社員の数」が成立するため，これも結局 \(O((N+Q) \log Q)\) で抑えられることになります．

最後に，オンラインクエリに対応する方法を解説します． 基本的には先読みできるときと似たようなことをやります． ただし，ある社員が入社したとき，それがいつ解雇されるかわからないので，「対応する区間に push」という操作ができません． そこで，それぞれの社員について，まず最初は無期限に雇用されると思いこんで，segtree の node に社員 id を push しておくことにします．

dfs 中にある segtree の node \(x\) を訪れたとします． また，\(x\) の部分木内の葉の個数を \(s\) とします． \(x\) に置いてある社員 id のうち，すでに解雇が決まっているものは削除してよいです． その後，\(x\) の社員 id のうち，礼儀正しさが下位 \(s-1\) 人に入らないものは，\(x\) の部分木では常に使用することが確定します．そのため，それらについて上述の \(b\) 更新を行うことができます．そして下位 \(s-1\) 人については，その id を \(x\) の左右の子にそのまま push し，dfs を続行します．

このアルゴリズムが正しく動くことは簡単にわかりますが，計算量が非自明です． 全 node に対する \(|a|\) の総和を \(U\)，全 node に対する「その node の部分木内に id を push した社員数」の総和を \(V\) とします． \(U,V\) を上から抑えることができればよいです． まず，segtree の区間への push を \(N+Q\) 人について行うと，\(U,V\) はどちらも \(O((N+Q) \log Q)\) になります． \(1\) 個の id を親から \(2\) つの子へ下ろした時，\(U,V\) はそれぞれ \(2\) ずつ増加します． ところで，各 node について，子に下ろす id の個数は高々 node の葉の個数であり，これは全部足し合わせると\(O(Q \log Q)\) になります． よってこれらの操作による計算量の増加は \(O(Q \log Q)\) で抑えられます．

これで高速なアルゴリズムが得られました． 結局，各 node で社員 id を強さ順にソートする部分がボトルネックになり，計算量は全体で \(O((N+Q) \log Q \log N)\) になります．

writer解