OI Problems   关于

总体思路

显然的，每一个圆都会对答案产生贡献，所以答案至少为 11。此时答案为 n+1n+1。而可能会遇到这种情况：

这时上下分离，对答案又贡献了 11，所以我们只需要考虑如何计算这样的贡献。


法一：线段树

注意到一个圆被分割成上下两半，当且仅当该圆截 xx 轴得线段已经被其他圆占领。

考虑维护一棵线段树，记录一段区间是否被占领即可。

时间复杂度 Θ(nlogn)\Theta(n\log n)。

  代码
// 2023.5.23

#include<bits/stdc++.h>
using namespace std;

int n;
struct circle{
    int x,r;
    bool operator<(circle tmp)const{
        return r<tmp.r;
    }
}c[300001];

int disc[600001],cntdisc;
int finddisc(int x){
    return lower_bound(disc+1,disc+1+cntdisc,x)-disc-1;
}

namespace SegmentTree{
    struct Node{
        int l,r; bool tag;
    }a[900001];
    void pushup(int id){
        a[id].tag=a[id<<1].tag & a[(id<<1)+1].tag;
    }
    void pushdown(int id){
        a[id<<1].tag|=a[id].tag;
        a[(id<<1)+1].tag|=a[id].tag;
    }

    void build(int id, int l, int r){
        a[id].l=l,a[id].r=r;
        if(l==r)return;
        int mid=l+r>>1;
        build(id<<1,l,mid);
        build((id<<1)+1,mid+1,r);
    }
    bool query(int id,int l,int r){
        pushdown(id); 
        if(l<=a[id].l&&a[id].r<=r)
            return a[id].tag;
        int mid=a[id].l+a[id].r>>1,res=1;
        if(l<=mid)res&=query(id<<1,l,r);
        if(r>mid) res&=query((id<<1)+1,l,r);
        return res;
    }
    void add(int id,int l,int r){
        pushdown(id);
        if(l<=a[id].l&&a[id].r<=r){
            a[id].tag=true; return;
        } 
        int mid=a[id].l+a[id].r>>1;
        if(l<=mid)add(id<<1,l,r);
        if(r>mid) add((id<<1)+1,l,r);
        pushup(id); 
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&c[i].x,&c[i].r);
        disc[++cntdisc]=c[i].x-c[i].r;
        disc[++cntdisc]=c[i].x+c[i].r;
    }
    sort(disc+1,disc+1+cntdisc);
    cntdisc=unique(disc+1,disc+cntdisc+1)-disc-1;
    sort(c+1,c+1+n);

    SegmentTree::build(1,1,cntdisc);
    int answer=n+1;
    for(int i=1;i<=n;i++){
        int l=finddisc(c[i].x-c[i].r),
            r=finddisc(c[i].x+c[i].r);
        answer+=SegmentTree::query(1,l+1,r),
        SegmentTree::add(1,l+1,r);
    }
    printf("%d\n",answer);
    return 0;
}

法二：单调栈

本文作者是 hank0402，遵循 CC BY-NC-SA 4.0 协议。

首先，我们观察到每加入一个圆，至少多分了 11 个部分，但也有时候分成了两个部分，即大圆被若干个小圆分成上下两部分。

那么我们考虑如何统计这种特殊情况。

首先，我们按每个圆的右端点从小到大排序，然后，我们按顺序加入单调栈中。

那么如果一个大圆里面的小圆没有再包含一个圆，我们就可以直接记录这个大圆包含的小圆的直径和，与大圆的直径比较就可以判断是否为特殊情况。

那么我们考虑维护一个没有包含关系的栈。

因为我们把右端点从小到大排了序，所以在加入一个圆的时候，我们只要看左端点，如果刚加的这个圆的左端点小于等于栈顶的左端点，那么栈顶的圆就被包含了，我们把它弹出，顺便记录弹出圆的直径和。

于是我们这个左端点递增的单调栈，既可以保证没有二次包含关系，也可以实时统计大圆包含的小圆的直径和，直接判断即可。

时间复杂度为 Θ(nlogn)\Theta(n\log n)，瓶颈在排序上。

  代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PII pair<int, int>
#define mkp make_pair
#define INF INT_MAX
template <typename T> inline void rd(T &x){
    x = 0; bool f = true; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') f = false; ch = getchar();}
    while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar();}
    if(!f) x = -x;
}
template <typename T, typename ...Args> inline void rd(T &x, Args &...args){ rd(x); rd(args...);}
const int N = 3e5 + 10;
struct circle {
    int x, r;
}c[N];
bool cmp(circle A, circle B) {
    if(A.x + A.r != B.x + B.r) return A.x + A.r < B.x + B.r;
    else return A.x - A.r > B.x - B.r;
}
int n, st[N], top, ans;
int main() {
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    rd(n);
    for(int i = 1; i <= n; ++i) rd(c[i].x, c[i].r);
    sort(c + 1, c + n + 1, cmp);
    for(int i = 1; i <= n; ++i) {
        int now = c[i].x - c[i].r, sum = 0;
        while(c[st[top]].x - c[st[top]].r >= now && top >= 1) {
            sum += 2 * c[st[top]].r;
            top --;
        }
        st[++top] = i;
        if(sum == 2 * c[i].r) ans ++;
    }
    cout << ans + n + 1 << endl;
    return 0;
}

法三：并查集

TODO

时间复杂度 Θ(n)\Theta(n)。