CF1140F 题解

link
一个点集 $S = (x_i, y_i)$ 的张集定义如下：

  • 刚开始张集等于 $S$；
  • 若对于点 $(x, y)$ ，存在 $(a, b)$，使得 $(a, b)$ 、 $(a, y)$ 、 $(x, b)$ 属于张集，则将 $(x, y)$ 加入张集；
  • 重复上述操作直到不能操作，此时集合即为 $S$ 的张集。
    现在有 $q$ 次操作每次操作会添加或删除一个点， 求每次操作后张集点的个数。
    $1 \le q, x_i, y_i \le 3 \times 10^5$。

首先一个肯定不好处理，转换成 $x_i$ 向 $y_i$ 连边，把集合对应一个图。

这样每个点都是一个横点（$x$）向一个纵点（$y$）连边，因此这个图任何时刻都是一个二分图（当然可以有多个联通块）。

接下来有个结论：$S$ 的张集所对应的图，就是 $S$ 对应的二分图的完全二分图。

这里给出一个比较感性的证明。我们回到点的角度，将点放到坐标系中：

对于直角形的结构，显然可以再得到一个点，像这样：

所以，我们可以一直加，直到点形成一个矩形的形状，这时候才没有可以加的点了：

然后发现，矩形就对应了一个完全二分图，得证。

对于完全二分图，边数就是二分图左右边边数的乘积。

因此，现在问题转换成了对一个二分图维护加边，删边，查询左右边数的乘积。

这时候把每条边在时间上转为一个区间，利用线段树分治，即时间建立线段树，将这条边用 $\tt{vector}$ 挂在 $\log$ 个节点上。

这样有什么好处呢？这样的话对于任意一个时刻，可以用线段树上根到这个叶子的所有节点所挂的边不重不漏得包含所有这个时刻拥有的所有边。

这就很妙了啊，我们就可以从根节点开始 $\tt{dfs}$ ，插入所有边同时更新答案，并且在 $\tt{dfs}$ 回溯时撤销边，$\tt{dfs}$ 到根节点记录答案，就可以用 $\Theta (n \log n)$ 的时间计算出答案了！

到了这个地步我们已经离答案很近了。现在问题又转换成了维护加边，撤销边，同时更新二分图左右边数。你会发现，这不就是可撤销并查集做的事情吗？因此最后用可撤销并查集维护这个东西，这道题就做完了！！！

CODE

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
#include <bits/stdc++.h>
using namespace std;
#define int long long

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
	return f ? -x : x;
}

#define PII pair<int, int> 
#define fi first
#define se second
#define mp make_pair
#define Q 300010

int q, fa[Q << 1], sz1[Q << 1], sz2[Q << 1], ans = 0, res[Q];
stack<PII > st;
struct node { int t, x, y; }e[Q];

void mem() {
	for (int i = 1; i <= 2 * q; i ++) {
		fa[i] = i;
		sz1[i] = (i <= q);
		sz2[i] = (i > q);
	}
}
int getF(int x) {
	return fa[x] == x ? x : getF(fa[x]);
}
void add(int x, int y) {
	int u = getF(x), v = getF(y + q);
	if (sz1[u] + sz2[u] > sz1[v] + sz2[v]) swap(u, v);
	st.push(mp(u, v));
	if (u == v) return;
	ans -= sz1[v] * sz2[v];
	ans -= sz1[u] * sz2[u];
	fa[u] = fa[v];
	sz1[v] += sz1[u];
	sz2[v] += sz2[u];
	ans += sz1[v] * sz2[v];
}
void del() {
	int u = st.top().fi, v = st.top().se;
	st.pop();
	if (u == v) return;
	ans -= sz1[v] * sz2[v];
	fa[u] = u;
	sz1[v] -= sz1[u];
	sz2[v] -= sz2[u];
	ans += sz1[u] * sz2[u];
	ans += sz1[v] * sz2[v];
}

#define lid (id << 1)
#define rid (id << 1 | 1)
struct Segment {
	int l, r;
	vector<PII > e;
}tr[Q * 4];
void Build(int id, int l, int r) {
	tr[id].l = l, tr[id].r = r;
	if (tr[id].l == tr[id].r) return;
	int mid = tr[id].l + tr[id].r >> 1;
	Build(lid, l, mid), Build(rid, mid + 1, r);
}
void Add(int id, int l, int r, int x, int y) {
	if (l <= tr[id].l && tr[id].r <= r) {
		tr[id].e.emplace_back(x, y);
		return;
	}
	int mid = tr[id].l + tr[id].r >> 1;
	if (l <= mid) Add(lid, l, r, x, y);
	if (r > mid) Add(rid, l, r, x, y);
}
void dfs(int id) {
	for (auto x : tr[id].e) add(x.fi, x.se);
	if (tr[id].l == tr[id].r) res[tr[id].l] = ans;
	else dfs(lid), dfs(rid);
	for (auto x : tr[id].e) del();
}

signed main() {
	q = read(), Build(1, 1, q);
	for (int i = 1; i <= q; i ++) {
		e[i].x = read(), e[i].y = read(), e[i].t = i;
	}
	sort(e + 1, e + q + 1, [](node a, node b) {
		if (a.x != b.x) return a.x < b.x;
		if (a.y != b.y) return a.y < b.y;
		return a.t < b.t;
	});
	for (int i = 1, f = 0; i <= q; i ++) {
		if (e[i - 1].x == e[i].x && e[i - 1].y == e[i].y && f) { f = 0; continue; }
		if (e[i + 1].x == e[i].x && e[i + 1].y == e[i].y) Add(1, e[i].t, e[i + 1].t - 1, e[i].x, e[i].y), f = 1;
		else Add(1, e[i].t, q, e[i].x, e[i].y);
	}

	mem(), dfs(1);
	for (int i = 1; i <= q; i ++) printf("%lld ", res[i]);
	puts("");
	return 0;
}