AOJ 2933 - 矢 / Arrow (RUPC2019 Day3 D)

解法

簡単のため、 $N$ にも送風機があるとしてよいです。
矢の長さが $i$ のときの損失回数がわかっていれば、各クエリに対して二分探索をして答えを求めることができます。
ということで、長さが $i$ のときの損失回数を頑張って求めます。
送風機と送風機の間にすっぽり矢が収まると、損失を受けます。
例えば、送風機 $j$ と送風機 $j+1$ の間の長さが $m_{j+1} - m_{j} - 1$
なので、その区間で長さ $i$ の矢に対しておこる損失の回数は、
$max(0,m_{j+1} - m_{j} - i)$
となります。
矢の長さが $1$ 増えると、その区間でおこる損失の回数は1減ります。損失回数が0になるまでこの法則は成り立ちます。
矢の長さが $i$ のとき、損失回数は送風機間の長さのみに依存するため、送風機間の長さを昇順でソートしても問題ありません。ということでソートをします。
さて、 $i=1$ から順番に損失回数を計算していきます。なぜかというと、 $i$ の場合は明らかに $\sum (送風機間の長さ)$ なので、すぐに求めることができるからです。
$i$ の長さの矢に対する損失回数を、 $i-1$ の際の情報を元に計算します。
長さ $i$ の矢に対する損失回数を $c_{i}$ とすると、
$c_{i} = c_{i-1} - (長さi-1以上の送風機間の区間の個数)$
となります。
あとはこれを求めていけばよいです。が、コーナーケースがただ一つ存在し、スタートから一番最初の送風機までの区間です。
この区間では、矢の長さがどのような場合でも、最初の送風機までの区間分の損失が生じます。
この損失を追加し忘れないようにしましょう。
あとは、前計算したものをもとに、二分探索をすることで答えを求めることができます。