CF1140F-Extending Set of Points
题目:
题目描述:
For a given set of two-dimensional points $ S $ , let’s denote its extension $ E(S) $ as the result of the following algorithm:
Create another set of two-dimensional points $ R $ , which is initially equal to $ S $ . Then, while there exist four numbers $ x_1 $ , $ y_1 $ , $ x_2 $ and $ y_2 $ such that $ (x_1, y_1) \in R $ , $ (x_1, y_2) \in R $ , $ (x_2, y_1) \in R $ and $ (x_2, y_2) \notin R $ , add $ (x_2, y_2) $ to $ R $ . When it is impossible to find such four integers, let $ R $ be the result of the algorithm.
Now for the problem itself. You are given a set of two-dimensional points $ S $ , which is initially empty. You have to process two types of queries: add some point to $ S $ , or remove some point from it. After each query you have to compute the size of $ E(S) $ .
输入格式:
The first line contains one integer $ q $ ( $ 1 \le q \le 3 \cdot 10^5 $ ) — the number of queries.
Then $ q $ lines follow, each containing two integers $ x_i $ , $ y_i $ ( $ 1 \le x_i, y_i \le 3 \cdot 10^5 $ ), denoting $ i $ -th query as follows: if $ (x_i, y_i) \in S $ , erase it from $ S $ , otherwise insert $ (x_i, y_i) $ into $ S $ .
输出格式:
Print $ q $ integers. $ i $ -th integer should be equal to the size of $ E(S) $ after processing first $ i $ queries.
样例:
样例输入1:
1
2
3
4
5
6
7
8
9
|
7
1 1
1 2
2 1
2 2
1 2
1 3
2 1
|
样例输出1:
思路:
我们将原来的$(x, y)$这个点转化为一条$x\to y(x代表行, y代表列)$的边, 然后发现答案为每一个连通块中x的个数*y的个数 的总和. 用线段树分治维护每条边出现的时间, 并查集维护连通性
实现:
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
| // Problem: CF1140F Extending Set of Points
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1140F
// Memory Limit: 1000 MB
// Time Limit: 3500 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/ios.h"
map<pair<int, int>, int> ss;
const int maxn = 6e5 + 10;
vector<pair<int, int>> q[maxn << 2];
void add(int p, int l, int r, int ll, int rr, pair<int, int> d)
{
if (l > rr || r < ll)
return;
if (ll <= l && r <= rr)
{
q[p].push_back(d);
return;
}
int mid = l + r >> 1;
if (ll <= mid)
add(p << 1, l, mid, ll, rr, d);
if (rr > mid)
add(p << 1 | 1, mid + 1, r, ll, rr, d);
}
int top;
int s[maxn];
int n;
int f[maxn], xc[maxn], yc[maxn];
int find(int x)
{
if (x == f[x])
return x;
return find(f[x]);
}
long long ans;
void merge(int x, int y)
{
int sx = find(x), sy = find(y);
if (sx == sy)
return;
ans -= 1ll * xc[sx] * yc[sx] + 1ll * xc[sy] * yc[sy];
if (xc[sx] + yc[sx] > xc[sy] + yc[sy])
swap(sx, sy);
s[++top] = sx;
f[sx] = sy;
xc[sy] += xc[sx];
yc[sy] += yc[sx];
ans += 1ll * xc[sy] * yc[sy];
}
void solve(int p, int l, int r)
{
int tmp = top;
for (auto x : q[p])
{
int a = x.first, b = x.second;
merge(a, b + 3e5);
}
if (l == r)
yout << ans << " ";
else
{
int mid = l + r >> 1;
solve(p << 1, l, mid);
solve(p << 1 | 1, mid + 1, r);
}
while (top > tmp)
{
int x = s[top], y = f[s[top]];
ans -= 1ll * xc[y] * yc[y];
f[x] = x;
xc[y] -= xc[x];
yc[y] -= yc[x];
ans += 1ll * xc[y] * yc[y] + 1ll * xc[x] * yc[x];
--top;
}
}
int main()
{
yin >> n;
for (int i = 1; i <= 6e5; i++)
{
f[i] = i;
xc[i] = (i <= 3e5);
yc[i] = !xc[i];
}
for (int i = 1; i <= n; i++)
{
int x, y;
yin >> x >> y;
pair<int, int> t = make_pair(x, y);
if (ss[t])
{
add(1, 1, n, ss[t], i - 1, t);
ss[t] = 0;
}
else
ss[t] = i;
}
for (auto x : ss)
if (x.second != 0)
add(1, 1, n, x.second, n, x.first);
solve(1, 1, n);
return 0;
}
|