ei1333の日記

ぺこい

ちょっと変わったセグメント木の使い方

「競プロ!!」 競技プログラミング Advent Calendar 2017 の 14 日目の記事です。

adventar.org

補足 実装例

スライドに載せたコードの実装例を載せてあります。

モノイドをのせるセグメント木(RMQ) [p13,p15]

struct SegNode
{
  int v;

  SegNode(int v) : v(v) {}

  SegNode operator*(const SegNode &r) const
  {
    return (v < r.v ? *this : r);
  }
} e(1 << 30);

struct SegmentTree
{
  int sz;
  vector< SegNode > seg;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, e);
  }

  void update(int k, const SegNode &x)
  {
    k += sz - 1;
    seg[k] = x;
    while(k > 0) {
      k = (k - 1) >> 1;
      seg[k] = seg[2 * k + 1] * seg[2 * k + 2];
    }
  }

  SegNode query(int a, int b, int k, int l, int r)
  {
    if(r <= a || b <= l) return (e);
    if(a <= l && r <= b) return (seg[k]);
    return (query(a, b, 2 * k + 1, l, (l + r) >> 1) * query(a, b, 2 * k + 2, (l + r) >> 1, r));
  }

  SegNode query(int a, int b)
  {
    return (query(a, b, 0, 0, sz));
  }
};

区間内かつ x 以下の値を持つ要素のうち最右の位置を見つける二分探索 [p22]

struct SegNode
{
  int v;

  SegNode(int v) : v(v) {}

  SegNode operator*(const SegNode &r) const
  {
    return (v < r.v ? *this : r);
  }
} e(1 << 30);

struct SegmentTree
{
  int sz;
  vector< SegNode > seg;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, e);
  }

  void update(int k, const SegNode &x)
  {
    k += sz - 1;
    seg[k] = x;
    while(k > 0) {
      k = (k - 1) >> 1;
      seg[k] = seg[2 * k + 1] * seg[2 * k + 2];
    }
  }

  SegNode query(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return (e);
    if(a <= l && r <= b) return (seg[k]);
    return (query(a, b, 2 * k + 1, l, (l + r) >> 1) * query(a, b, 2 * k + 2, (l + r) >> 1, r));
  }

  SegNode query(int a, int b)
  {
    return (query(a, b, 0, 0, sz));
  }

  int find(int a, int b, int x, int k, int l, int r)
  {
    if(seg[k].v > x || r <= a || b <= l) return (-1);
    if(k >= sz - 1) return (k - (sz - 1));
    int rv = find(a, b, x, 2 * k + 2, (l + r) >> 1, r);
    if(rv != -1) return (rv);
    return (find(a, b, x, 2 * k + 1, l, (l + r) >> 1));
  }

  int find(int a, int b, int x)
  {
    return (find(a, b, x, 0, 0, sz));
  }
};

Dynamic-connectivity [p74]

using edge = pair< int, int >;

struct UnionFind
{
  vector< int > data;
  stack< pair< int, int > > st;

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

  bool unite(int x, int y)
  {
    x = find(x), y = find(y);
    st.emplace(x, data[x]);
    st.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[st.top().first] = st.top().second;
    st.pop();
    data[st.top().first] = st.top().second;
    st.pop();
  }
};


struct Dynamic_connectivity
{
  UnionFind uf;
  int n, sz;
  vector< vector< edge > > edges;

  vector< pair< pair< int, int >, edge > > pending;
  map< edge, int > cnt, appear;

