感動
解説
E：L[i]+R[i]でソート、問題ごとに境界を定めれば作問者二人のどちらに振り分けるかが一意に定まる あとは作問者ごとにBITで区間加算、区間和を取得すればO(N^2logN)
— Ryota (@re_re0101) November 19, 2020
↑の方針ですね。
自分が聞きたい区間の中央値が二つの教える区間の中央値に近いほうを選べば必ず損をしないことから、どちらに行くかは中央値でソートしたときprefixとsuffixになりますね
この方針でも真面目にやるとlog落とせますが、BITは速いのでそのまま書いた ←累積和でいいのでさすがに書きなおした
計算量は
