[0,n)の整数の集合を管理する定数倍が軽いデータ構造

しばしばマラソン（ヒューリスティック）コンテストで使うやつです。 値の追加・削除・存在確認が、最悪時間計算量が定数倍の軽い O(1)、 空間計算量が O(n) でできます。 入っている値を他の値で置き換えるとか、入っている値からランダムに1つ返すとかも簡単にできます。

仕組みとしては単純で、集合に入っている値を保持する que と、 [0,n) の各整数が que の何番目に入っているかを保持する pos の2つを操作します（queと言いつつキューではない）。

エラー処理は入れてないので必要に応じて。

struct IndexSet {

  vector<int> que;
  vector<int> pos;

  IndexSet(int n) : pos(n, -1) {}

  void add(int v) {
    pos[v] = que.size();
    que.push_back(v);
  }

  void remove(int v) {
    int p = pos[v];
    int b = que.back();
    que[p] = b;
    que.pop_back();
    pos[b] = p;
    pos[v] = -1;
  }

  bool contains(int v) const {
    return pos[v] != -1;
  }

  int size() const {
    return que.size();
  }
};