概要

操作を逆から見ることにしましょう。区間 \([l, r)\) からなる派閥について考えているとき、 \(x = \displaystyle \sum_{k=l}^{r-1} A_k\) として \(l \leq a \leq b \leq r\) かつ \(\displaystyle \sum_{k=a}^{b-1} > \frac{x}{2}\) でありまた区間 \([a, b)\) もある時点で 1 つの派閥をなすような極小な区間 \([a, b)\) までスキップすることができます。このスキップ操作と愚直に最小値で分割する操作で区間の \(A\) の和が半分になりますから、以上を 1 ステップとして \(O(\log N + \log \max A)\) ステップで \(r-l=1\) となり答えを求められます。

スキップ操作を高速に行うことを考えましょう。\([a, b)\) を求めるのは大変ですが、代わりに \(\displaystyle \sum_{k=c}^{d-1} A_k \leq \frac{x}{2}\) を満たすような極大な区間 \([c, d)\) のうち \(\displaystyle \min_{k=c}^{d-2} B_k\) を最大化するようなものを求めても構いません。(それを内包する派閥をなす区間のうち極小なものが \([a, b)\) となります) この言い換えにより「ある時点で派閥をなす」という条件の扱いづらさが楽になります。

\([c, d)\) は簡単な二分探索で \(O(\log^2 N)\) で求まります。クエリに答えるときは 1 クエリあたりこれを \(O(\log N + \log \max A)\) 回処理する必要がありますが、丁寧な実装では十分高速です。実際には Segment Tree 上で左右の端ノードをもって並列に二分探索を進めることで \(O(\log N)\) で求めることができ、より高速です。

詳細や解答例

解説スライド

小課題 1 コード

小課題 5 コード