cp-includes

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub rsalesc/cp-includes

:warning: RangeDSU.cpp

Depends on

Code

#ifndef _LIB_RANGE_DSU
#define _LIB_RANGE_DSU
#include <bits/stdc++.h>
#include "SegtreeFast.cpp"
#include "DSU.cpp"

namespace lib {
using namespace std;
struct RangeDSU {
  struct NodeImpl {
    int low, high;
    int low_inv, high_inv;
    friend NodeImpl operator+(const NodeImpl& a, const NodeImpl& b) {
      NodeImpl res = a;
      if(b.low < res.low) res.low = b.low, res.low_inv = b.low_inv;
      if(b.high > res.high) res.high = b.high, res.high_inv = b.high_inv;
      return res;
    }
  };
  using Node = seg::Active<NodeImpl>;

  seg::SegtreeFast<Node, seg::CombineFolder<Node>> sg;
  FastDSU dsu;
  vector<vector<int>> inv;

  RangeDSU(int n) : sg(seg::make_builder(n)), dsu(n), inv(n) {
    // TODO: optimize
    for(int i = 0; i < n; i++) {
      sg.update_element(i, seg::SetUpdater<NodeImpl>(node_impl(i)));
      inv[i].push_back(i);
    }
  }

  NodeImpl node_impl(int i) {
    int u = dsu[i];
    return NodeImpl{u, u, i, i};
  }

  void activate(int i) {
    sg.update_element(i, seg::ActiveUpdater<Node>(true));
  }

  void deactivate(int i) {
    sg.update_element(i, seg::ActiveUpdater<Node>(false));
  }

  int operator[](int i) {
    return dsu[i];
  }

  bool merge(int u, int v) {
    if(!dsu.merge(u, v)) return false;
    tie(u, v) = dsu.last_merge();
    for(int x : inv[u]) {
      inv[v].push_back(x);
      sg.update_element(x, seg::SetUpdater<NodeImpl>(node_impl(x)));
    }
    return true;
  }

  int merge_range(int i, int j, int x) {
    x = dsu[x];
    Node res = sg.query<Node>(i, j, seg::CombineFolder<Node>());
    if(!res.is_active()) return -1;
    if(res.low != x) {
      merge(res.low, x);
      return res.low_inv;
    }
    if(res.high != x) {
      merge(res.high, x);
      return res.high_inv;
    }
    return -1;
  }

  void merge_all_range(int i, int j, int x) {
    while(merge_range(i, j, x) != -1);
  }

  pair<int, int> last_merge() const { return dsu.last_merge(); }
  vector<int> last_move() const { return inv[last_merge().first]; }
};
} // namespace lib

#endif
#line 1 "RangeDSU.cpp"


#include <bits/stdc++.h>
#line 1 "SegtreeFast.cpp"


#line 1 "Segtree.cpp"


#line 4 "Segtree.cpp"

namespace lib {
using namespace std;
namespace seg {
struct LeafBuilder {
  template <typename Node> void operator()(Node &no, int i) const {}
  inline pair<int, int> range() const { return {0, 0}; }
  bool should_build() const { return true; }
};

struct EmptyLeafBuilder : LeafBuilder {
  int n;
  explicit EmptyLeafBuilder(int n) : n(n) {}
  inline pair<int, int> range() const { return {0, n - 1}; }
  bool should_build() const { return true; }
};

struct ImplicitBuilder : LeafBuilder {
  int L, R;
  explicit ImplicitBuilder(int L, int R) : L(L), R(R) {}
  inline pair<int, int> range() const { return {L, R}; }
  bool should_build() const { return false; }
};

// TODO: NOT IMPLEMENTED
template <typename DefaultNode>
struct ImplicitWithDefaultBuilder : LeafBuilder {
  int L, R;
  DefaultNode default_node;
  explicit ImplicitWithDefaultBuilder(int L, int R, DefaultNode def)
      : L(L), R(R), default_node(def) {}

  template <typename Node> inline void operator()(Node &no, int i) const {
    no = default_node;
  }

