vijos1883 月光的魔法
题目
背景
影几欺哄了众生了
天以外——
月儿何曾圆缺
描述
有些东西就如同月光的魔法一般.
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
4
7 5
-9 11
11 9
0 20
OUTPUT
6
解题报告
本次考试觉得唯一能A的一道题 （唯一能拿分的题吧啊喂），然而还是打挂了- -
正解：
我们考虑一下每个圆对答案的贡献，当它只是单独的一个圆时，它只把整个平面分割成圆内与圆外两部分，故贡献为1，同理，各种内切与外切也没有什么影响，但我们考虑，如果一个圆被沿直径一个点不差的被分开，它自己就又被分成两个部分，贡献就为2。
如何判断呢，显然10^9的坐标是无法正常处理的，所以我们需要离散，用线段树维护区间被覆盖的点，把圆压成线段，每加入一个线段，就判断该区间是否已经被覆盖，假如被覆盖，说明该圆已经被沿直径分开了，那么它的贡献为2，否则为1.
你以为这样就结束了？NONONO（莫名中二= =）。我们考虑这样一种情况，我们已经有了两个圆，一个占领了1~2，一个占领了3~4，我们现在要加入一个1~4的圆，首先，我们自然会查询1~4的总权值，得到4，是不是就会认为1~4全部覆盖然后开心的加了2？显然是错误的，2~3这一段区间并未被覆盖，但我们认为它被覆盖了，那么我们如何处理呢？
我们可以把每个点劈成两半，一个称为该点的左半点，一个称为该点的右半点，那么当两个圆切于该点时，自然可以认为，一个圆覆盖了左半点，一个圆覆盖了右半点，此时再按上面那种方法判断，就啥事也没有啦
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
inline int read(){
int sum(),f();
char ch(getchar());
for(;ch<''||ch>'';ch=getchar())
if(ch=='-')
f=-;
for(;ch>=''&&ch<='';sum=sum*+ch-'',ch=getchar());
return sum*f;
}
map<int,int>ma;
struct node{
int l,r;
friend bool operator<(const node &a,const node &b){
return (a.r-a.l)<(b.r-b.l);
}
}a[];
int n;
int tmp[];
int cnt;
int sum[<<],add[<<];
inline void pushup(int i){
sum[i]=sum[i<<]+sum[i<<|];
}
inline void pushdown(int i,int len){
if(add[i]){
add[i<<]=add[i];
add[i<<|]=add[i];
sum[i<<]=add[i]*(len-(len>>));
sum[i<<|]=add[i]*(len>>);
add[i]=;
}
}
inline void update(int ll,int rr,int c,int l,int r,int i){
if(ll>rr)
return;
if(ll<=l&&r<=rr){
add[i]=c;
sum[i]=c*(r-l+);
return;
}
pushdown(i,r-l+);
int mid((l+r)>>);
if(ll<=mid)
update(ll,rr,c,l,mid,i<<);
if(mid<rr)
update(ll,rr,c,mid+,r,i<<|);
pushup(i);
}
inline int query(int ll,int rr,int l,int r,int i){
if(ll>rr)
return ;
if(ll<=l&&r<=rr)
return sum[i];
pushdown(i,r-l+);
int mid((l+r)>>);
int ret();
if(ll<=mid)
ret+=query(ll,rr,l,mid,i<<);
if(mid<rr)
ret+=query(ll,rr,mid+,r,i<<|);
return ret;
}
int ans();
int main(){
n=read();
for(int i=;i<=n;i++){
int x(read()),r(read());
a[i].l=x-r,a[i].r=x+r;
tmp[++cnt]=a[i].l,tmp[++cnt]=a[i].r;
}
sort(tmp+,tmp+cnt+);
cnt=;
for(int i=;i<=(n<<);i++)
if(!ma.count(tmp[i]))
ma[tmp[i]]=++cnt;
sort(a+,a+n+);
for(int i=;i<=n;i++){
a[i].l=ma[a[i].l]<<;
a[i].r=(ma[a[i].r]<<)-;//cout<<i<<' '<<l<<' '<<r<<endl;
if(query(a[i].l,a[i].r,,n<<,)==a[i].r-a[i].l+)
ans+=;
else
ans++;
update(a[i].l,a[i].r,,,n<<,);
}
printf("%d",ans);
}
话说我当时用线段建了个图，然后dfs，现在想想也是蠢= =