解題區/解題區 - Zerojudge

b493. 史蒂芙的外交夥伴

contents

  1. 1. Problem
    1. 1.1. 背景
    2. 1.2. 題目描述
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. 垃圾回收
    2. 4.2. 預先支付空間
    3. 4.3. 內存用盡

Problem

背景

史蒂芙終於有了夥伴，夥伴們各自為了人類國家出訪外交，在大陸版圖中有 $N$ 個小城市，每個城市都有各自的文明發展程度 $A_i$，史蒂芙的夥伴擁有各自能力 $K$ 只能選擇文明發展程度 $A_i$ 小於等於 $K$ 的國家拜訪。一開始國家跟國家之間彼此不相連，隨著外交拓展，小城市決定為史蒂芙的人類國家開一條道路通行另一個小城市，但如果這兩個小城市可以藉由直接相連或間接相連，那這一條道路將不會被建造。

礙於時間有限，史蒂芙手頭上有數個計劃，打算對起點城市到終點城市策劃行程，現在請你算出所有計畫的走訪個數。

題目描述

給定 $N$ 個城市版圖以及 $Q$ 個詢問，一開始城市彼此都不相連，詢問操作有以下兩種

  • 0 X Y 建造城市編號 X 到城市編號 Y 的雙向道路。如果 X 和 Y 本身已經直接相連或間接相連，則忽略此操作。
  • 1 X Y K 詢問路線 X 到 Y 的行程規劃，當夥伴的能力為 $K$ 能走訪的國家個數。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
7 11
1 5 2 6 3 7 4
0 2 4
0 1 2
0 1 3
0 3 7
1 4 7 3
1 7 4 5
0 2 5
0 5 3
1 1 4 5
0 1 4
1 7 4 6

Sample Output

1
2
3
4
2
0
2
3

Solution

在樹上套用函數式線段樹，維護有根樹和 LCA 的操作，將父節點的線段樹狀態傳遞給子節點進行持久化的變動，詢問 x 到 y 路徑時利用區間加減法，計算 x, y, LCA(x, y) 到根的符合條件的數量，統計一下即可。

由於一開始不是完整的一棵樹，會逐漸合成一棵樹，利用啟發式合併，也就是最傳統的合併操作，將小的集合合併到大的集合，合併複雜度為小集合的大小，那複雜度保證 $O(N \log N)$。

在套用函數式線段樹後，合併操作必須在 $O(N \log N)$ 時間完成，空間複雜度也是 $O(N \log N)$，因此完全所有合併操作需要 $O(N \log^2 N)$ 的時間，空間複雜度仍然是 $O(N \log N)$，若沒有搭配垃圾回收，空間會變成 $O(N \log^2 N)$ 的需求。

關於垃圾回收，建議使用 std::queue<> 完成，因為佔有空間少空間常數是 2，若使用 std::vector<> 空間常數是 2，但多餘的部分保證不會用到，就變得相當浪費。一旦支持垃圾回收，空間使用會逐漸變得不連續性，碎片化會造成 cache 的能力降低。速度上會慢上許多。若預先支付空間或者直接浪費 $O(N \log^2 N)$ 的空間都是可以被接受的方案。

在 LCA 計算，需要 $O(N \log N)$ 的時間建表以及 $O(N \log N)$ 的空間，詢問複雜度是 $O(\log N)$。若要降空間複雜度為 $O(N)$，可以用 Link/Cut Tree 代替，由於 splay tree 實作關係，時間複雜度常數略個三四倍。

