競技プログラミング用 知識集積所
ABC449E - A = v
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
考察問題。
Xの値が小さければ愚直にやっても間に合うが、実際には最大10^18まであるのでTLEする。
そこで、vectorの延長を1つずつではなくまとめて行い、しかも実際にvector構成はしないという方針を考えなければならない。
Xの値が小さければ愚直にやっても間に合うが、実際には最大10^18まであるのでTLEする。
そこで、vectorの延長を1つずつではなくまとめて行い、しかも実際にvector構成はしないという方針を考えなければならない。
問題では、登場回数最少のものが複数ある場合は、値が最小のものを追加することになっている。
しかし、この後の挙動を考えると、登場回数最少のものが複数ある場合は全部を小さい順に全部追加するという操作だと思っても問題ない。
すると、登場回数最少のグループに新しい数が加わるまで、「まとめて何セットかつけたことにします」で処理することすら可能になる。
しかし、この後の挙動を考えると、登場回数最少のものが複数ある場合は全部を小さい順に全部追加するという操作だと思っても問題ない。
すると、登場回数最少のグループに新しい数が加わるまで、「まとめて何セットかつけたことにします」で処理することすら可能になる。
こうすると、クエリのXに対して、「何個同時につけるときの何番目」という情報に計算で変換できるようになる。
よって、クエリを全部先読みさえすれば、あとは「何個同時につけるときの何番目」を高速に求める方法だけが問題になる。
そしてその「前からk番目」は、Fenwick木※において、登場回数最少グループに含まれるものを1、そうでないものを0としておくことで、先頭からの合計がk以上になる最初の位置を二分探索※することで求められる。
よって、クエリを全部先読みさえすれば、あとは「何個同時につけるときの何番目」を高速に求める方法だけが問題になる。
そしてその「前からk番目」は、Fenwick木※において、登場回数最少グループに含まれるものを1、そうでないものを0としておくことで、先頭からの合計がk以上になる最初の位置を二分探索※することで求められる。
あとは非常に重い実装を頑張るのみ。
