C++の順序付多重集合について

最近multisetを使うと簡単に解ける問題がちょくちょくAtCoderで出題されて解けなかったりしたので、簡単にC++のmultisetについてまとめる。

C++のmultisetとは

順序付多重集合、つまり順序を保持しつつ要素の重複を許容した集合を効率的に管理するためのデータ構造であり、以下の操作をで行うことができる。

• insert
• erase
• find
• lower_bound
• upper_bound
• count

更に詳しくは以下。
vivi.dyndns.org

※注意その1

lower_bound,upper_bound等はstd::lower_bound,std::upper_boundを使うととなってしまう罠があるため、multisetに定義されたものを使うこと。
詳しくは以下。
betrue12.hateblo.jp

※注意その2

multiset内の要素を削除するとき、s.erase(v);のように書くとs内のvが全て削除される。一つだけ削除したい場合はiteratorを指定してやる必要があり、例えば以下のように書けば良い。

auto itr = s.find(v);
s.erase(itr);

典型的な問題

要素を更新しつつ2分探索をする必要がある問題などで有効な場合があり、例えばこの問題なんかは典型的。
atcoder.jp
この問題は、以下の手続きで解くことができる。

1. 色グループ毎の値を保持するデータ構造を定義する
2. 右から順に要素を見ていく
3. 既存の色グループの中で、最小値が今着目している値より大きいものがあるか？
   1. YES→該当する色グループに加える
   2. No→新たな色グループを作る
4. 全ての要素を見終わった時点で存在している色グループの数が答え

ここで、処理3に着目したとき色グループ毎に全ての値を保持する必要はなく、ある色グループに値を加えられるかどうかはあくまで最小値のみが関係することがわかる。
よって、各色グループの最小値のみを保持し、今着目している値より大きい最小値を持つグループがあるかどうかを高速に判定できれば良い。
この処理はmultisetのupper_boundでで実現できる。よって要素を見ていく計算量と合わせて全体でで解くことができた。

実装

#include <algorithm>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define pb push_back
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n, s) for (int i = (s); i < (n); i++)
#define rrep(i, n) for (int i = (n - 1); i >= 0; i--)
#define rreps(i, n, s) for (int i = s; i >= n; i--)

using ll = long long;
using namespace std;
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int MOD = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    multiset<ll> s;
    for (int i = n - 1; i >= 0; i--) {
        auto it = s.upper_bound(a[i]);
        if (it != s.end()) { s.erase(it); }
        s.insert(a[i]);
    }
    cout << s.size() << endl;
    return 0;
}

類題

以下の問題は最小値ではなくk番目の値だが、同様にmultisetで解ける。
atcoder.jp