std::setを使わない代替テクニック

競技プログラミングでは、C++ に std::set という（事実上）平衡二分探索木ライブラリがあるから、たまにその使用を前提とした問題が出る。

std::set, multiset は、集合を順序を持って管理するデータ構造であり、以下のことができる（set - cpprefjp C++日本語リファレンス より一部抜粋）

Pythonでは標準ライブラリにないし、実装してもリストアクセスの遅さからTLEに直面することがままある。

いや、実際には、別に使わなくても何とか別の方法がある場合が多いが、std::setが「使えば一発」なのに対し、問題依存の考察や実装の手間を要するのが常である。 （素直にC++で書けって？そりゃそうだ）

std::setを使いたいけど使えない……という場合に、代わりになりうる方法をメモ。

問題に出くわすごとに列挙していき、ある程度蓄積されたら分類方法を考える。

• Binary Indexed Tree
  • 最も汎用性のある代替方法
• 優先度付きキュー (heapq)
  • 一定の制約の上で簡単&高速
• 問題依存の上手い方法
  • 列挙していけば何か共通点みたいなのが見つかるかも知れない
• C++コードを埋め込んで外部モジュールとしてコンパイル
  • 下記、参考の3つめのリンク参照

• 参考
  • k 番目の値を高速に取り出せるデータ構造のまとめ - BIT上二分探索や平衡二分探索木など - Qiita
  • 【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita
  • [Python]平衡二分木が必要な時に代わりに何とかする変なテク[競プロ] - 菜

最も汎用性の高い置き換え。std::setは言うて単純な機能しか持ってないが、こちらなら追加の機能実装も可能。

• 集合に、値を追加したり削除したりする
• 任意のタイミングで、小さい方から $k$ 番目の値を答えよ。$k$ は可変である。
• 制約
  • 値の取り得る範囲は $1～10^6$（配列を作れる）程度

Binary Indexed Tree で管理できる。ただし、BIT上で累積和の二分探索を実装する必要がある。 詳細はBinary Indexed Tree（Fenwick Tree）参照。

• 値 $x$ を追加 → $bit.add(x, 1)$
• 値 $x$ を削除 → $bit.add(x, -1)$
• $k$ 番目の値を取得 → 累積和が $k$ 以上になる最小のindexを取得

値の取り得る種類数が $N=10^6$ 程度で、かつ先読みできる場合、前もって圧縮して $1～N$ に対応づければよい。

BIT上の二分探索では、累積和が $k$ 以上になる要素そのものは分かっても、前後の値はたどれない。

この方法では前後の値を求めたい場合は $k \pm 1$ で累積和の二分探索を改めて行うしかない（と思う）。

ただし、小さい方の値を求める際、以下の方法で少しだけ省略できる場合がある。

累積和の探索では、その過程で、累積和が $k$ 以上になる最小の要素を $x$ として「$x$ 未満の要素の個数」も求めることになる。 （これを $L[k]$ と表す）

• $L[k]=k-1$ なら、改めて累積和が $k-1$ 以上になる最小の要素を二分探索
• $L[k] \lt k-1$ なら、$x$

• 値が追加されたり削除されたりする
• 任意のタイミングで、小さい方から $k$ 番目の値を答えよ
• 制約
  • $k$ は固定である

上記のような制約があれば、2つの優先度付きキューを用いることで代替できる。

Binary Indexed Treeでは実現できない、$10^9$ など配列を作るのが厳しい範囲のクエリにも対応できる。

• lower: 常に値の個数を $k$ 個に保つ優先度付きキュー。大きい方から取り出す
• upper: $k$ 個から溢れた分を管理する優先度付きキュー。小さい方から取り出す

答えは常にlowerの先頭に位置する（$x$ とする）。新しい値 $y$ が来たとき、

• $x \le y$ なら、$y$ をupperにpush
• $x \gt y$ なら、$x$ をlowerよりpopし、代わりに $y$ をpush。$x$ はupperにpush

lowerとupperの要素数が同じになるように保ちながら追加していく。

削除されるのが $k$ 番目の値に限定されるなら、つねに優先度キューの先頭にあるので可能。

優先度キューとは別に、「値が生き残っているか」を管理するデータを用意する。

