yukicoder No.1012 荷物収集
ちょっと複雑な累積和。次のような状況を想定する。
[左の荷物群の初期位置] 運びたい位置X [右の荷物の初期位置]
累積和を取ることで、「左の荷物群をその荷物群の中での右端まで異動するためのコスト」のテーブルが構成できる。
あとは「左の荷物群の中での右端」からXまでの移動コストだが、これは左の荷物群の総量と「左の荷物群の中での右端」からXまでの距離の積になる。これで左側がクエリごとにO(1)で計算できた。右側も同様。
あとは左と右に荷物を振り分ける作業であるが、これは二分探索すればよい。計算量はO(log(N) * Q)。
二分探索で見つけたインデックスに±1といった調整が必要になるので、二分探索した結果がどこにあるのか常にイメージで持っておく or 適当に総当りのいずれかが必要。