  inline pair<int, int> range() const { return {L, R}; }
  bool should_build() const { return false; }
};

template <typename RandomIterator> struct RangeLeafBuilder : LeafBuilder {
  RandomIterator begin, end;
  explicit RangeLeafBuilder(RandomIterator begin, RandomIterator end)
      : begin(begin), end(end) {}

  template <typename Node> inline void operator()(Node &no, int i) const {
    no = *(begin + i);
  }

  inline pair<int, int> range() const { return {0, end - begin - 1}; }
};

template <typename F> struct LambdaLeafBuilder : LeafBuilder {
  F f;
  pair<int, int> rng;
  explicit LambdaLeafBuilder(F f, pair<int, int> range)
      : f(f), rng(range) {}

  template <typename Node> inline void operator()(Node &no, int i) const {
    no = f(i);
  }

  inline pair<int, int> range() const { return rng; }
};

EmptyLeafBuilder make_builder(int n) { return EmptyLeafBuilder(n); }

template <typename RandomIterator>
RangeLeafBuilder<RandomIterator> make_builder(RandomIterator begin,
                                              RandomIterator end) {
  return RangeLeafBuilder<RandomIterator>(begin, end);
}

template <typename T>
RangeLeafBuilder<typename vector<T>::const_iterator>
make_builder(const vector<T> &v) {
  return RangeLeafBuilder<typename vector<T>::const_iterator>(v.begin(),
                                                              v.end());
}

template<typename T>
LambdaLeafBuilder<std::function<T(int)>>
make_builder(std::function<T(int)> f, pair<int, int> range) {
  return LambdaLeafBuilder<std::function<T(int)>>(f, range);
}

template <typename T> struct CombineFolder {
  inline T operator()() const { return T(); }

  template <typename Node> inline T operator()(const Node &no) const {
    return T(no);
  }

  inline T operator()(const T &a, const T &b) const { return a + b; }
};

template <typename T> struct EmptyFolder : CombineFolder<T> {
  using CombineFolder<T>::operator();

  template <typename Node> inline T operator()(const Node &no) const {
    return T();
  }
  inline T operator()(const T &a, const T &b) const { return T(); }
};

template <typename T> struct SumFolder : CombineFolder<T> {};

template <typename T> struct ProductFolder : CombineFolder<T> {
  using CombineFolder<T>::operator();
  inline T operator()() const { return T(1); }
  inline T operator()(const T &a, const T &b) const { return a * b; }
};

template <typename T> struct MaxFolder : CombineFolder<T> {
  using CombineFolder<T>::operator();
  inline T operator()() const { return numeric_limits<T>::min(); }
  inline T operator()(const T &a, const T &b) const { return max(a, b); }
};

template <typename T> struct MinFolder : CombineFolder<T> {
  using CombineFolder<T>::operator();
  inline T operator()() const { return numeric_limits<T>::max(); }
  inline T operator()(const T &a, const T &b) const { return min(a, b); }
};

template <typename T> struct SingleValueUpdater {
  T value;
  explicit SingleValueUpdater(T val) : value(val) {}
};

template <typename T> struct SetUpdater : SingleValueUpdater<T> {
  using SingleValueUpdater<T>::SingleValueUpdater;

  template <typename Node> inline void operator()(Node &no) const {
    no = this->value;
  }
};

template <typename T> struct AddUpdater : SingleValueUpdater<T> {
  using SingleValueUpdater<T>::SingleValueUpdater;

  template <typename Node> inline void operator()(Node &no) const {
    no += this->value;
  }
};

template <typename T> struct MultUpdater : SingleValueUpdater<T> {
  using SingleValueUpdater<T>::SingleValueUpdater;

  template <typename Node> inline void operator()(Node &no) const {
    no *= this->value;
  }
};

struct EmptyPushdown {
  template<typename Node>
  inline bool dirty(const Node& no) const { return false; }

  template<typename Node>
  inline void operator()(Node& no, int l, int r, 
                  Node* ln, Node* rn) const {}
};

template<typename Node>
struct Active : public Node {
  bool active_ = false;
  Active& operator=(const Node& no) {
    Node::operator=(no);
    return *this;
  }
  bool is_active() const { return active_; }
  Active& activate() {
    active_ = true;
    return *this;
  }
  Active& deactivate() {
    active_ = false;
    return *this;
  }
  void toggle() {
    active_ = !active_;
  }
  friend Active<Node> operator+(const Active<Node>& a, const Active<Node>& b) {
    if(!a.active_) return b;
    else if(!b.active_) return a;
    Active<Node> res;
    res = Node(a) + Node(b);
    return res.activate();
  }
};

template <typename T>
struct ActiveUpdater {
  bool flag;