垃圾回收

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <bits/stdc++.h> 
using namespace std;
class SegementTree {
public:
    static const int MAXN = 1000000;
    static const int MAXV = 50005;
    struct Node {
        Node *lson, *rson;
        int sum;
        Node() {
        	lson = rson = NULL;
        	sum = 0;
        }
    } _mem[MAXN];
    int L, R, V, mem_buf, mem_idx;
    queue<Node*> mem_bin[MAXV], bin;
    inline void clear_bin(int x) {
        while (!mem_bin[x].empty()) {
            recycle(mem_bin[x].front());
            mem_bin[x].pop();
        }
    }
    inline void recycle(Node *x) {
        bin.push(x);
    }
    Node* init(int l, int r, int v) {
        L = l, R = r, V = v;
        mem_buf = 0;
        for (int i = 0; i <= v; i++) {
            while (!mem_bin[i].empty())	mem_bin[i].pop();
        }
        while (!bin.empty())	bin.pop();
        Node* root = build(l, r);
        return root;
    }
    Node* newNode() {
        Node *u;
        if (mem_buf < MAXN) {
            u = &_mem[mem_buf++];
        } else {
            assert(!bin.empty());
            u = bin.front(), bin.pop();
        }
        *u = Node();
        mem_bin[mem_idx].push(u);
        return u;
    }
    Node* cloneNode(Node *p) {
        Node* u = newNode();
        *u = *p;
        return u;
    }
    Node* build(int l, int r) {
        if (l > r)  return NULL;
        Node *u = newNode();
        if (l == r) {
        } 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, int l, int r) {
        assert(p != NULL);
        Node *u = cloneNode(p);
        u->sum++;
        if (l == r) {
        } else {
        	int mid = (l + r)/2;
        	if (x <= mid)
            	u->lson = change(p->lson, x, l, mid);
        	else
         		u->rson = change(p->rson, x, mid+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x) {
        return change(p, x, L, R);
    }
    
    int QD;
    void find(Node *v1, int x, int l, int r) {
        if (1 <= l && r <= x) {
        	QD += v1->sum;
        	return ;
        }
        int mid = (l + r)/2;
        if (x <= mid) {
            find(v1->lson, x, l, mid);
        } else {
            find(v1->lson, x, l, mid);
            find(v1->rson, x, mid+1, r);
        }
    }
    int find(Node *v1, int x) {
        QD = 0;
        find(v1, x, L, R);
        return QD;
    }
} tree;
const int MAXN = 65536;
const int MAXLOGN = 17;
SegementTree::Node *root[MAXN];
int A[MAXN];
int fa[MAXLOGN][MAXN], dep[MAXN];
int parent[MAXN], weight[MAXN];
vector<int> g[MAXN];
void dfs(int u, int p, vector<int> &vA) {
    root[u] = tree.change(root[p], A[u]);
    fa[0][u] = p, dep[u] = dep[p] + 1;
    vA.push_back(u);
    for (auto v : g[u]) {
        if (v == p)	continue;
        dfs(v, u, vA);
    }
}
int findp(int x) {
    return x == parent[x] ? x : (parent[x]=findp(parent[x]));
}
int LCA(int x, int y) {
    if (dep[x] < dep[y])	swap(x, y);
    int d = dep[x] - dep[y];
    for (int i = MAXLOGN-1; i >= 0; i--) {
        if ((d>>i)&1) {
            d -= 1<<i;
            x = fa[i][x];
        }
    }
    if (x == y)	return x;
    for (int i = MAXLOGN-1; i >= 0; i--) {
        if (fa[i][x] != fa[i][y]) {
            x = fa[i][x], y = fa[i][y];
        }
    }
    return fa[0][x];
}
void merge(int X, int Y) {
    if (findp(X) == findp(Y))	return ;
    int rx, ry;
    rx = findp(X), ry = findp(Y);
    if (weight[rx] < weight[ry])	swap(rx, ry), swap(X, Y);
    g[X].push_back(Y), g[Y].push_back(X);
    // merge Y's group into X's group
    tree.clear_bin(ry), tree.mem_idx = rx;
    vector<int> vA;
    dfs(Y, X, vA);
    for (int i = 1; i < MAXLOGN; i++) {
        for (auto j : vA)
            fa[i][j] = fa[i-1][fa[i-1][j]];
    }	
    parent[ry] = rx, weight[rx] += weight[ry];
}
int path(int X, int Y, int K) {
    if (findp(X) != findp(Y))	return 0;
    int rx, ry, lca;
    rx = findp(X), ry = findp(Y);
    lca = LCA(X, Y);
    int ret = tree.find(root[X], K) + tree.find(root[Y], K) - tree.find(root[lca], K) * 2;
    ret += A[lca] <= K;
    return ret;
}
int main() {
    int N, Q, cmd;
    int X, Y, K;
    while (scanf("%d %d", &N, &Q) == 2) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &A[i]);
            
        for (int i = 1; i <= N; i++)
            parent[i] = i, weight[i] = 1, g[i].clear(), dep[i] = 0;
        for (int i = 0; i < MAXLOGN; i++)
            for (int j = 0; j <= N; j++)
                fa[i][j] = 0;
            
        tree.mem_idx = 0;
        root[0] = tree.init(1, N, N);
        for (int i = 1; i <= N; i++)
            root[i] = root[0];
        
        int d = 0;
        for (int i = 0; i < Q; i++) {
            scanf("%d %d %d", &cmd, &X, &Y);
            X ^= d, Y ^= d;
            if (cmd == 0) {
                merge(X, Y);
            } else {
                scanf("%d", &K), K ^= d;
                d = path(X, Y, K);
                printf("%d\n", d);
            }
        }
    }
    return 0;
}

