Mo's Algorithm

説明

Mo’s algorithm - ei1333の日記

クエリを先読みできて、区間の伸縮が簡単に計算できるとき Mo’s Algorithm が適用できる可能でいがある。

計算量

• $O(f(N) Q \sqrt N)$

区間を伸縮するときの計算量を $f(N)$ とする

実装例

• Mo($N$, $Q$):= 区間の長さ $N$, $Q$ 個のクエリで初期化する。
• add($l$, $r$):= クエリ $[l, r)$ を追加する。
• run($add$, $del$, $rem$):= 全てのクエリを処理する。ここで, add(idx) は idx 番目の要素を入れる, del(idx) は idx 番目の要素を消す, rem(idx) はクエリ idx を処理する関数。

struct Mo {
  using ADD = function< void(int) >;
  using DEL = function< void(int) >;
  using REM = function< void(int) >;

  int width;
  vector< int > left, right, order;
  vector< bool > v;

  Mo(int N, int Q) : width((int) sqrt(N)), order(Q), v(N) {
    iota(begin(order), end(order), 0);
  }

  void add(int l, int r) { /* [l, r) */
    left.emplace_back(l);
    right.emplace_back(r);
  }

  int run(const ADD &add, const DEL &del, const REM &rem) {
    assert(left.size() == order.size());
    sort(begin(order), end(order), [&](int a, int b) {
      int ablock = left[a] / width, bblock = left[b] / width;
      if(ablock != bblock) return ablock < bblock;
      if(ablock & 1) return right[a] < right[b];
      return right[a] > right[b];
    });
    int nl = 0, nr = 0;
    auto push = [&](int idx) {
      v[idx].flip();
      if(v[idx]) add(idx);
      else del(idx);
    };
    for(auto idx : order) {
      while(nl > left[idx]) push(--nl);
      while(nr < right[idx]) push(nr++);
      while(nl < left[idx]) push(nl++);
      while(nr > right[idx]) push(--nr);
      rem(idx);
    }
  }
};

検証

SPOJ D-Query

nt main() {
  int N, Q;
  cin >> N;
  vector< int > A(N);
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }
  cin >> Q;
  vector< int > f(1000001);
  Mo mo(N, Q);
  for(int i = 0; i < Q; i++) {
    int l, r;
    cin >> l >> r;
    mo.add(--l, r);
  }
  int ret = 0;
  auto add = [&](int idx) { if(f[A[idx]]++ == 0) ret++; };
  auto del = [&](int idx) { if(f[A[idx]]-- == 1) --ret; };
  vector< int > ans(Q);
  auto rem = [&](int idx) { ans[idx] = ret; };
  mo.run(add, del, rem);
  for(int i = 0; i < Q; i++) {
    cout << ans[i] << "\n";
  }
}

SPOJ Frequent values

int main() {
  int N, Q;
  while(cin >> N, N) {
    cin >> Q;
    vector< int > A(N);
    for(int i = 0; i < N; i++) {
      cin >> A[i];
      A[i] += 100000;
    }
    vector< int > f(200001), g(200001);
    Mo mo(N, Q);
    for(int i = 0; i < Q; i++) {
      int l, r;
      cin >> l >> r;
      mo.add(--l, r);
    }
    int ret = 0;
    auto add = [&](int idx) {
      g[f[A[idx]]]--;
      f[A[idx]]++;
      g[f[A[idx]]]++;
      if(f[A[idx]] > ret) ++ret;
    };
    auto del = [&](int idx) {
      g[f[A[idx]]]--;
      f[A[idx]]--;
      g[f[A[idx]]]++;
      if(ret - 1 == f[A[idx]] && g[ret] == 0) --ret;
    };
    vector< int > ans(Q);
    auto rem = [&](int idx) { ans[idx] = ret; };
    mo.run(add, del, rem);
    for(int i = 0; i < Q; i++) {
      cout << ans[i] << "\n";
    }
  }
}

応用 1: ロールバック平方分割

普通のMoだと要素を削除する操作が要求された。

Mo’s algorithm の上位互換の話 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ をすると、削除操作は不要で要素の追加と snapshot を撮った位置まで巻き戻す rollback ができればよい。

