【APIO2019】桥梁

发表于 更新于 本文字数： 3.1k 阅读时长 ≈ 3 分钟
https://www.luogu.org/problem/P5443

题目链接

【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
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, BLO = 700;
int n, m, q, fa[N], sz[N], ans[N], pos[N];
struct Edge {
	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("%d\n", ans[i]);
	return 0;
}