預先支付空間

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <bits/stdc++.h> 
using namespace std;
int log2int(int x){
    return __builtin_clz((int)1)-__builtin_clz(x);
}
class SegementTree {
public:
    static const int MAXN = 1000000;
    static const int MAXV = 50005;
    struct Node {
        Node *lson, *rson;
        int sum;
        Node() {
        	lson = rson = NULL;
        	sum = 0;
        }
    } _mem[MAXN];
    int L, R, V, mem_idx;
    Node* init(int l, int r, int v) {
        L = l, R = r, V = v;
        mem_idx = 0;
        Node* root = build(l, r);
        return root;
    }
    inline Node* newNode() {
        Node *u = &_mem[mem_idx++];
        *u = Node();
        return u;
    }
//	inline Node* cloneNode(Node *p) {
//		Node *u = &_mem[mem_idx++];
//		*u = *p;
//		return u;
//	}
    Node* build(int l, int r) {
        if (l > r)  return NULL;
        Node *u = newNode();
        if (l == r) {
        } else {
            int m = (l + r)/2;
        	u->lson = build(l, m);
        	u->rson = build(m+1, r);
        }
        return u;
    }
    Node* change(Node *p, Node **sp, int x, int l, int r) {
//		Node *u = cloneNode(p);
        Node *u = *sp;
        *u = *p;
        u->sum++;
        if (l == r) {
        } else {
        	int mid = (l + r)/2;
        	if (x <= mid)
            	u->lson = change(p->lson, sp+1, x, l, mid);
        	else
         		u->rson = change(p->rson, sp+1, x, mid+1, r);
        }
        return u;
    }
    Node* change(Node *p, Node **sp, int x) {
        return change(p, sp, x, L, R);
    }
    
