の値の組み合わせ全 通りについて場合分けし、それぞれ少しずつ異なる解法を用意しましょう。
セグメント木などを用いて の累積和を高速に取得し、必要に応じてセグメント木上の二分探索を行うことで、 どのような に対しても クエリ当たり の時間計算量で処理することができます。
実装に際して、 かつ の場合の処理や、セグメント木上の二分探索が必要なケースでの細かな場合分けに対する処理に注意しましょう。
ところで、場合分けのいらないセグメント木の解法があるようです。不快要素を感じられなかった方、「不快コンなのに不快じゃないじゃん！」と不快になりましたか？（）
場合分け以外をまったく想定しておらずこのような事態になりましたことを深く反省しております。お詫び申し上げます。