JOI2011春合宿4-1 Apples 解説

問題リンク

解説

まず，濃さ $D$ のリンゴが入荷したら，配列の $[D, D+M]$ に $1$ 加算して，$N$ 個の出荷クエリが来た時は，配列のうちで $N$ 以上の最も右の値が取れれば良い．

出荷するべきリンゴは std::set などで容易に求められるので，出荷するときには入荷のときの逆操作を行えばいいだけになる．

クエリが先読みできれば，座標圧縮してセグ木に載せることができるが，この問題はインタラクティブなのでそれができないのが問題である．

ここで，必要なところだけ作るセグ木/動的セグ木を使うと，メモリが少なく済む． メモリ制限がかなり厳しいので，余計な情報をノードに一切持たないようにしてメモリを節約する必要がある．