【luogu CF1140F】Extending Set of Points（线段树分治）

Extending Set of Points

题目链接：luogu CF1140F

题目大意

有一个点集，有一个扩展操作是加入符合条件的 (x0,y0) 直到不能加入位置。
符合条件是原来 (x0,y0) 不存在而且存在 (a,b) 使得 (a,b),(a,y0),(x0,b) 都在点集中。
然后一开始点集为空，会加入或者删除点集，每次问你如果要扩展最后点集有多少个点，注意不会真的扩展。

思路

考虑到怎样会扩展，就是你比如有一列的点，列的位置是一个集合 S，然后某个位置的点所在的行有一个点。
那这个点的那里一列上所有 S 集合上的位置最后都会扩展的有点。

那你发现，如果行和列给它分别建点，然后一个点就把它所在的行和列连边。
首先是二分图，接着你根据上面的性质，其实只要某个行点能走到某个列点，那这个行列的位置就会有点。
那总结一下最后会形成一个类似矩形，每个行的和每个列的线形成的所有交点都有点。
那就是你行点的个数乘列点的个数。

于是处理好了一次的情况，考虑多次询问。
发现是插入和删除，那每个点出现的时刻是一个区间。
然后并查集的话你要删除也不是不行，改成按秩合并。
但是要按顺序删除，按栈的顺序，所以我们上线段树分治即可。

代码

#include
#include
#include
#define ll long long

using namespace std;

const int N = 3e5 + 100;
int n;
map <pair <int, int>, int> a;
ll ans[N];

struct Bing_cha_ji {
	int sta[N], fa[N << 1];
	ll ans, nx[N << 1], ny[N << 1];
	
	void Init() {
		for (int i = 1; i <= n + n; i++) fa[i] = i;
		for (int i = 1; i <= n; i++) nx[i] = 1, ny[i + n] = 1;
	}
	
	int find(int now) {
		if (fa[now] == now) return now;
		return find(fa[now]);
	}
	
	void insert(pair <int, int> W) {
		int x = W.first, y = W.second + n;
		x = find(x); y = find(y); if (x == y) return ;
		ans -= nx[x] * ny[x] + nx[y] * ny[y];
		if (nx[x] + ny[x] <= nx[y] + ny[y]) swap(x, y);
		fa[y] = x; sta[++sta[0]] = y; nx[x] += nx[y]; ny[x] += ny[y];
		ans += nx[x] * ny[x];
	}
	
	void pop() {
		int y = sta[sta[0]--], x = fa[y];
		ans -= nx[x] * ny[x];
		nx[x] -= nx[y]; ny[x] -= ny[y];
		fa[y] = y; ans += nx[x] * ny[x] + nx[y] * ny[y];
	}
}B;

struct XD_tree {
	vector <pair<int, int> > f[N << 2];
	
	void insert(int now, int l, int r, int L, int R, pair <int, int> x) {
		if (L <= l && r <= R) {
			f[now].push_back(x); return ;
		}
		int mid = (l + r) >> 1;
		if (L <= mid) insert(now << 1, l, mid, L, R, x);
		if (mid < R) insert(now << 1 | 1, mid + 1, r, L, R, x);
	}
	
	void build(int now, int l, int r) {
		int lst = B.sta[0];
		for (int i = 0; i < f[now].size(); i++) B.insert(f[now][i]);
		if (l == r) {
			ans[l] = B.ans;
			while (B.sta[0] > lst) B.pop();
			return ;
		}
		int mid = (l + r) >> 1;
		build(now << 1, l, mid); build(now << 1 | 1, mid + 1, r);
		while (B.sta[0] > lst) B.pop();
	}
}T;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int x, y; scanf("%d %d", &x, &y);
		if (!a[make_pair(x, y)]) {
			a[make_pair(x, y)] = i;
		}
		else {
			T.insert(1, 1, n, a[make_pair(x, y)], i - 1, make_pair(x, y));
			a.erase(make_pair(x, y));
		}
	}
	for (map <pair <int, int>, int> ::iterator it = a.begin(); it != a.end(); it++) T.insert(1, 1, n, it->second, n, it->first);
	
	B.Init(); T.build(1, 1, n);
	for (int i = 1; i <= n; i++) printf("%lld ", ans[i]);
	
	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