  ActiveUpdater(bool f) : flag(f) {}

  template <typename Node> inline void operator()(Node &no) const {
    no.active_ = flag;
  }
};
}  // namespace seg
}  // namespace lib


#line 5 "SegtreeFast.cpp"

namespace lib {
using namespace std;
namespace seg {
template <typename Node, typename CombinerFn> struct SegtreeFastBase {
  const static int MULTIPLIER = 2;

  CombinerFn combiner_fn;

  vector<Node> t;
  int L, n;

  SegtreeFastBase() {}
  template <typename Builder> explicit SegtreeFastBase(const Builder &builder) {
    pair<int, int> range = builder.range();
    L = range.first;
    n = range.second - range.first + 1;
    assert(n > 0);
    t = vector<Node>(n * MULTIPLIER);
    build(builder);
  }

  template <typename Builder> void build(const Builder &builder) {
    for (int i = n; i < 2 * n; i++)
      builder(t[i], L + i - n);
    for (int i = n - 1; i > 0; i--)
      t[i] = combiner_fn(t[i << 1], t[i << 1 | 1]);
  }

  template <typename Rebuilder> void rebuild(const Rebuilder &rebuilder) {
    for (int i = n; i < 2 * n; i++)
      rebuilder(t[i]);
    for (int i = n - 1; i > 0; i--)
      rebuilder(t[i], t[i << 1], t[i << 1 | 1]);
  }
};

template <typename Node, typename CombinerFn>
struct SegtreeFast : SegtreeFastBase<Node, CombinerFn> {
  typedef SegtreeFastBase<Node, CombinerFn> Base;
  using Base::combiner_fn;
  using Base::L;
  using Base::n;
  using Base::SegtreeFastBase;
  using Base::t;

  template <typename Updater>
  void update_element(int i, const Updater &updater) {
    i -= L;
    assert(i >= 0);
    for (updater(t[i += n]); i /= 2;)
      t[i] = combiner_fn(t[i << 1], t[i << 1 | 1]);
  }

  template <typename T, typename Folder>
  T query(int i, int j, const Folder &folder) {
    // input is [i, j]
    i -= L, j -= L;
    assert(i >= 0 && j >= 0);
    i += n, j += n;
    if (i == j)
      return folder(t[i]);
    T resl = folder(t[i]), resr = folder(t[j]);

    // now it is [i, j)
    i++;
    while (i < j) {
      if (i & 1)
        resl = folder(resl, folder(t[i++]));
      if (j & 1)
        resr = folder(folder(t[--j]), resr);
      i /= 2, j /= 2;
    }

    return folder(resl, resr);
  }
};

template <typename Node>
struct SegtreeFastSplash : SegtreeFastBase<Node, EmptyFolder<Node>> {
  typedef SegtreeFastBase<Node, EmptyFolder<Node>> Base;
  using Base::L;
  using Base::n;
  using Base::SegtreeFastBase;
  using Base::t;

  template <typename T, typename Folder>
  T query_element(int i, const Folder &folder) {
    i -= L;
    assert(i >= 0);
    T res = folder(t[i += n]);
    while (i /= 2) {
      res = folder(folder(t[i]), res);
    }
    return res;
  }

  template <typename Updater>
  void splash(int i, int j, const Updater &updater) {
    // input is [i, j]
    i -= L, j -= L;
    assert(i >= 0 && j >= 0);
    // now it is [i, j)
    i += n, j += n + 1;

    while (i < j) {
      if (i & 1)
        updater(t[i++]);
      if (j & 1)
        updater(t[--j]);
      i /= 2, j /= 2;
    }
  }
};

} // namespace seg
} // namespace lib


#line 1 "DSU.cpp"


#line 4 "DSU.cpp"

namespace lib {
using namespace std;

struct DSU {
  vector<int> p, ptime, sz;
  int tempo = 0;
  int merges = 0;
  pair<int, int> last_merge_ = {-1, -1};

  DSU(int n = 0) : p(n), ptime(n, 1e9), sz(n, 1) { iota(p.begin(), p.end(), 0); }

