背景

Czy 找到宝藏获得屠龙宝刀和神秘秘籍! 现在他要去找经常 ntr 他的 Jmars 报仇......

题目描述

Czy 学会了一招 “堕天一击”, 他对一个地点发动堕天一击, 地面上就会留下一个很大的圆坑. 圆坑的周围一圈能量太过庞大, 因此无法通过. 所以每次 czy 发动技能都会把地面分割. Jmars 拥有好大好大的土地, 几十眼都望不到头, 所以可以假设土地的大小是无限大. 现在 czy 对他发动了猛烈的攻击, 他想知道在泽宇攻击之后他的土地被切成几份了?

Czy 毕竟很虚, 因此圆心都在 x 坐标轴上. 另外, 保证所有圆两两之间不会相交.

格式

输入第一行为整数 n, 表示 czy 放了 n 次堕天一击.

接下来 n 行, 每行两个整数 x [i], r [i]. 表示在坐标 (x [i], 0) 放了一次堕天一击, 半径为 r [i].

输出一行, 表示地面被分割成几块.

样例输入

4
7 5
-9 11
11 9
0 20

样例输出

6

数据范围

对于 30% 数据,\(n \leq 5000\)

对于 100% 数据,\(1 \leq n \leq 300000\),\(-10^9 \leq x_i \leq 10^9\),\(1 \leq r_i \leq 10^9\).

Explanation

官方正解如下:

考虑圆对答案的贡献: 当它并没有被沿着直径分开的时候, 对答案的贡献是 1. 如果被分开贡献是 2. 所以按 r 从小到大排序, 把树的左右端点离散, 用一个线段树维护区间是否被覆盖. 如果已经被覆盖, 贡献是 2, 否则贡献是 1

其实 @BurstZero 大神想出了一个更高的算法:

首先这个题可以简化成这个更弱化的问题: 就是一段区间内完全被许多区间覆盖, 则这个圆被分成两份, 反之则一份. 于是, 我们将每一段区间拆成两个点, 即两个顶点. 这两个顶点确定了这一条线段.

考虑这样的情况: 两个顶点若完全连接了一个更大的区间, 则这个情况一定是封闭一个 圆的充要条件. 我们可以用并查集来维护, 每一次检测到要合并的两个点原来在同一个并查集内则答案加一 (初始值为 \(n + 1\)) .

复杂度强迫症可以认为并查集是均摊 \(O(1)\) 的, 并且可以用基数排序来离散化. 当然 常数可能有点大.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 600100;

class UnionFindSet
{
public:
    int parent[maxn];
    int n;
    int find(int p)
    {
        if (parent[p] == p)
            return p;
        return find(parent[p]);
    }
    void join(int p, int q)
    {
        p = find(p);
        q = find(q);
        if (p != q)
            parent[p] = q;
        return ;
    }
    void init(int n_)
    {
        n = n_;
        for (int i = 1; i <= n; i++)
            parent[i] = i;
        return ;
    }
} graph;

struct srtr { lli val; int pos; } srt[maxn];
bool cmp(srtr a, srtr b) {
    return a.val < b.val; }
class UnscatterizationModule
{
public:
    lli arr[maxn];
    int n;
    int eval(void)
    { // Returns size of all points
        for (int i = 1; i <= n; i++)
            srt[i].val = arr[i], srt[i].pos = i;
        sort(srt + 1, srt + 1 + n, cmp);
        for (int i = 1; i <= n; i++)
            arr[srt[i].pos] = arr[srt[i - 1].pos] + (srt[i].val > srt[i - 1].val);
        return arr[srt[n].pos];
    }
} um;

int n, m;
int dat[maxn][2]; // Left boundaries and right boundaries

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        lli a, b; scanf("%lld%lld", &a, &b);
        // dat[i][0] = a - b, dat[i][1] = a + b;
        um.arr[i * 2 - 1] = a - b;
        um.arr[i * 2] = a + b;
    }
    um.n = n * 2;
    m = um.eval();
    // Saving evaluated de-scatterization data
    for (int i = 1; i <= n; i++)
        dat[i][0] = um.arr[i * 2 - 1],
        dat[i][1] = um.arr[i * 2];
    graph.init(m);
    // Judging correctness
    int result = n + 1; // With the infinite void
    for (int i = 1; i <= n; i++) {
        int p = dat[i][0],
            q = dat[i][1];
        p = graph.find(p);
        q = graph.find(q);
        if (p == q)
            result++;
        graph.join(p, q);
    }
    printf("%d\n", result);
    return 0;
}