導入 配列 $a = (a_0, a_1, \dots, a_{n-1})$ に対して適当な区間 $[l\lldot r)$ が与えられて、そこでの平均値 $f_a(l, r) = \tfrac1{r-l}\sum_{i=l}^{r-1} a_i$ を考えます。 たとえば $[l\lldot r)$ がたくさん与えられて平均値を求めるだけなら、累積和を用いるだけでよいです。 あるいは $a_i$ を $x$ に更新するようなクエリがたくさん与えられる場合も、セグ木を用いるだけでよいです。 では、左端 $l$ を固定した場合に平均値を最大たらしめる右端 $\argmax_{r\gt l} f_a…