题意描述
平面直角坐标系的第一象限内有一块左下角为 \((0,0)\) 右上角为 \((10^{100},10^{100})\)
的矩形区域，区域内有正偶数个整点，试求出这样一条从
\((0,0)\) 出发，到 \((10^{100},10^{100})\)
的在区域内部的折线：
- 折线的每一部分都平行于 \(x\) 轴或
\(y\) 轴。
- 折线不能经过给定的整点。
- 折线将整块区域分成包含给定整点个数相等的两块。
- 折线拥有尽可能少的折点。
可以证明一定存在一条满足限制的折线，你只需要输出满足限制的折线的折点数即可。
注意折点的坐标可以不是整数。
每组测试点有 \(T\)
组数据，对于所有测试点，\(1 \leq T \leq
10^4\)，\(1 \leq \sum n \leq 5 \times
10^5\)，\(1 \leq n \leq
10^5\)，\(1 \leq x_i,y_i \leq
n\)，保证 \(n\)
为正偶数，每组数据中不存在两个坐标相同的整点。
解题思路
首先我们可以证明出一条定理：答案必定大于等于 \(2\) 且小于等于 \(4\)。首先由于点都在 \((1 \sim 100, 1 \sim 100)\) 之间，于是为了在
\((1 \sim 100, 1 \sim 100)\)
之间平分点，我们至少要在这里转折一次。而在这区间之外无论如何均只需转向一次就可平分面积。于是答案必定大于等于
\(2\)。又显然我们可以通过至多 \(3\) 次转折分隔点，加上分隔面积总共 \(4\) 次，于是答案小于等于 \(4\)。
于是我们可以分类讨论情况答案是否为 \(2\)、\(3\)、\(4\)
即可。目前我们从横行考虑。纵行翻转一下坐标同理。
答案为 \(2\)
时很好判断，显然我们只需要判断横行上下点的数目是否相等即可。可用树状数组解决。
答案为 \(3\)
时，我们可推出情况为选定一个横行 \(x\)
与纵行 \(y\)，满足 \(a \le x\) 且 \(y
\le b\) 的点 \((a, b)\) 的个数为
\(\frac{n}{2}\)。于是我们可将每个点按照先
\(x\) 后 \(y\)
的优先级从小到大排序，然后对于每一行二分求出是否可找出满足条件的 \(y\) 即可。
其余情况答案即为 \(4\)，单次询问时间复杂度为 \(O(n \log^2 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
81
82
83
84
| #include <cstdio>
#include <vector>
#include <algorithm>
struct BinaryIndexedTree {
int n;
std::vector<int> a;
void init(int n) {
this->n = n;
a.resize(n + 1);
std::fill(a.begin(), a.end(), 0);
}
static int lowbit(int x) {
return x & -x;
}
void update(int pos, int delta) {
for (; pos <= n; pos += lowbit(pos)) a[pos] += delta;
}
int query(int pos) {
int res = 0;
for (; pos; pos -= lowbit(pos)) res += a[pos];
return res;
}
} bit;
void solve() {
int n;
scanf("%d", &n);
std::vector<std::pair<int, int>> a[2];
for (int i = 0; i < 2; i++) a[i].resize(n);
for (int i = 0; i < n; i++) {
scanf("%d %d", &a[0][i].first, &a[0][i].second);
a[1][i] = std::make_pair(a[0][i].second, a[0][i].first);
}
std::sort(a[0].begin(), a[0].end());
std::sort(a[1].begin(), a[1].end());
for (int i = 0; i < 2; i++) {
bit.init(n);
for (int j = 0; j < n; j++) bit.update(a[i][j].first, 1);
for (int j = 1; j <= n; j++) {
if (bit.query(j) == n / 2) {
puts("2");
return;
} else if (bit.query(j) > n / 2) break;
}
}
for (int i = 0; i < 2; i++) {
bit.init(n);
for (int j = 0; j < n; j++) {
bit.update(a[i][j].second, 1);
if (j == n - 1 || a[i][j + 1].first != a[i][j].first) {
int l = 0, r = n;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (bit.query(mid) <= j + 1 - n / 2) l = mid;
else r = mid - 1;
}
if (bit.query(l) == j + 1 - n / 2) {
puts("3");
return;
}
}
}
}
puts("4");
}
int main() {
int t;
scanf("%d", &t);
while (t--) solve();
return 0;
}
|