Data Structure

Disjoint Set Union

支援操作：

  1. void init(int n)
    • 初始化點集合為 ，代表 -base 或 -base 皆可
  2. int R(int x)
    • 均攤 回傳 所在的集合的 boss 並路徑壓縮
  3. int U(int x, int y)
    • 均攤 合併 與 所在的集合，合併成功回傳 ，否則回傳
Code 
struct DSU {
    
    vector<int> p;
    int maxn;
    
    void init(int N) {
        maxn = N + 1;
        p.resize(maxn), iota(ALL(p), 0);
    }
    
    int R(int x) { return x ^ p[x] ? p[x] = R(p[x]) : x; }
    int U(int x, int y) { return (x = R(x)) ^ (y = R(y)) ? p[x] = y, 1 : 0; }
    
};

Disjoint Set Union with Undo

支援操作：

  1. void init(int n)
    • 初始化點集合為 ，代表 -base 或 -base 皆可
  2. int R(int x)
    • 回傳 所在的集合的 boss
  3. int U(int x, int y)
    • 啟發式 合併 與 所在的集合，合併成功回傳 ，否則回傳
  4. void undo()
    • 回復上一次的有效 U(x, y) 操作
Code 
struct DSU {
    
    vector<int> p, sz;
    vector<tuple<int, int, int, int>> ops;
    int maxn;
    
    void init(int N) {
        maxn = N + 1;
        p.resize(maxn), iota(ALL(p), 0);
        sz.assign(maxn, 1);
    }
    
    int R(int x) { return p[x] ^ x ? R(p[x]) : x; }
    
    int U(int x, int y) {
        x = R(x), y = R(y);
        if (x == y) return 0;
        if (sz[x] > sz[y]) swap(x, y);
        ops.eb(x, y, p[x], sz[y]);
        return sz[y] += sz[x], p[x] = y, 1;
    }
    
    void undo() {
        auto [x, y, p_x, sz_y] = ops.back(); ops.pb();
        p[x] = p_x, sz[y] = sz_y;
    }
    
};
Code with 離散化 
struct DSU {
    
    vector<int> p, sz;
    vector<tuple<int, int, int, int>> ops;
    vector<int> disc;
    int maxn;
    
    void init(const vector<int> _disc) {
        disc = _disc, maxn = SZ(disc);
        p.resize(maxn), iota(ALL(p), 0);
        sz.assign(maxn, 1);
    }
    
    int _R(int x) { return p[x] ^ x ? _R(p[x]) : x; }
    int R(int x) {
        int id_x = lower_bound(ALL(disc), x) - begin(disc);
        return _R(id_x);
    }
    
    int _U(int x, int y) {
        x = _R(x), y = _R(y);
        if (x == y) return 0;
        if (sz[x] > sz[y]) swap(x, y);
        ops.eb(x, y, p[x], sz[y]);
        return sz[y] += sz[x], p[x] = y, 1;
    }
    int U(int x, int y) {
        int id_x = lower_bound(ALL(disc), x) - begin(disc);
        int id_y = lower_bound(ALL(disc), y) - begin(disc);
        return _U(id_x, id_y);
    }
    
    void undo() {
        auto [x, y, p_x, sz_y] = ops.back(); ops.pb();
        p[x] = p_x, sz[y] = sz_y;
    }
    
};

Interval Container

宣告：

  • IntervalContainer<int> itv;
    • 儲存 int 型別的資訊

支援操作：

  1. void cut(int p)
    • 將 跟 切開（helper function，應該不會被直接呼叫）
  2. void modify(int l, int r, T v)
    • 將 區間的值修改為
  3. vector<pair<pii, T>> get(int l, int r)
    • 取得 區間的值
  4. vector<pair<pii, T>> remove(int l, int r)
    • 將 區間的值移除，並回傳被移除的區間與值
Code 
template <typename T>
struct IntervalContainer {
    
    map<pii, T> itv;
    
    void cut(int p) { /// cut [p-1, p]
        auto it = itv.lower_bound({p, p});
        if (it == begin(itv)) return;
        if (it != end(itv) and it->first.first == p) return;
        it = prev(it);
        if (it->first.second < p) return;
        auto [lr, v] = *it; auto [l, r] = lr;
        it = itv.erase(it);
        it = itv.emplace_hint(it, pii(l, p-1), v);
        it = itv.emplace_hint(it, pii(p, r), v);
    }
    
    void modify(int l, int r, T v) {
        cut(l), cut(r+1);
        auto it_L = itv.lower_bound({l, l});
        auto it_R = itv.lower_bound({r+1, r+1});
        auto it = itv.erase(it_L, it_R);
        itv.emplace_hint(it, pii(l, r), v);
    }
    
    vector<pair<pii, T>> get(int l, int r) {
        cut(l), cut(r+1);
        auto it_L = itv.lower_bound({l, l});
        auto it_R = itv.lower_bound({r+1, r+1});
        vector<pair<pii, T>> ret;
        while (it_L != it_R) ret.eb(*it_L), it_L = next(it_L);
        return ret;
    }
    
    vector<pair<pii, T>> remove(int l, int r) {
        cut(l), cut(r+1);
        auto it_L = itv.lower_bound({l, l});
        auto it_R = itv.lower_bound({r+1, r+1});
        vector<pair<pii, T>> ret;
        while (it_L != it_R) ret.eb(*it_L), it_L = itv.erase(it_L);
        return ret;
    }
    
};