  int make_node() {
    int i = p.size();
    p.emplace_back(i);
    ptime.emplace_back(0);
    sz.emplace_back(1);
    return 1;
  }

  int get(int i, int at) const {
    return p[i] == i ? i : (at >= ptime[i] ? get(p[i], at) : i);
  }

  int operator[](int i) const { return get(i, tempo); }

  int merge(int u, int v) {
    u = (*this)[u], v = (*this)[v];
    if (u == v)
      return 0;
    if (sz[u] < sz[v])
      swap(u, v);
    p[v] = u;
    ptime[v] = ++tempo;
    sz[u] += sz[v];
    last_merge_ = {v, u};
    merges++;
    return 1;
  }
  pair<int, int> last_merge() const {
    return last_merge_;
  }

  int n_comps() const { return (int)p.size() - merges; }
};

struct CompressedDSU {
  vector<int> p;
  CompressedDSU(int n = 0) : p(n) { iota(p.begin(), p.end(), 0); }
  int get(int i) {
    return p[i] == i ? i : p[i] = get(p[i]);
  }
  int operator[](int i) { return get(i); }
  int& parent(int i) { return p[i]; }
};

struct FastDSU {
  vector<int> p, sz;
  int merges = 0;
  pair<int, int> last_merge_ = {-1, -1};
  FastDSU(int n = 0) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }

  int get(int i) {
    return p[i] == i ? i : p[i] = get(p[i]);
  }
  int operator[](int i) { return get(i); }

  int merge(int u, int v) {
    u = get(u), v = get(v);
    if(u == v) return 0;
    if(sz[u] < sz[v])
      swap(u, v);
    p[v] = u;
    sz[u] += sz[v];
    merges++;
    last_merge_ = {v, u};
    return 1;
  }
  pair<int, int> last_merge() const {
    return last_merge_;
  }
  int n_comps() const { return (int)p.size() - merges; }
};
} // namespace lib


#line 6 "RangeDSU.cpp"

namespace lib {
using namespace std;
struct RangeDSU {
  struct NodeImpl {
    int low, high;
    int low_inv, high_inv;
    friend NodeImpl operator+(const NodeImpl& a, const NodeImpl& b) {
      NodeImpl res = a;
      if(b.low < res.low) res.low = b.low, res.low_inv = b.low_inv;
      if(b.high > res.high) res.high = b.high, res.high_inv = b.high_inv;
      return res;
    }
  };
  using Node = seg::Active<NodeImpl>;

  seg::SegtreeFast<Node, seg::CombineFolder<Node>> sg;
  FastDSU dsu;
  vector<vector<int>> inv;

  RangeDSU(int n) : sg(seg::make_builder(n)), dsu(n), inv(n) {
    // TODO: optimize
    for(int i = 0; i < n; i++) {
      sg.update_element(i, seg::SetUpdater<NodeImpl>(node_impl(i)));
      inv[i].push_back(i);
    }
  }

  NodeImpl node_impl(int i) {
    int u = dsu[i];
    return NodeImpl{u, u, i, i};
  }

  void activate(int i) {
    sg.update_element(i, seg::ActiveUpdater<Node>(true));
  }

  void deactivate(int i) {
    sg.update_element(i, seg::ActiveUpdater<Node>(false));
  }

  int operator[](int i) {
    return dsu[i];
  }

  bool merge(int u, int v) {
    if(!dsu.merge(u, v)) return false;
    tie(u, v) = dsu.last_merge();
    for(int x : inv[u]) {
      inv[v].push_back(x);
      sg.update_element(x, seg::SetUpdater<NodeImpl>(node_impl(x)));
    }
    return true;
  }

  int merge_range(int i, int j, int x) {
    x = dsu[x];
    Node res = sg.query<Node>(i, j, seg::CombineFolder<Node>());
    if(!res.is_active()) return -1;
    if(res.low != x) {
      merge(res.low, x);
      return res.low_inv;
    }
    if(res.high != x) {
      merge(res.high, x);
      return res.high_inv;
    }
    return -1;
  }

  void merge_all_range(int i, int j, int x) {
    while(merge_range(i, j, x) != -1);
  }

  pair<int, int> last_merge() const { return dsu.last_merge(); }
  vector<int> last_move() const { return inv[last_merge().first]; }
};
} // namespace lib
Back to top page