AtCoder Beginner Contest 188 D - Snuke Prime

問題

考察

$1 \le a_i \le b_i \le 10^9$ となっていて、区間として範囲が大きいので
いもす法という手法を使って、単純に各区間の増減の累積和を取ることができないことが分かる。

最初は各区間について $a_i, b_i$ を一組としてまとめて、うまくソートなりなんなりをすれば良さそうと考えていたが
そこからまったく分からなかった。

公式解説によると
各区間の $a_i, b_i$ をまとめて考えるのではなく、 $a_i, b_i$ を別々のものとして扱い、
いもす法の発想を少し応用した工夫をすることで解くことができる。

f:id:tookunn:20210503192521p:plain

こんな感じに区間を直線で表すと
$i$ 日目を1からなめていったときにいずれかの区間の $a_i$ か $b_i$ と重なるまで
払う料金は一定で、 $a_i$ か $b_i$ に出くわしたときに料金が変動することが分かるので
いもす法っぽく $a_i$ 日目に $+c_i$ 円、 $b_i + 1$ 日目に $- c_i$ 円という料金が変動する情報を持っておけば良い。