    int QD;
    void find(Node *v1, int x, int l, int r) {
        if (1 <= l && r <= x) {
        	QD += v1->sum;
        	return ;
        }
        int mid = (l + r)/2;
        if (x <= mid) {
            find(v1->lson, x, l, mid);
        } else {
            find(v1->lson, x, l, mid);
            find(v1->rson, x, mid+1, r);
        }
    }
    int find(Node *v1, int x) {
        QD = 0;
        find(v1, x, L, R);
        return QD;
    }
} tree;
const int MAXN = 50005;
const int MAXLOGN = 17;
SegementTree::Node *root[MAXN], *pre_mem[MAXN][MAXLOGN];
int A[MAXN];
int fa[MAXN][MAXLOGN], dep[MAXN];
int parent[MAXN], weight[MAXN];
vector<int> g[MAXN];
void dfs(int u, int p, vector<int> &vA) {
    root[u] = tree.change(root[p], pre_mem[u], A[u]);
    fa[u][0] = p, dep[u] = dep[p] + 1;
    vA.push_back(u);
    for (auto v : g[u]) {
        if (v == p)	continue;
        dfs(v, u, vA);
    }
}
int findp(int x) {
    return x == parent[x] ? x : (parent[x]=findp(parent[x]));
}
int LCA(int x, int y) {
    if (dep[x] < dep[y])	swap(x, y);
    int d = dep[x] - dep[y];
    int LOGN = log2int(dep[x]);
    for (int i = LOGN; i >= 0; i--) {
        if ((d>>i)&1)
            d -= 1<<i, x = fa[x][i];
    }
    if (x == y)	return x;
    for (int i = LOGN; i >= 0; i--) {
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    }
    return fa[x][0];
}
void merge(int X, int Y) {
    if (findp(X) == findp(Y))	return ;
    int rx, ry;
    rx = findp(X), ry = findp(Y);
    if (weight[rx] > weight[ry])	swap(rx, ry), swap(X, Y);
    g[X].push_back(Y), g[Y].push_back(X);
    // merge Y's group into X's group
    parent[rx] = ry, weight[ry] += weight[rx];
    vector<int> vA;
    dfs(X, Y, vA);
    int LOGN = log2int(weight[ry]);
    for (int i = 1; i <= LOGN; i++) {
        for (auto j : vA)
            fa[j][i] = fa[fa[j][i-1]][i-1];
    }	
}
int path(int X, int Y, int K) {
    if (findp(X) != findp(Y))	return 0;
    int lca = LCA(X, Y);
    int ret = tree.find(root[X], K) + tree.find(root[Y], K) - tree.find(root[lca], K) * 2;
    ret += A[lca] <= K;
    return ret;
}
int main() {
    int N, Q, cmd;
    int X, Y, K;
    while (scanf("%d %d", &N, &Q) == 2) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &A[i]);
            
        for (int i = 1; i <= N; i++)
            parent[i] = i, weight[i] = 1, g[i].clear(), dep[i] = 0;
        for (int i = 0; i < MAXLOGN; i++)
            for (int j = 0; j <= N; j++)
                fa[j][i] = 0;
            
        root[0] = tree.init(1, N, N);
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < MAXLOGN; j++)
                pre_mem[i][j] = tree.newNode();
            root[i] = tree.change(root[0], pre_mem[i], A[i]);
        }
        
        int d = 0;
        for (int i = 0; i < Q; i++) {
            scanf("%d %d %d", &cmd, &X, &Y);
            X ^= d, Y ^= d;
            if (cmd == 0) {
                merge(X, Y);
            } else {
                scanf("%d", &K);
                K ^= d;
                d = path(X, Y, K);
                printf("%d\n", d);
            }
        }
    }
    return 0;
}

內存用盡

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <bits/stdc++.h> 
using namespace std;
int log2int(int x) {
    return __builtin_clz((int)1)-__builtin_clz(x);
}
class SegementTree {
public:
    static const int MAXN = 7000000;
    static const int MAXV = 50005;
    struct Node {
        Node *lson, *rson;
        int sum;
        Node() {
        	lson = rson = NULL;
        	sum = 0;
        }
    } _mem[MAXN];
    int L, R, V, mem_idx;
    Node* init(int l, int r, int v) {
        L = l, R = r, V = v;
        mem_idx = 0;
        Node* root = build(l, r);
        return root;
    }
    inline Node* newNode() {
        Node *u = &_mem[mem_idx++];
        *u = Node();
        return u;
    }
    inline Node* cloneNode(Node *p) {
        Node *u = &_mem[mem_idx++];
        *u = *p;
        return u;
    }
    Node* build(int l, int r) {
        if (l > r)  return NULL;
        Node *u = newNode();
        if (l == r) {
        } 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, int l, int r) {
        Node *u = cloneNode(p);
        u->sum++;
        if (l == r) {
        } else {
        	int mid = (l + r)/2;
        	if (x <= mid)
            	u->lson = change(p->lson, x, l, mid);
        	else
         		u->rson = change(p->rson, x, mid+1, r);
        }
        return u;
    }
    Node* change(Node *p, int x) {
        return change(p, x, L, R);
    }
    
