[补档]vijos1883 月光的魔法

vijos1883 月光的魔法

题目

传送门：https://www.vijos.org/p/1883

背景

影几欺哄了众生了

天以外——

月儿何曾圆缺

描述

有些东西就如同月光的魔法一般.

Luke是爱着vijos的.

他想为自己心爱的东西画些什么.

就画N个圆吧.

把它们的圆心都固定在x轴上.

圆与圆.

为了爱,两两不能相交.

为了爱,它们可以互相贴在一起.

内切或外切,都是允许的.

vijos的美丽,在于人心.

vijos的孩子们,一定能告诉大家:Luke画的圆究竟把平面分割成了多少块?

月光恬美地洒在大地上.

Luke知道,如果什么都不画,平面就只有一块.多美呢!

Luke知道,只画一个圆,平面就分成了两块.也很美呢!

但Luke还是要多画一些的,因为他真的深爱着vijos呢.

INPUT

输入数据第一行:输出一个整数N,1<=N<=300,000.表示圆的个数.

之后N行,每一行有2个整数,x[i]和r[i]表示圆心固定在x[i]的位置,半径为r[i].

-1,000,000,000<=x[i]<=1,000,000,000

1<=r[i]<=1,000,000,000

所有圆都是唯一的,不会出现重叠.

OUTPUT

输出只有一行,要求输出平面被分割成了多少块.

SAMPLE

INPUT

7 5

-9 11

11 9

0 20

OUTPUT

解题报告

本次考试觉得唯一能A的一道题（唯一能拿分的题吧啊喂），然而还是打挂了- -

正解：

我们考虑一下每个圆对答案的贡献，当它只是单独的一个圆时，它只把整个平面分割成圆内与圆外两部分，故贡献为1，同理，各种内切与外切也没有什么影响，但我们考虑，如果一个圆被沿直径一个点不差的被分开，它自己就又被分成两个部分，贡献就为2。

如何判断呢，显然10^9的坐标是无法正常处理的，所以我们需要离散，用线段树维护区间被覆盖的点，把圆压成线段，每加入一个线段，就判断该区间是否已经被覆盖，假如被覆盖，说明该圆已经被沿直径分开了，那么它的贡献为2，否则为1.

你以为这样就结束了？NONONO（莫名中二= =）。我们考虑这样一种情况，我们已经有了两个圆，一个占领了1~2，一个占领了3~4，我们现在要加入一个1~4的圆，首先，我们自然会查询1~4的总权值，得到4，是不是就会认为1~4全部覆盖然后开心的加了2？显然是错误的，2~3这一段区间并未被覆盖，但我们认为它被覆盖了，那么我们如何处理呢？

我们可以把每个点劈成两半，一个称为该点的左半点，一个称为该点的右半点，那么当两个圆切于该点时，自然可以认为，一个圆覆盖了左半点，一个圆覆盖了右半点，此时再按上面那种方法判断，就啥事也没有啦

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<map>
 6 using namespace std;
 7 inline int read(){
 8     int sum(0),f(1);
 9     char ch(getchar());
10     for(;ch<'0'||ch>'9';ch=getchar())
11         if(ch=='-')
12             f=-1;
13     for(;ch>='0'&&ch<='9';sum=sum*10+ch-'0',ch=getchar());
14     return sum*f;
15 }
16 map<int,int>ma;
17 struct node{
18     int l,r;
19     friend bool operator<(const node &a,const node &b){
20         return (a.r-a.l)<(b.r-b.l);
21     }
22 }a[300001];
23 int n;
24 int tmp[600001];
25 int cnt;
26 int sum[600001<<3],add[600001<<3];
27 inline void pushup(int i){
28     sum[i]=sum[i<<1]+sum[i<<1|1];
29 }
30 inline void pushdown(int i,int len){
31     if(add[i]){
32         add[i<<1]=add[i];
33         add[i<<1|1]=add[i];
34         sum[i<<1]=add[i]*(len-(len>>1));
35         sum[i<<1|1]=add[i]*(len>>1);
36         add[i]=0;
37     }
38 }
39 inline void update(int ll,int rr,int c,int l,int r,int i){
40     if(ll>rr)
41         return;
42     if(ll<=l&&r<=rr){
43         add[i]=c;
44         sum[i]=c*(r-l+1);
45         return;
46     }
47     pushdown(i,r-l+1);
48     int mid((l+r)>>1);
49     if(ll<=mid)
50         update(ll,rr,c,l,mid,i<<1);
51     if(mid<rr)
52         update(ll,rr,c,mid+1,r,i<<1|1);
53     pushup(i);
54 }
55 inline int query(int ll,int rr,int l,int r,int i){
56     if(ll>rr)
57         return 0;
58     if(ll<=l&&r<=rr)
59         return sum[i];
60     pushdown(i,r-l+1);
61     int mid((l+r)>>1);
62     int ret(0);
63     if(ll<=mid)
64         ret+=query(ll,rr,l,mid,i<<1);
65     if(mid<rr)
66         ret+=query(ll,rr,mid+1,r,i<<1|1);
67     return ret;
68 }
69 int ans(1);
70 int main(){
71     n=read();
72     for(int i=1;i<=n;i++){
73         int x(read()),r(read());
74         a[i].l=x-r,a[i].r=x+r;
75         tmp[++cnt]=a[i].l,tmp[++cnt]=a[i].r;
76     }
77     sort(tmp+1,tmp+cnt+1);
78     cnt=0;
79     for(int i=1;i<=(n<<1);i++)
80         if(!ma.count(tmp[i]))
81             ma[tmp[i]]=++cnt;
82     sort(a+1,a+n+1);
83     for(int i=1;i<=n;i++){
84         a[i].l=ma[a[i].l]<<1;
85         a[i].r=(ma[a[i].r]<<1)-1;//cout<<i<<' '<<l<<' '<<r<<endl;
86         if(query(a[i].l,a[i].r,1,n<<2,1)==a[i].r-a[i].l+1)
87             ans+=2;
88         else
89             ans++;
90         update(a[i].l,a[i].r,1,1,n<<2,1);
91     }
92     printf("%d",ans);
93 }

View Code

话说我当时用线段建了个图，然后dfs，现在想想也是蠢= =