問題：No.817 Coin donation - yukicoder
解答：#501352 (C++14) No.817 Coin donation - yukicoder
解法：i円の硬貨が何枚あるかを累積的に管理し、個数がk以上となるときのiを出力すればよい。ただし、硬貨の種類の上限が109であるため、全ての種類の硬貨の枚数を管理することはできない。
クエリでAi～Bi円の硬貨を入れるという操作が与えらるが、これをimos法と同じアイディアで管理する。また枚数の更新はこのクエリのAi、Biのタイミングのみで行うこととし、その間を計算で補間するとうまくいく。
座標圧縮を使う方法もあるらしい。
