P5816 [CQOI2010]内部白点 题解

· · 题解

扫描线是一种方法，在处理点集状态的题目中经常用到。其本质就是按照特定方向一个个处理平面上的点，并更新一些状态（保证不漏不多）。本题解用浅显易懂的语言，远离大量公式推导，帮助新手了解这种方法的本质，还有我们是如何一步步想到解答思路的。

前置芝士：

  1. 树状数组 与 权值树状数组
  2. 离散化
  3. 快速排序

    本题易懂思路 + 简洁实现

    在本题解中，我们称以黑点为端点的，平行于 x 坐标轴的线段为横线段，平行于 y 坐标轴的线段为竖线段。假设最开始这些能连成横竖线段的点已经连好了。

首先观察题目，容易发现两条让这道题变成紫题的性质：

  1. 什么输出 -1 是骗人的，根本不会无限加点
  2. 只会生成一次黑点，之后就不可能出现新的了

证明

首先我们要知道内部白点是啥？是一条横线段和一条竖线段的交点。那么生成的黑点 p 会不会制造新的内部白点呢？不可能！因为想构成新的内部白点需要至少一条新的横/竖线段。但是与 p 连着的所有横/竖线段都会被原来有的横竖线段覆盖。（重点理解一下）

既然如此，我们的答案就是现有横竖线段的交点啦！

统计交点

首先要知道怎么统计横竖线段，这一点很简单。分别以 x 或 y 为第一关键字进行排序，之后就能方便地知道所有 y 或 x 相等的点，它们构成了所有合法线段。

但是实际上我们不需要也不可以统计那么多线段，所有内部白点不能是原来就有的黑点。所以线段顶点相交不能统计进去。那么对于 x （例，y同理）坐标相等的点，只有y坐标最接近的点计入线段。

举个例子：

P_1=(2,4),P_2=(2,9),P_3=(2,6)

只需要建2条线段： P_1P_3 和 P_2P_3 。

那么改成双关键字排序就不成问题了。

接下来就变成了扫描线最擅长的统计交点。

我们可以按照点的 y 坐标从上到下遍历点，过程中如果找到了一条 y 相等的横线段，那么所有满足条件的竖线段都会和当前线段相交：

为了找到这些满足条件的竖线段，我们可以先预处理出：对于点 i，它是否是某竖线段上起点，又是否是某线段下终点。由于我们从上往下遍历，所以可以在统计点 i 和 i-1 作为横线段的答案之前不再考虑点 i 作为下终点的竖线段；统计答案之后开始考虑点 i 作为上起点的竖线段。（当然不作为起终点就不管了）

到这里，解决了关于 y 的 A 条件的满足，接下来想关于 x 的 B 条件。

看到 |x_i|\le 10^9 的恐怖值域，先离散化一下。

离散化下来所有点的 x 坐标，然后用一个权值树状数组记录所有被我们考虑的竖线段的 x 坐标，然后查找两个横线段的端点中间的 x 坐标范围即可。

加入新线段就对应下标 +1 ，退出则 -1 。

Code

代码十分简单，这题主要难度其实在于题目误导性。

扫描线并不难，了解了方法就可以轻松做题。

时间复杂度 O(nlogn)

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) x & -x
int n, b[100010], ans = 0, tx, ty;
char op;
struct node {
    int x, y, f, e; // f存储此点是否是竖线段起点,e为是否是终点
    bool operator<(const node& b) const {
        if (op == 'x') return x != b.x ? x < b.x : y < b.y;
        else return y != b.y ? y < b.y : x < b.x;
    }
} a[100010];
int t[100010];
void add(int x, int k) { // 权值树状数组点加
    for (; x <= n; x += lowbit(x)) t[x] += k;
}
int ask(int x) { // 权值树状数组前缀和统计
    int sum = 0;
    for (; x; x -= lowbit(x)) sum += t[x];
    return sum;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> tx >> ty;
        a[i] = {tx, ty, 0, 0}, b[i] = tx;
    }
    sort(b + 1, b + n + 1); // x离散化
    for (int i = 1; i <= n; i++) 
        a[i].x = lower_bound(b + 1, b + n + 1, a[i].x) - b;
    op = 'x', sort(a + 1, a + n + 1); // 按x排序来统计竖线
    for (int i = 2; i <= n; i++)
        if (a[i].x == a[i - 1].x) // 相同x构成竖线
            a[i - 1].f = a[i].e = 1; // 分别是竖线段首尾
    op = 'y', sort(a + 1, a + n + 1); // 按y排序来找横线
    for (int i = 1; i <= n; i++) {
        if (a[i].e) add(a[i].x, -1); // 线段结束
        if (i > 1 && a[i].y == a[i - 1].y) // 两点构成横线
            ans += ask(a[i].x - 1) - ask(a[i - 1].x); // 查询中间竖线段数量=交点
        if (a[i].f) add(a[i].x, 1); // 新线段加入
    }
    cout << ans + n; // 别忘了原来的黑点！
    return 0;
}