  Dynamic_connectivity(int n, int q) : n(q), uf(n) // (2018-03-21修正)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    edges.resize(2 * sz - 1);
  }

  void insert(int idx, edge e)
  {
    if(e.first > e.second) swap(e.first, e.second);
    if(cnt[e]++ == 0) appear[e] = idx;
  }

  void erase(int idx, edge e)
  {
    if(e.first > e.second) swap(e.first, e.second);
    if(--cnt[e] == 0) pending.emplace_back(make_pair(appear[e], idx), e);
  }

  void add(int a, int b, const edge &e, int k, int l, int r)
  {
    if(r <= a || b <= l) return;
    if(a <= l && r <= b) {
      edges[k].emplace_back(e);
      return;
    }
    add(a, b, e, 2 * k + 1, l, (l + r) >> 1);
    add(a, b, e, 2 * k + 2, (l + r) >> 1, r);
  }

  void add(int a, int b, const edge &e)
  {
    add(a, b, e, 0, 0, sz);
  }

  void build()
  {
    for(auto &p : cnt) {
      if(p.second > 0) pending.emplace_back(make_pair(appear[p.first], sz), p.first);
    }
    for(auto &s : pending) {
      add(s.first.first, s.first.second, s.second);
    }
  }

  void execute(const function< void(int) > &f, int k = 0)
  {
    for(auto &e : edges[k]) {
      int a, b;
      tie(a, b) = e;
      uf.unite(a, b);
    }
    if(k < sz - 1) {
      execute(f, 2 * k + 1);
      execute(f, 2 * k + 2);
    } else if(k - (sz - 1) < n) {
      int query_index = k - (sz - 1);
      f(query_index);
    }
    for(auto &e : edges[k]) {
      uf.undo();
    }
  }
};

辺の追加削除でデータを変換するのがわりと虚無なので, insert(クエリ時刻, edge), erase(クエリ時刻, edge) を呼び出してすべての辺を追加削除した後に, build() を呼び出すことでいい感じにデータを変換してセグメント木に辺をはるようになっています。

(verified:
Dynamic connectivity contest A. Connect and Disconnect http://codeforces.com/gym/100551/submission/33216575)

Fractional-cascading [p99,p104,p105]

struct SegmentTreeFractionalCascading
{
  vector< vector< int > > seg;
  vector< vector< int > > L, R;
  int sz;

  SegmentTreeFractionalCascading(vector< vector< int > > &array)
  {
    sz = 1;
    while(sz < array.size()) sz <<= 1;
    seg.resize(2 * sz - 1);
    L.resize(2 * sz - 1);
    R.resize(2 * sz - 1);
    for(int k = 0; k < array.size(); k++) {
      seg[k + sz - 1] = array[k];
      sort(begin(seg[k + sz - 1]), end(seg[k + sz - 1]));
    }
    for(int k = sz - 2; k >= 0; k--) {
      seg[k].resize(seg[2 * k + 1].size() + seg[2 * k + 2].size());
      L[k].resize(seg[k].size() + 1);
      R[k].resize(seg[k].size() + 1);
      merge(begin(seg[2 * k + 1]), end(seg[2 * k + 1]), begin(seg[2 * k + 2]), end(seg[2 * k + 2]), begin(seg[k]));
      int tail1 = 0, tail2 = 0;
      for(int i = 0; i < seg[k].size(); i++) {
        L[k][i] = tail1, R[k][i] = tail2;
        if(tail1 < seg[2 * k + 1].size() && seg[2 * k + 1][tail1] == seg[k][i]) {
          ++tail1;
        } else {
          ++tail2;
        }
      }
      L[k][seg[k].size()] = (int) seg[2 * k + 1].size();
      R[k][seg[k].size()] = (int) seg[2 * k + 2].size();
    }
  }

  int query(int a, int b, int lower, int upper, int k, int l, int r)
  {
    if(r <= a || b <= l) {
      return (0);
    } else if(a <= l && r <= b) {
      return (upper - lower);
    } else {
      return (query(a, b, L[k][lower], L[k][upper], 2 * k + 1, l, (l + r) >> 1) + query(a, b, R[k][lower], R[k][upper], 2 * k + 2, (l + r) >> 1, r));
    }
  }

  int query(int a, int b, int l, int r)
  {
    l = lower_bound(begin(seg[0]), end(seg[0]), l) - begin(seg[0]);
    r = lower_bound(begin(seg[0]), end(seg[0]), r) - begin(seg[0]);
    return (query(a, b, l, r, 0, 0, sz));
  }
};