【APIO2019】桥梁

题目链接

【APIO2019】桥梁

做法

考虑对询问分块,选择块大小为 $ S $ ,每次对块内的操作进行处理。因此对于之前的修改可以预处理出来。
对于块内询问,将所有没有在这个块内修改的边按权值大到小排序,将询问按权值大到小排序,然后用两个指针维护。若此时指向边权大于询问的权值,则加入一条边;否则询问。
考虑加入可能被修改的边。按照时间将边进行修改,然后将边权权不小于询问权值的边加入,在进行询问。这部分可以暴力进行。考虑做完后需要撤销操作,所以需要用按秩合并的并查集。
这样询问的复杂度为 $ O(S^3 log n + m log n) $ 。
考虑对边修改后进行排序。暴力排序时间复杂度 $ O(n sqrt{n} log n) $ ,而分类后归并排序时间复杂度 $ O(n sqrt{n log n}) $ ,此时 $ S = sqrt{n log n} $ 最优。

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

using namespace std;
const int N = 100010, BLO = 700;
int n, m, q, fa[N], sz[N], ans[N], pos[N];
struct {
int x, y, w, id; inline bool operator<(const Edge &yy)const { return w > yy.w; }
}; Edge e[N], a1[N], a2[N];
struct Q {
int opt, x, y, id; inline bool operator<(const Q &yy)const { return y > yy.y; }
}; Q qry[N], qq[N]; int len, pre[N];
struct S {
int id, fa, sz; S(int x = 0, int y = 0, int z = 0) : id(x), fa(y), sz(z) {}
}; S sta[N]; int top = 0;
bool used[N];

void gi(int &x) {
x = 0; register char c = getchar(); for(; c < '0' || c > '9'; c = getchar());
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
}
int Find(int x) { return x == fa[x] ? x : Find(fa[x]); }
void Union(int x, int y) {
x = Find(x), y = Find(y); if(x == y) return ;
if(sz[x] > sz[y]) swap(x, y);
sta[++top] = S(x, fa[x], sz[x]), fa[x] = y, sz[y] += sz[x];
}
inline void Undo() {
S u = sta[top--]; sz[fa[u.id]] -= u.sz, fa[u.id] = u.fa, sz[u.id] = u.sz;
}
int main() {
gi(n), gi(m);
for(int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
for(int i = 1; i <= m; i++) gi(e[i].x), gi(e[i].y), gi(e[i].w), e[i].id = i;
gi(q);
for(int i = 1; i <= q; i++)
gi(qry[i].opt), gi(qry[i].x), gi(qry[i].y), qry[i].id = i;
sort(e + 1, e + m + 1); for(int i = 1; i <= m; i++) pos[e[i].id] = i;
for(int l = 1, r; l <= q; l += BLO) {
r = min(q, l + BLO - 1), len = 0;
for(int i = 1; i <= m; i++) used[i] = 0;
for(int i = l; i <= r; i++) {
if(qry[i].opt == 2) qq[++len] = qry[i]; else used[qry[i].x] = 1;
}
stable_sort(qq + 1, qq + len + 1);
int p1 = 1, p2 = 1;
for(; p1 <= m || p2 <= len;) {
for(; p1 <= m && used[e[p1].id]; ++p1);
if(p1 > m && p2 > len) continue;
if(p2 > len || (p1 <= m && e[p1].w >= qq[p2].y)) Union(e[p1].x, e[p1].y), ++p1;
else {
int cur = top, ps = l - 1;
for(int i = l; i <= r && i <= qq[p2].id; i++) {
ps = i;
if(qry[i].opt == 1)
pre[qry[i].id] = e[pos[qry[i].x]].w, e[pos[qry[i].x]].w = qry[i].y;
}
for(int i = l; i <= r; i++)
if(qry[i].opt == 1 && e[pos[qry[i].x]].w >= qq[p2].y)
Union(e[pos[qry[i].x]].x, e[pos[qry[i].x]].y);
ans[qq[p2].id] = sz[Find(qq[p2].x)];
for(int i = ps; i >= l; i--)
if(qry[i].opt == 1) e[pos[qry[i].x]].w = pre[qry[i].id];
for(; top > cur; Undo()); ++p2;
}
}
for(; top; Undo());
for(int i = l; i <= r; i++) if(qry[i].opt == 1) e[pos[qry[i].x]].w = qry[i].y;
int len1 = 0, len2 = 0;
for(int i = 1; i <= m; i++) {
if(used[e[i].id]) a1[++len1] = e[i]; else a2[++len2] = e[i];
}
sort(a1 + 1, a1 + len1 + 1), p1 = p2 = 1;
for(int i = 1; i <= m; i++) {
if(p2 > len2 || (p1 <= len1 && a1[p1] < a2[p2])) e[i] = a1[p1++];
else if(p2 <= len2) e[i] = a2[p2++];
}
for(int i = 1; i <= m; i++) pos[e[i].id] = i;
}
for(int i = 1; i <= q; i++) if(ans[i]) printf("%dn", ans[i]);
return 0;
}