追記(2024/03/21)
AtCoderでもstd::setライクなライブラリが使えるらしいです。手前味噌ですが、それについてのポエムを書いたので、よかったら見てね。
はじめに
この記事は投稿者のメモ代わりに書かれています。不具合があったらごめんね。
ACコードもあまりリーダブルじゃないので参考にしないように。
この記事は何？
競プロでは、配列の最大/最小値を求めたり、配列上で二分探索をしたりすることがよくあります。配列の要素が変わらなければ簡単ですが、要素が挿入されたり削除されたりすることもあります。 頻繁ではありませんが。 こんなとき、いちいちソートしていては間に合いません。C++ならstd::setを使えますがPythonにはありません。
以下ではstd::setの代わりに使える かもしれない 方法を書きます。
heapqを知っていますか？
ABC137D - Summer Vacation
いきなり脱線しますが優先度付きキューを紹介します。優先度付きキューとは、appendが$O(\log N)$、popが$O(\log N)$、最小値の参照が$O(1)$で済むデータ構造です。
Pythonでは標準ライブラリのheapqが使えます。Aをheapifyしたとき、$A[0]$がAの最小値です。最大値を求めたい場合はappendする値とpopされた値に$-1$を掛けます。
公式解説が一番わかりやすいので読んでください。
ACコードの例
類題
heapqから削除したつもりリストを作って管理する
ABC170E - Smart Infants
こちらのブログの解説が非常にわかりやすいです。
幼児$i$が幼稚園Aの最強園児である時、$i$がAからBへ転園すると、Aの最強園児が入れ替わります。つまりAから$i$を削除したあとの最強園児を求めなくてはなりません。
これを解決するのが、削除したつもりの園児のリストを作成する方法です。
つまり、最強園児を求める際に、heapqの先頭に来た園児に対して削除したつもりかチェックし、そうであるならば本当に削除します。そうでないならば、その園児が最強です。最強園児が決まるか、園児が0人になるまで繰り返します。listでは本当に削除する時の処理が遅いため、dictで要素ごとに個数を管理します。
クエリを処理するごとに平等さを求める必要がありますが、同様にheapqと「削除したつもりリスト」で管理できます。
ACコードの例
配列を木構造に落として総和をメモする
ARC033C - データ構造
BIT（Fenwick Treeとも）というデータ構造を使えば、区間和を$O(logN)$で求めることができます。また、平方分割を使えば、区間和を$O(\sqrt{N})$で求めることができます。
$A_{X_i} = (S \in X_i) \ ?\ 1 :0$として、右端のindexが0で総和がxとなる最小の区間を求めれば解けます。
$1\le X_i \le 2 \times 10^5$なので、$X_i-1$をそのままindexとして配列に格納しても間に合います。
二分探索で求めれば間に合うそうですが、私のコーディングスキルでは残念ながらTLEになってしまいました。平方分割で線形探索を行うと通りました。
ACコードの例
類題
座標圧縮＋木
ABC217D - Cutting Woods
簡単のために$x=0,L$にも切れ目があることにします。
$1\le L \le10^9$なので、$L$をそのままindexとして配列に格納すると間に合いません。
そこで、考えるべき線の数が高々$Q+2$本であること、線の左右関係は問題を通じて変わらないことを利用して、座標圧縮を行います。座標圧縮とは、値の上下関係を維持したまま圧縮し、圧縮後の値について操作を行うテクニックです。ただし、あらかじめ全ての値を知っている必要があるため、クエリ先読みを行います。
抽象的な書き方をすると$f(X)=[0,\#X)\cap\mathbb{Q}$かつ$a_i<a_j\Leftrightarrow f(a_i)<f(a_j)$
を満たす$f$と$f^{-1}$を考えるのですが、具体的には重複を取り除いた後にソートしてindexとvalueを入れ替えてdictに入れればよいです。提出したコードでは難解な書き方になっていますが、簡単に書くとこうなります。
X = set()
for c,x in Q:
X.add(x)
finv = list(sorted(X))
f = dict()
for k,v in enumerate(X):
f[v] = k
あとはBITなり平方分割なりに乗せてください。BITも二分探索もしんどいので私は平方分割と線形探索を行いました。だいぶループ回してるはずなのに通るとは思わなかった。
ACコードの例
巨人の肩に乗る
likein12さんがPython向けのordered setとmultisetのwrapperを公開しています。
バイナリを埋め込む手法が使われているため、コンテストのルールをよく確認して使用してください。
自力で実装する
頑張って実装しても遅いことが稀によくあります。
いかがでしたか
C++書けるならそっちのほうがいいよ。