• 要素に重複が無い場合
  • 「値:$x$ は生き残っているか」を管理するデータ
• 要素に重複がある場合
  • 要素にIDをつける
  • 「ID:$i$ は生き残っているか」を管理するデータ
• lowerで生き残っている要素数を管理する変数 $lc$（lowerの個数が $k$ 未満になる可能性のある場合）
• lower, upperで生き残っている要素数を管理する変数 $lc, uc$（中央値を求める場合）

値 $y$ を削除するとき、lowerの先頭 $x$ と比較して、

• $x \lt y$ なら、$y$ を削除済みにする
• $x \ge y$ なら、$y$ を削除済みにし、upperからlowerに1要素移す

popするとき、それが生き残っている値かどうかを確認し、削除済みなら無かったこととして続けてpopする。

一概には言えないけど、だいたい以下のような問題に適用できうる。

• 順列など、全ての要素が異なる配列を考える
• 各要素について、「自分の左(右)で自分に最も近い、自分より小さな(大きな)値の位置」を求めたい

Binary Indexed Tree でもいいんだけど、より高速で、なかなかアイデアが綺麗な解法。

これを使って解ける問題（ネタバレ注意）

std::setであれば、値の小さい順に「要素のindex」をinsertしていく方法が考えられる。

ある要素 $A_i$ を挿入しようとしたとき、既にset内にあるのは自身より小さな要素のindexに限られる。 そこから $i$ 未満で最も大きい数を検索すれば、それが $A_i$ にとって、自身より小さな左で直近の要素の位置である。

各要素の暫定解を表す配列を用意して、値の大きい順に処理して更新していく。

• $L$: 自身より左で、自身より小さい直近の要素のindex（暫定）
• $R$: 自身より右で、自身より小さい直近の要素のindex（暫定）

ある要素の処理が終わったら、後から処理される要素のために、自身をスキップさせるよう更新する。

横一列に繋がったグラフの辺を繋ぎなおすと考えるとわかりやすい。

【初期状態】
i   1   2   3   4   5   6
   ③--①--④--⑥--⑤--②
L   0   1   2   3   4   5    自身より左で自身より小さい要素の i （暫定）
R   2   3   4   5   6   7    自身より右で自身より小さい要素の i （暫定）

はじめはすぐ左・すぐ右の位置を入れておく

【最も大きい要素⑥】
処理された時点のL,Rの値がそのまま答えとなる。
最初はどの要素も自分より小さいので、すぐ左・すぐ右のindexとなるのは当然。
i   1   2   3   4   5   6
   ③--①--④--⑥--⑤--②
L   0   1   2  [3]  4   5
R   2   3   4  [5]  6   7

次の処理のために、⑥を抜いて、④と⑤を直結させたい。
i   1   2   3   4   5   6
   ③--①--④------⑤--②
L   0   1   2       _   5
R   2   3   _       6   7

そのためには、以下のように更新すればよい
L[R[i]] = L[i]
R[L[i]] = R[i]

今回に当てはめると、
L[5] = 3
L[3] = 5

i   1   2   3   4   5   6
   ③--①--④------⑤--②
L   0   1   2      [3]  5
R   2   3  [5]      6   7

【2番目に大きい要素⑤】
同様に、この時点での L[i]=3, R[i]=6 が⑤にとっての答え
i   1   2   3   4   5   6
   ③--①--④------⑤--②
L   0   1   2      [3]  5
R   2   3   5      [6]  7

同様に更新すると、ちゃんと④と②がつながる
i   1   2   3   4   5   6
   ③--①--④----------②
L   0   1   2          [3]
R   2   3  [6]          7

これを繰り返すと、$O(N)$ で求められる。std::setを使うと $O(N\log{N})$ なので、それより高速である。

値が飛び飛びなら、先読みできるなら圧縮すればよい。先読みできない場合は……わからん。

同じ値が含まれると、同率の処理が上手くいかない。

一応、自身の値 “以下” の直近の位置を求めればいいなら、方法がある。

• $L[i],R[i]$ の取得を同率の要素ごとにまとめて行い、更新は全ての同率の要素が終わった後で一括に行う

自身の値 “未満” なら……どうやればいいだろうね。