S[j]-S[i] で和を求めるときに、i<j でも j<i でも構わないということ。符号を入れ替えればいいだけ。そしてこの問題に関して言えば、問われているのが絶対値であることで符号の入れ替えさえ不要だった。絶対値が問題を面倒にしているとばかり思っていたぜ。■提出 #28807480 (AC / 232 Byte / 1853 ms)。累積和をソートすることも解を二分探索することも早くからわかっていた。二分探索の中で数列をスキャンする中で j<i となるケースを除外するために BIT なりで対数時間の処理を加えてしまうと Nlog^2 になって困ったなーと考えていた。事前にじっくり準備して BIT に頼らないデータ、それも N×N よりコンパクトなデータが作れないかなーと考えていた。実は j<i となるケースを除外する必要などなかった。累積和の使い方がわかっていない！ 精進の道とは自分のアホさを確認する道なのか。+/- に応じて +x/-x するというのが縦の見かたなら、M に応じて x を +1/-1 することが +x/-x する操作にそれぞれ何回寄与するかを考えるのが横からの見かた。提出 #28608177 (AC / 157 Byte / 72 ms)。気がつくと簡単に答えが出て気持ちがいい。■横からの見かたが培われたのはたぶんこのとき>「足し算とはそういうものだ、と言われたら言葉がない。私は足し算がわかりません。」 なんだ、より難しい類題を解説 AC していたから解けただけだった。m_nOpeBlkRedawCount って初めて見るけどどういう役割なのかな。結局行き着くところはミニマップの構造的・原理的問題だよね。文書の全体を(たぶん愚直に)描画しているからいろいろと遅い。全体を俯瞰するのがミニマップの用途だと思うけど、俯瞰したいほど大きな文書を扱うのに難がある。LOD (Level of Detail) が必要？