※1500msecぐらいかかりました。※Sorterがうざったいかもしれませんが、AtCoderと共通化したいため、このようにしています(こどふぉのGoはバージョンが新しいので実際はもっとスマートに書けるはずです。詳しく解説されています(他にも色々わかりやすくまとめている方がたくさんおられました)。今回は、位置に関してBITで管理するため、要素数の制約から座標圧縮する必要はありませんでした。BIT上の二分探索とは?hosさんのBIT解説PDFにおいて最後の方で説明がなされています。自分には最初何をやっているのかよくわかりませんでした。自分なりに議論を補間しつつゆっくりと追っていくと理解できたので、忘れた頃の未来の自分を第一の対象として、理解の道筋を残しておこうと思います。「BIT上の二分探索ってそもそも何?」となってしまいましたが、これは「元の配列の先頭からの累積和に関する二分探索」となります。2乗になるというのは納得できます。落とすことができる、とのことです。それとともに与えられたアルゴリズムが以下のものですが、これまた初見時はよくわかりませんでした。1}これは要約すると、「先頭からの累積和を、できるだけ長い区間から足して良いかを都度判断する」ということを行っています。いうのは現在注目している区間の長さを意味しています。小さい場合は、足してから右側の次の短い長さの区間を見る必要があります。逆にkey値よりも大きい場合は、その区間和は足さずに左側の次の短い長さの区間を見る必要があります。以下は、ある具体例におけるアルゴリズムの様子を図示したものです(あまりわかりやすくできませんでしたが。