解題區/解題區 - Zerojudge

b412. 記憶中的并查集

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

維護一個並查集的操作，並且支持版本回溯。

  • 合併兩個堆
  • 詢問兩個元素是否同堆
  • 版本回溯

Sample Input

1
2
3
4
5
6
2 5
2 1 2
1 1 2
2 1 2
1 1
3 0 3

Sample Output

1
2
3
0
1
0

Solution

持久化概念，相當於維護 parent[] 陣列的版本，這一點可以利用可持久化線段樹來維護。

並查集的查詢功能不修改 parent[] 陣列，合併操作卻有可能修改數個 parent[]，為了降低記憶體用量，盡可能少用路徑壓縮這個技巧，雖然在一般並查集都會使用這個來加速，否則很容易變很慢，是因為持久化是會拉低速度，因為持久化需要 $O(\log N)$ 的時間去更改 parent[]，單筆路徑壓縮長度為 $M$ 個點，需要 $O(M \log N)$ 的調整，$M$ 在並查集中是常數類。

詢問不多時用啟發式合併就好，將小堆的元素合併到大堆中。效能會比較好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
const int MAXN = 3000000;
class SegementTree {
public:
    struct Node {
        Node *lson, *rson;
        pair<int, int> val;
    } nodes[MAXN];
    int nodesize, L, R;
    Node* init(int l, int r) {
        nodesize = 0;
        L = l, R = r;
        Node* root = build(l, r);
        return root;
    }
    Node* newNode() {
        if (nodesize >= MAXN)
            exit(0);
        return &nodes[nodesize++];
    }
    Node* cloneNode(Node *p) {
        if (nodesize >= MAXN)
            exit(0);
        Node* u = &nodes[nodesize++];
        *u = *p;
        return u;
    }
    Node* build(int l, int r) {
        if (l > r)  return NULL;
        Node *u = newNode();
        u->lson = u->rson = NULL;
        if (l == r) {
            u->val = make_pair(l, 1);
        } else {
            int m = (l + r)/2;
        	u->lson = build(l, m);
        	u->rson = build(m+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x, pair<int, int> val, int l, int r) {
        Node *u = cloneNode(p);
        if (l == r) {
        	u->val = val;
        } else {
        	int mid = (l + r)/2;
        	if (x <= mid)
            	u->lson = change(p->lson, x, val, l, mid);
        	else
         		u->rson = change(p->rson, x, val, mid+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x, pair<int, int> val) {
        return change(p, x, val, L, R);
    }
    pair<int, int> find(Node *ver, int x, int l, int r) {
        if (l == r)
        	return ver->val;
        int mid = (l + r)/2;
        if (x <= mid)
            return find(ver->lson, x, l, mid);
        else
            return find(ver->rson, x, mid+1, r);
    }
    pair<int, int> find(Node *ver, int x) {
        return find(ver, x, L, R);
    }
    // disjoint set
    pair<int, int> findp(Node *ver, int x) {
        pair<int, int> p = find(ver, x);
        return x == p.first ? p : findp(ver, p.first);
    }
    Node* joint(Node *ver, int x, int y) {
        pair<int, int> a = findp(ver, x);
        pair<int, int> b = findp(ver, y);
        if (a.first == b.first)
            return ver;
        Node *u = ver;
        if (a.second > b.second) {
            u = change(u, b.first, make_pair(a.first, b.second));
            u = change(u, a.first, make_pair(a.first, a.second + b.second));
        } else {
            u = change(u, a.first, make_pair(b.first, a.second));
            u = change(u, b.first, make_pair(b.first, a.second + b.second));
        }
        return u;
    }
} segTree;
const int MAXQ = 262144;
SegementTree::Node *ver[MAXQ];
int main() {
    int n, m;
    int cmd, x, y, v;
    while (scanf("%d %d", &n, &m) == 2) {
        ver[0] = segTree.init(1, n);
        int encrypt = 0;
        for (int i = 1; i <= m; i++) {
            scanf("%d", &cmd);
            cmd ^= encrypt;
            if (cmd == 0) { 		// back
                scanf("%d", &v);
                v ^= encrypt;
                ver[i] = ver[v];
            } else if (cmd == 1) {	// joint
                scanf("%d %d", &x, &y);
                x ^= encrypt, y ^= encrypt; 
                ver[i] = segTree.joint(ver[i-1], x, y);
            } else if (cmd == 2) {	// find
                scanf("%d %d", &x, &y);
                x ^= encrypt, y ^= encrypt;
                pair<int, int> a = segTree.findp(ver[i-1], x);
                pair<int, int> b = segTree.findp(ver[i-1], y);
                int t = a.first == b.first;
                printf("%d\n", t);
                ver[i] = ver[i-1];
                encrypt = t;
            } else {
                puts("WTF");
                return 0;
            }
        }
    }
    return 0;
}