問題
https://codeforces.com/contest/1294/problem/D
問題概要
空の配列と正の整数xが与えられる。さらに、クエリがq個与えられ一つのクエリ毎に非負整数yが配列に挿入される。
配列に挿入された整数に対しては任意のタイミングと回数でxを加算または減算することができる。
今、上記の条件で配列のMEX(minimum non-negative integer)を最大化したい。各クエリ毎にMEXがいくつになるかを答えよ。
考察
MEXを最大化したいため、できるだけ配列の中の整数を0から順に敷き詰めていきたいです。
yに対して好きなだけxを加算または減算できるということは、つまりy % xとなる任意の整数を作れるということです。なのでyそのものではなく、y % xが一致する値の個数さえ覚えておけば、MEXを最大化できる配列が構築できることになります。ここで、MEXの候補となるのは一致する値の個数が最も少ないy % xにかかわる数字となります。
・・・説明が下手すぎるので、図を書きました。
この図でわかるように、一番へこんでる部分がMEXになるのですが、愚直に実装して探索していては間に合いません。なので、個数をsetやセグメントツリーで管理する必要があります。
セグメントツリーで実装する場合、1つずつインクリメントする口と、最小値だけでなくそのインデックスがどこなのかをもらってくる口が必要となります。（多分）
実装例→Submission #69389297 - Codeforces
自分用おぼえがき
残念ながらコンテスト中には通せなかったです。そもそもセグメントツリーを実戦投入したのはこれが初めてで、あわてて検索して拾ってきたやつを、どういじればほしいものになるのかー、ってやってるうちにタイムアップとなってしまいました。
翌日、おちついて考えたら、割とあっさり実装できてしまいました。コンテスト中にもこの落ち着きがほしい・・・。
なお、拾ってきたのはこちらです。
とてもわかり易い説明でしたし、機能追加もやりやすかったです。（ていうか、そもそもそういう趣旨の記事ですね） ありがとうございました。
