bzoj3673: 可持久化并查集 by zky

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <stdexcept>
#include <cstring>

using namespace std;

// #define RA_DO_HANDLE_EXCEPTION 1
// #define RA_MALLOC_ON_DEMAND 1
// #define RA_UNLIMITED_TIMESTAMPS 1

template <typename _Type>
class retroactive_array
{
private:
    // Constants, only used if required
    static const int _node_pool_size = 1000100;
    static const int _timestamp_size = 20100;
    // Segment tree structural implementation
    class ra_node {
    public:
        _Type value;
        ra_node *lc, *rc;
    };
    int _size;
    #ifdef RA_UNLIMITED_TIMESTAMPS
    std::map<int, ra_node*> root;
    #else
    ra_node* root[_timestamp_size];
    #endif
    // Node allocation units
    #ifdef RA_MALLOC_ON_DEMAND
    ra_node* alloc_node(void)
    {
        ra_node *p = new ra_node;
        return p;
    }
    #else
    ra_node _node_pool[_node_pool_size];
    int _node_pool_cntr;
    ra_node* alloc_node(void)
    {
        #ifdef RA_DO_HANDLE_EXCEPTION
        if (_node_pool_cntr >= _node_pool_size)
            throw std::out_of_range("Memory pool overflow");
        #endif
        ra_node *p = &_node_pool[_node_pool_cntr++];
        return p;
    }
    #endif
    // Recursive tree building unit
    typedef _Type gen_function(int);
    ra_node* build_tree(int l, int r, gen_function func)
    {
        ra_node *p = this->alloc_node();
        if (l == r) {
            p->value = func(l);
            return p;
        }
        int mid = (l + r) >> 1;
        p->lc = this->build_tree(l, mid, func);
        p->rc = this->build_tree(mid + 1, r, func);
        return p;
    }
    // Querying data from structure
    _Type query(ra_node *p, int l, int r, int pos)
    {
        if (l == r)
            return p->value;
        int mid = (l + r) >> 1;
        if (pos <= mid)
            return this->query(p->lc, l, mid, pos);
        else
            return this->query(p->rc, mid + 1, r, pos);
    }
    // Modifying data in structure
    ra_node* modify(ra_node *p, int l, int r, int pos, _Type val)
    {
        // Creating clone of this node
        ra_node *q = this->alloc_node();
        q->value = p->value;
        q->lc = p->lc;
        q->rc = p->rc;
        // Working on segment tree
        if (l == r) {
            q->value = val;
            return q;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            q->lc = this->modify(q->lc, l, mid, pos, val);
        else
            q->rc = this->modify(q->rc, mid + 1, r, pos, val);
        return q;
    }
private:
    // Maintaining functions for invoking upper-level retroactive array
    // functions on I/O
    size_t get_size(void)
    {
        return this->_size;
    }
    bool has_time(int time)
    {
        if (this->root[time] == NULL)
            return false;
        return true;
    }
    void create_fork(int time, int time_old = 0)
    {
        if (time == time_old)
            return ;
        #ifdef RA_DO_HANDLE_EXCEPTION
        if (this->root[time_old] == NULL)
            throw std::out_of_range("Unexpected time of fork source supplied.");
        #endif
        if (this->root[time] != NULL)
            return ;
        ra_node *o_root = this->root[time_old];
        ra_node *c_root = this->alloc_node();
        // Copy data for duplication
        c_root->value = o_root->value;
        c_root->lc = o_root->lc;
        c_root->rc = o_root->rc;
        // Putting back into map
        this->root[time] = c_root;
        return ;
    }
    _Type get_data(int time, int pos)
    {
        #ifdef RA_DO_HANDLE_EXCEPTION
        if (pos < 0 || pos > this->_size)
            throw std::out_of_range("Indexing limits out of bound.");
        #endif
        // Retrieving root at position
        ra_node *c_root = this->root[time];
        #ifdef RA_DO_HANDLE_EXCEPTION
        if (c_root == NULL)
            throw std::out_of_range("Unexpected time supplied.");
        #endif
        // Getting data
        _Type res = this->query(c_root, 1, _size, pos);
        return res;
    }
    void set_data(int time, int pos, _Type val)
    {
        #ifdef RA_DO_HANDLE_EXCEPTION
        if (pos < 0 || pos > this->_size)
            throw std::out_of_range("Indexing limits out of bound.");
        #endif
        // Retrieving root at position
        ra_node *c_root = this->root[time];
        #ifdef RA_DO_HANDLE_EXCEPTION
        if (c_root == NULL)
            throw std::out_of_range("Please create a fork before setting data.");
        #endif
        // Modifying data
        c_root = this->modify(c_root, 1, _size, pos, val);
        this->root[time] = c_root;
        return ;
    }
    void init_array(int n, gen_function func)
    {
        this->_size = n;
        ra_node *c_root = this->build_tree(1, _size, func);
        #ifdef RA_UNLIMITED_TIMESTAMPS
        this->root.clear();
        #else
        memset(root, 0, sizeof(root));
        #endif
        this->root[0] = c_root;
        return ;
    }
    _Type _default_zero;
    _Type _zero_override_func(int in) {
        return _default_zero; }
    void init_array(int n, _Type zero)
    {
        this->_default_zero = zero;
        this->init_array(n, _zero_override_func);
        return ;
    }
// protected:
public:
    // Data wrapper for positions (third-level)
    class ra_val_wrapper {
    protected:
        retroactive_array* _ra;
        int _time, _pos;
    public:
        ra_val_wrapper(retroactive_array* _ra, int _time, int _pos) {
            this->_ra = _ra;
            this->_time = _time;
            this->_pos = _pos;
            return ; }
        ra_val_wrapper& operator = (ra_val_wrapper in) {
            *this = _Type(in);
            return *this; }
        ra_val_wrapper& operator = (_Type in) {
            this->_ra->set_data(this->_time, this->_pos, in);
            return *this; }
        operator _Type (void) {
            _Type val = this->_ra->get_data(this->_time, this->_pos);
            return val; }
    };
    // Data wrapper for time (second-level)
    class ra_time_wrapper {
    protected:
        retroactive_array* _ra;
        int _time;
    public:
        ra_time_wrapper(retroactive_array* _ra, int _time) {
            this->_ra = _ra;
            this->_time = _time;
            return ; }
        ra_val_wrapper operator [] (int pos) {
            ra_val_wrapper rvw(this->_ra, this->_time, pos);
            return rvw; }
    };
    // Wrapping time
    ra_time_wrapper call_time_wrapper(int time)
    {
        // Checking if fork required
        this->create_fork(time);
        // Returning wrapper
        ra_time_wrapper rtw(this, time);
        return rtw;
    }
public:
    retroactive_array(void) {
        this->_size = 0;
        #ifndef RA_MALLOC_ON_DEMAND
        memset(_node_pool, 0, sizeof(_node_pool));
        _node_pool_cntr = 0;
        #endif
        return ; }
    retroactive_array(int n, _Type zero) {
        this->init_array(n, zero);
        return ; }
    void init(int n, gen_function func) {
        this->init_array(n, func);
        return ; }
    void init(int n, _Type zero) {
        this->init_array(n, zero);
        return ; }
    size_t size(void) {
        return this->get_size(); }
    _Type get(int time, int pos) {
        return this->get_data(time, pos); }
    void set(int time, int pos, _Type val) {
        this->set_data(time, pos, val);
        return ; }
    void fork(int time, int time_old = 0) {
        this->create_fork(time, time_old);
        return ; }
    ra_time_wrapper operator [] (int time) {
        return this->call_time_wrapper(time); }
};

struct rds_unit {
    int par, size;
    rds_unit(void) { par = size = 0; }
    rds_unit(int _1, int _2) { par = _1, size = _2; }
};
rds_unit ra_generator(int pos) {
    rds_unit ru(pos, 1);
    return ru;
}

class retroactive_disjoint_set
{
private:
    int n;
    retroactive_array<rds_unit> ra;
public:
    void fork(int time, int time_old = 0) {
        ra.fork(time, time_old);
        return ; }
    int find(int time, int p)
    {
        rds_unit q_ru = ra.get(time, p);
        int q = q_ru.par;
        if (p == q)
            return p;
        return find(time, q);
    }
    bool joined(int time, int p, int q)
    {
        p = find(time, p);
        q = find(time, q);
        if (p == q)
            return true;
        return false;
    }
    void join(int time, int p, int q)
    {
        p = find(time, p);
        q = find(time, q);
        if (p == q)
            return ;
        rds_unit p_ru = ra.get(time, p),
                 q_ru = ra.get(time, q);
        // Ensure rank balance
        if (p_ru.size > q_ru.size)
            std::swap(p, q),
            std::swap(p_ru, q_ru);
        // Joining
        q_ru.size += p_ru.size;
        p_ru.par = q;
        ra.set(time, p, p_ru);
        ra.set(time, q, q_ru);
        return ;
    }
    void init(int n)
    {
        this->n = n;
        ra.init(n, ra_generator);
        return ;
    }
};

retroactive_disjoint_set rds;

int n, m;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    rds.init(n);
    int last = 0;
    for (int i = 1; i <= m; i++) {
        int func, a, b;
        scanf("%d", &func);
        if (func == 1) {
            scanf("%d%d", &a, &b);
            // a = a ^ last;
            // b = b ^ last;
            rds.fork(i, i - 1);
            rds.join(i, a, b);
        } else if (func == 2) {
            scanf("%d", &a);
            // a = a ^ last;
            rds.fork(i, a);
        } else if (func == 3) {
            scanf("%d%d", &a, &b);
            // a = a ^ last;
            // b = b ^ last;
            rds.fork(i, i - 1);
            last = rds.joined(i, a, b);
            printf("%d\n", last);
        }
    }
    return 0;
}