std::setが欲しくなる問題をPythonで解く

# 追記(2024/03/21)
AtCoderでもstd::setライクなライブラリが使えるらしいです。手前味噌ですが、[それについてのポエムを書いた](https://qiita.com/mukakego/items/7df93e17ec0cd0913a14)ので、よかったら見てね。

# はじめに
この記事は投稿者のメモ代わりに書かれています。不具合があったらごめんね。
ACコードもあまりリーダブルじゃないので参考にしないように。
# この記事は何？
競プロでは、配列の最大/最小値を求めたり、配列上で二分探索をしたりすることがよくあります。配列の要素が変わらなければ簡単ですが、要素が挿入されたり削除されたりすることもあります。 ~~頻繁ではありませんが。~~ こんなとき、いちいちソートしていては間に合いません。C++ならstd::setを使えますがPythonにはありません。
以下ではstd::setの代わりに使える ~~かもしれない~~ 方法を書きます。
# heapqを知っていますか？
[ABC137D - Summer Vacation](https://atcoder.jp/contests/abc137/tasks/abc137_d
)
いきなり脱線しますが**優先度付きキュー**を紹介します。優先度付きキューとは、appendが$O(\log N)$、popが$O(\log N)$、最小値の参照が$O(1)$で済むデータ構造です。
Pythonでは標準ライブラリのheapqが使えます。Aをheapifyしたとき、$A[0]$がAの最小値です。最大値を求めたい場合はappendする値とpopされた値に$-1$を掛けます。
[公式解説](https://img.atcoder.jp/abc137/editorial.pdf)が一番わかりやすいので読んでください。
[ACコードの例](https://atcoder.jp/contests/abc137/submissions/26417745)

### 類題
* [ABC141D - Powerful Discount Tickets](https://atcoder.jp/contests/abc141/tasks/abc141_d)
* [ABC212D - Querying Multiset](https://atcoder.jp/contests/abc212/tasks/abc212_d)
* [ABC217E - Sorting Queries](https://atcoder.jp/contests/abc217/tasks/abc217_e)

# heapqから削除したつもりリストを作って管理する
[ABC170E - Smart Infants](https://atcoder.jp/contests/abc170/tasks/abc170_e)
[こちらのブログ](https://betrue12.hateblo.jp/entry/2020/08/04/204914)の解説が非常にわかりやすいです。
幼児$i$が幼稚園Aの最強園児である時、$i$がAからBへ転園すると、Aの最強園児が入れ替わります。つまりAから$i$を削除したあとの最強園児を求めなくてはなりません。
これを解決するのが、**削除したつもり**の園児のリストを作成する方法です。
つまり、最強園児を求める際に、heapqの先頭に来た園児に対して**削除したつもり**かチェックし、そうであるならば**本当に削除**します。そうでないならば、その園児が最強です。最強園児が決まるか、園児が0人になるまで繰り返します。listでは**本当に削除**する時の処理が遅いため、dictで要素ごとに個数を管理します。
クエリを処理するごとに平等さを求める必要がありますが、同様にheapqと「削除したつもりリスト」で管理できます。
[ACコードの例](https://atcoder.jp/contests/abc170/submissions/26419421)

# 配列を木構造に落として総和をメモする
[ARC033C - データ構造](https://atcoder.jp/contests/arc033/tasks/arc033_3)
**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コードの例](https://atcoder.jp/contests/arc033/submissions/26425457)

### 類題
* [ABC157E - Simple String Queries](https://atcoder.jp/contests/abc157/tasks/abc157_e)

# 座標圧縮＋木
[ABC217D - Cutting Woods](https://atcoder.jp/contests/abc217/tasks/abc217_d)
簡単のために$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に入れればよいです。提出したコードでは難解な書き方になっていますが、簡単に書くとこうなります。

```python
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コードの例](https://atcoder.jp/contests/abc217/submissions/26427753)

# 巨人の肩に乗る
likein12さんがPython向けのordered setとmultisetのwrapperを公開しています。
バイナリを埋め込む手法が使われているため、コンテストのルールをよく確認して使用してください。

https://zenn.dev/likein12/articles/55283e9a47dac2

# 自力で実装する

https://twitter.com/terry_u16/status/1434330979041120260

頑張って実装しても遅いことが稀によくあります。

# いかがでしたか
C++書けるならそっちのほうがいいよ。