• MoRollBack($N$, $Q$):= 区間の長さ $N$, $Q$ 個のクエリで初期化する。
• add($l$, $r$):= クエリ $[l, r)$ を追加する。
• run($add$, $rem$, $reset$, $snapshot$, $rollback$):= 全てのクエリを処理する。ここで, add(idx) は idx 番目の要素を入れる, rem(idx) はクエリ idx を処理する、$reset$ はデータ構造の初期化, $snapshot$ は現在の状態を記録, $rollback$ は $snapshot$ まで巻き戻す関数。

struct MoRollBack {
  using ADD = function< void(int) >;
  using REM = function< void(int) >;
  using RESET = function< void() >;
  using SNAPSHOT = function< void() >;
  using ROLLBACK = function< void() >;

  int width;
  vector< int > left, right, order;

  MoRollBack(int N, int Q) : width((int) sqrt(N)), order(Q) {
    iota(begin(order), end(order), 0);
  }

  void add(int l, int r) { /* [l, r) */
    left.emplace_back(l);
    right.emplace_back(r);
  }

  int run(const ADD &add, const REM &rem, const RESET &reset, const SNAPSHOT &snapshot, const ROLLBACK &rollback) {
    assert(left.size() == order.size());
    sort(begin(order), end(order), [&](int a, int b) {
      int ablock = left[a] / width, bblock = left[b] / width;
      if(ablock != bblock) return ablock < bblock;
      return right[a] < right[b];
    });
    reset();
    for(auto idx : order) {
      if(right[idx] - left[idx] < width) {
        for(int i = left[idx]; i < right[idx]; i++) add(i);
        rem(idx);
        rollback();
      }
    }
    int nr = 0, last_block = -1;
    for(auto idx : order) {
      if(right[idx] - left[idx] < width) continue;
      int block = left[idx] / width;
      if(last_block != block) {
        reset();
        last_block = block;
        nr = (block + 1) * width;
      }
      while(nr < right[idx]) add(nr++);
      snapshot();
      for(int j = (block + 1) * width - 1; j >= left[idx]; j--) add(j);
      rem(idx);
      rollback();
    }
  }
};

Codeforces 2014-2015 ACM-ICPC, NEERC, Southern Subregional Contest A - Nasta Rabbara

区間 $[l_i, r_i]$ の辺のみがあるときに、二部グラフかどうか答えよ

struct UnionFindUndo {
  vector< int > data;
  stack< pair< int, int > > history;

  UnionFindUndo(int sz) {
    data.assign(sz, -1);
  }

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    history.emplace(x, data[x]);
    history.emplace(y, data[y]);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k) {
    if(data[k] < 0) return (k);
    return (find(data[k]));
  }

  int size(int k) {
    return (-data[find(k)]);
  }

  void undo() {
    data[history.top().first] = history.top().second;
    history.pop();
    data[history.top().first] = history.top().second;
    history.pop();
  }

  void snapshot() {
    while(history.size()) history.pop();
  }

  void rollback() {
    while(history.size()) undo();
  }
};

int main() {
  int N, M, Q;
  cin >> N >> M >> Q;
  vector< int > X(M), Y(M);
  for(int i = 0; i < M; i++) {
    cin >> X[i] >> Y[i];
    --X[i], --Y[i];
  }
  MoRollBack mo(N, Q);
  for(int i = 0; i < Q; i++) {
    int l, r;
    cin >> l >> r;
    mo.add(--l, r);
  }

  UnionFindUndo uf(N + N);
  vector< int > ans(Q);
  int dame_sum = 0, dame_add = 0;
  vector< int > dame;
  auto add = [&](int idx) {
    uf.unite(X[idx], Y[idx] + N);
    uf.unite(X[idx] + N, Y[idx]);
    dame_add += uf.find(X[idx]) == uf.find(Y[idx]);
  };
  auto rem = [&](int idx) {
    ans[idx] = dame_sum + dame_add > 0;
  };
  auto reset = [&]() {
    uf = UnionFindUndo(N + N);
    dame_add = dame_sum = 0;
  };
  auto snapshot = [&]() {
    uf.snapshot();
    dame_sum += dame_add;
    dame_add = 0;
  };
  auto rollback = [&]() {
    uf.rollback();
    dame_add = 0;
  };
  mo.run(add, rem, reset, snapshot, rollback);
  for(auto &p : ans) {
    if(p) cout << "Impossible\n";
    else cout << "Possible\n";
  }
}