2019年4月2日火曜日

平衡二分木のための問題リスト

平衡二分木のための問題リスト

Treapの実装をいじったときのテスト用に、Treapが使える問題をメモしておく。今のところすべてAtCoder。

別に平衡二分木でないと解けない問題を選んでいるわけではなくて、いわゆるセグメント木で解く問題が多い。(セグメント木が必要になったらimplicit treapを使っているので)

問題 データ 更新 取得
データ構造 key 挿入・削除 添え字アクセス
特別賞 key 挿入 添え字アクセス
Enclosed Points key 挿入 二分探索
Exclusive OR Queries key 挿入・削除 区間走査
タコヤキオイシクナール key/value 挿入・一点更新 区間取得
Meaningful Mean key/value 挿入・一点更新 区間取得
Roadwork key/value 挿入・区間更新 一点取得
Deforestation value 区間更新 (構築のみ)
足ゲームII value 区間更新 区間取得
ドキドキデート大作戦高橋君 value 区間更新 区間取得
Counting 1’s value 区間更新 区間取得
本棚 value 一点更新 区間取得
pushpush value 挿入・反転 (構築のみ)
Absolute Minima value 挿入 区間取得
Hash Swapping value merge/split 区間取得

項目「データ」について:

  • key: 比較のためのキーのみを持つ。たぶんC++のstd::setやJavaのTreeSetに対応する。
  • key/value: キーを持ち、キーに対応する値も持つ。たぶんC++のstd::mapやJavaのTreeMapに対応する。多重集合とかもこれで表現できる。
  • value: 比較可能なキーを持たない。左から何番目にあるかを暗黙のキーとして使うので、implicit treapと呼ぶらしい。ほぼ動的セグメント木(+α)として使う。