順序付集合

Pythonで順序付き集合の処理をしようとして苦労することが多い.そこで,順序付集合はC++で解けるようにしておきたい.

使うのは<set>.この中に,キーの重複を許さないsetと,キーの重複を許すmultisetがある.ソートを保ったまま,要素の挿入(insert)を対数時間で処理できる.
set - cpprefjp C++日本語リファレンス


イテレータ,lower_bound,upper_boundについては以下がわかりやすい.
AI - 4.04.イテレータ

  • lower_bound:「指定した値以上の最小の要素」を指すイテレータを返す.見つからなかった場合は、範囲の最後を返す.
  • upper_bound:「指定した値より大きな最小の要素」を指すイテレータを返す.見つからなかった場合は、範囲の最後を返す.

std::set

重複がない集合を扱うことができる.
set - cpprefjp C++日本語リファレンス

ABC217D - Cutting Woods

D - Cutting Woods
(C++解法:(C++) ABC217D - Cutting Woods - 競プロはじめました)
(Python解法:ABC217D - Cutting Woods - 競プロはじめました)


std::multiset

重複がある集合を扱いたい場合はこちらを使う.
multiset - cpprefjp C++日本語リファレンス

ABC241D - Sequence Query

D - Sequence Query
(C++解法:(C++)ABC241D - Sequence Query - 競プロはじめました)

ABC245E - Wrapping Chocolate

E - Wrapping Chocolate
(C++解法:ABC245E - Wrapping Chocolate - 競プロはじめました