Codeforces Round #259 E. Little Pony and Lord Tirek
http://codeforces.com/contest/453/problem/E
問題概要:
ポニーがN匹一列に並んでいる。ポニーiは最初siのManaを持っており、毎時間riのペースでManaを増やすが、Manaはmiまでしか持てない（それ以上になるとmiで止まる）
クエリがM回ある。それぞれのクエリで、時刻tiに[l,r]の範囲のポニーのManaを全部刈り取り、その合計を答える。刈り取られると彼らのManaは0になる。
クエリーはtiが狭義単調増加になるよう与えられる。
解法
初期条件siは面倒なのでとりあえず無視。
セグメント木上の区間で、その区間に属するポニーを「刈り取られてからManaが増加する時間」の長さでソート。(mi/ri)
この並びのポニーで、miの累積和、riの累積和を取る。
これで、あるセグメント木上の区間が時刻Tに刈り取られ、その後時間difが経った時にまた刈り取られるとすると、増加時間が dif以上、以下でポニーを分割し、増加時間がdifより少ないポニーたちについてはmiの総和、大きいポニーたちについてはriの総和*difで刈り取る合計が求まる。①
クエリーごとに、刈り取る範囲のポニーの列を、いつ最後に刈り取られたかの区間で分割する。
いつ最後に刈り取られたかの区間について、セグメント木でlogN個の区間に分割できる。
区間K個と重なる範囲を刈り取るとすると、それぞれlogN個に分割し、①の方針でやると二分探索を含むのでO(Klog^2N)の時間がかかるが、刈り取る範囲に完全に含まれる区間は刈り取りの後全部一緒になる。ここから考えるとならしでO(Mlog^2N)になることが分かる。
いつ最後に刈り取られたかの区間はsetで持って重なるものをイテレーションしてもできるが、
以下の方法でもできる：
セグメント木上のあるノードに含まれるポニーが全員同じ時刻に刈り取られたなら、そこで①の感じで処理。
そうでないなら、刈り取る範囲に完全に含まれているとしても、さらに分割。
この方針で、刈り取られた時刻が同じ区間それぞれについて処理している事になる。
あるノードの刈り取られた時刻が一緒かどうかは、刈り取った時にそのノードにフラグを建てておき、下のノードへは使うときに伝播させる。あるノードを更新したら、それらの上のノードで刈り取られた時刻が同じかどうかを確認する、という一般的な処理。
初期条件siがあるので、最後に刈り取られたのが時刻0の場合は、何があってもノードがひとつになるまで分割。
時間O(Mlog^2N)
空間O(NlogN)