    int QD;
    void find(Node *v1, int x, int l, int r) {
        if (1 <= l && r <= x) {
        	QD += v1->sum;
        	return ;
        }
        int mid = (l + r)/2;
        if (x <= mid) {
            find(v1->lson, x, l, mid);
        } else {
            find(v1->lson, x, l, mid);
            find(v1->rson, x, mid+1, r);
        }
    }
    int find(Node *v1, int x) {
        QD = 0;
        find(v1, x, L, R);
        return QD;
    }
} tree;
const int MAXN = 50005;
const int MAXLOGN = 16;
SegementTree::Node *root[MAXN];
int A[MAXN];
int fa[MAXLOGN][MAXN], dep[MAXN];
int parent[MAXN], weight[MAXN];
vector<int> g[MAXN];
void dfs(int u, int p, vector<int> &vA) {
    root[u] = tree.change(root[p], A[u]);
    fa[0][u] = p, dep[u] = dep[p] + 1;
    vA.push_back(u);
    for (auto v : g[u]) {
        if (v == p)	continue;
        dfs(v, u, vA);
    }
}
int findp(int x) {
    return x == parent[x] ? x : (parent[x]=findp(parent[x]));
}
int LCA(int x, int y) {
    if (dep[x] < dep[y])	swap(x, y);
    int d = dep[x] - dep[y];
    int LOGN = log2int(dep[x]);
    for (int i = LOGN; i >= 0; i--) {
        if ((d>>i)&1)
            d -= 1<<i, x = fa[i][x];
    }
    if (x == y)	return x;
    for (int i = LOGN; i >= 0; i--) {
        if (fa[i][x] != fa[i][y])
            x = fa[i][x], y = fa[i][y];
    }
    return fa[0][x];
}
void merge(int X, int Y) {
    if (findp(X) == findp(Y))	return ;
    int rx, ry;
    rx = findp(X), ry = findp(Y);
    if (weight[rx] < weight[ry])	swap(rx, ry), swap(X, Y);
    g[X].push_back(Y), g[Y].push_back(X);
    // merge Y's group into X's group
    parent[ry] = rx, weight[rx] += weight[ry];
    vector<int> vA;
    dfs(Y, X, vA);
    int LOGN = log2int(weight[rx]);
    for (int i = 1; i <= LOGN; i++) {
        for (auto j : vA)
            fa[i][j] = fa[i-1][fa[i-1][j]];
    }	
}
int path(int X, int Y, int K) {
    if (findp(X) != findp(Y))	return 0;
    int lca = LCA(X, Y);
    int ret = tree.find(root[X], K) + tree.find(root[Y], K) - tree.find(root[lca], K) * 2;
    ret += A[lca] <= K;
    return ret;
}
int main() {
    int N, Q, cmd;
    int X, Y, K;
    while (scanf("%d %d", &N, &Q) == 2) {
        for (int i = 1; i <= N; i++)
            scanf("%d", &A[i]);
            
        for (int i = 1; i <= N; i++)
            parent[i] = i, weight[i] = 1, g[i].clear(), dep[i] = 0;
        for (int i = 0; i < MAXLOGN; i++)
            for (int j = 0; j <= N; j++)
                fa[i][j] = 0;
            
        root[0] = tree.init(1, N, N);
        for (int i = 1; i <= N; i++)
            root[i] = root[0];
        
        int d = 0;
        for (int i = 0; i < Q; i++) {
            scanf("%d %d %d", &cmd, &X, &Y);
            X ^= d, Y ^= d;
            if (cmd == 0) {
                merge(X, Y);
            } else {
                scanf("%d", &K);
                K ^= d;
                d = path(X, Y, K);
                printf("%d\n", d);
            }
        }
    }
    return 0;
}