data-structure/range-union-find.hpp

• View this file on GitHub
• Last update: 2020-12-05 07:59:51+09:00
• Include: #include "data-structure/range-union-find.hpp"

Verified with

• verify/verify-yuki/yuki-1170.test.cpp

Code

#pragma once

struct RangeUnionFind {
  vector<int> data, left, right;
  RangeUnionFind(int N) : data(N, -1) {
    left.resize(N);
    right.resize(N);
    iota(begin(left), end(left), 0);
    iota(begin(right), end(right), 1);
  }

  int find(int k) { return data[k] < 0 ? k : data[k] = find(data[k]); }

  int unite(int x, int y) {
    if ((x = find(x)) == (y = find(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    left[x] = min(left[x], left[y]);
    right[x] = max(right[x], right[y]);
    return true;
  }

  // unite [l, r)
  void range_unite(int l, int r) {
    if ((l = max(l, 0)) >= (r = min(r, (int)data.size()))) return;
    int m;
    while ((m = right[find(l)]) < r) {
      assert(left[find(m)] == m);
      unite(l, m);
    }
  }

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

  int same(int x, int y) { return find(x) == find(y); }
};

#line 2 "data-structure/range-union-find.hpp"

struct RangeUnionFind {
  vector<int> data, left, right;
  RangeUnionFind(int N) : data(N, -1) {
    left.resize(N);
    right.resize(N);
    iota(begin(left), end(left), 0);
    iota(begin(right), end(right), 1);
  }

  int find(int k) { return data[k] < 0 ? k : data[k] = find(data[k]); }

  int unite(int x, int y) {
    if ((x = find(x)) == (y = find(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    left[x] = min(left[x], left[y]);
    right[x] = max(right[x], right[y]);
    return true;
  }

  // unite [l, r)
  void range_unite(int l, int r) {
    if ((l = max(l, 0)) >= (r = min(r, (int)data.size()))) return;
    int m;
    while ((m = right[find(l)]) < r) {
      assert(left[find(m)] == m);
      unite(l, m);
    }
  }

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

  int same(int x, int y) { return find(x) == find(y); }
};

Back to top page