背景
影几欺哄了众生了，天以外——月儿何曾圆缺。
描述
有些东西就如同月光的魔法一般.
Luke是爱着vijos的.他想为自己心爱的东西画些什么——————就画N个圆吧.把它们的圆心都固定在x轴上.圆与圆.为了爱,两两不能相交.为了爱,它们可以互相贴在一起.内切或外切,都是允许的.
vijos的美丽,在于人心.vijos的孩子们,一定能告诉大家:Luke画的圆究竟把平面分割成了多少块?
月光恬美地洒在大地上.Luke知道,如果什么都不画,平面就只有一块.多美呢!Luke知道,只画一个圆,平面就分成了两块.也很美呢!但Luke还是要多画一些的,因为他真的深爱着vijos呢.
格式
输入格式
输入数据第一行:输出一个整数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
所有圆都是唯一的,不会出现重叠.
输出格式
输出只有一行,要求输出平面被分割成了多少块.
限制
对于40%的数据:
N<=5000.
对于100%的数据:
1<=N<=300,000;-1,000,000,000<=x[i]<=1,000,000,000;1<=r[i]<=1,000,000,000
题解
线段树的引用，我将圆按半径从大到小排列，用每个圆的编号在线段树上覆盖“该圆所覆盖的x轴”。线段树维护每一段中编号的最小值。之后从半径从小到大，若该圆所覆盖的x轴上编号最小=这个圆的编号，ans+1，否则ans+2.具体是为什么……好像画个图想想就好。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define MAXN 300002
#define ll long long
using namespace std;
int n,b[MAXN<<1],cnt,hs[MAXN<<1],zz;
struct yuan{int o,r,L,R;} a[MAXN];
struct tree{int l,r,v,tag;} tr[MAXN*8];
ll ans;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+(ch-'0'); ch=getchar();}
return f*x;
}
bool kp(const yuan &i,const yuan &j) {return i.r>j.r;}
void init()
{
n=read(); //printf("%d\n",n);
int i,x,r;
for(i=1;i<=n;i++)
{a[i].o=read(); a[i].r=read();
//printf("%d %d\n",a[i].o,a[i].r);
a[i].L=a[i].o-a[i].r; a[i].R=a[i].o+a[i].r;
//printf("%d %d\n",a[i].L,a[i].R);
b[++cnt]=a[i].L; b[++cnt]=a[i].R;
}
sort(b+1,b+cnt+1);
hs[1]=b[1]; zz=1;
for(i=2;i<=cnt;i++)
{if(b[i]!=b[i-1]) hs[++zz]=b[i];}
/*for(i=1;i<=zz;i++) printf("%d ",hs[i]);
printf("\n");
system("pause");*/
sort(a+1,a+n+1,kp);
}
//------------------------------------------------------------------------------
void build(int w,int s,int e)
{
tr[w].l=s; tr[w].r=e;
if(s==e)
{tr[w].v=1<<30; tr[w].tag=-1; return ;}
int mid=(s+e)>>1;
build(w<<1,s,mid); build((w<<1)+1,mid+1,e);
}
int getw(int x)
{
int s=1,e=zz,mid,w;
while(s<=e)
{mid=(s+e)>>1;
if(hs[mid]>x) e=mid-1;
else {w=mid; s=mid+1;}
}
return w;
}
void down(int w)
{
if(tr[w].tag==-1) return;
int l=w<<1,r=l+1,t=tr[w].tag;
tr[w].tag=-1;
tr[l].v=t; tr[l].tag=t;
tr[r].v=t; tr[r].tag=t;
}
void insert(int w,int s,int e,int v)
{
down(w);
int l=tr[w].l,r=tr[w].r;
if(s==l&&r==e)
{tr[w].v=v; tr[w].tag=v;
return ;
}
int mid=(l+r)>>1;
if(e<=mid) insert(w<<1,s,e,v);
else if(s>mid) insert((w<<1)+1,s,e,v);
else {insert(w<<1,s,mid,v); insert((w<<1)+1,mid+1,e,v);}
tr[w].v=min(tr[(w<<1)+1].v,tr[w<<1].v);
}
int find(int w,int s,int e)
{
down(w);
int l=tr[w].l,r=tr[w].r;
if(s==l&&r==e) return tr[w].v;
int mid=(l+r)>>1;
if(e<=mid) return find(w<<1,s,e);
else if(s>mid) return find((w<<1)+1,s,e);
else return min(find(w<<1,s,mid),find((w<<1)+1,mid+1,e));
}
void work()
{
int i,s,e;
for(i=1;i<=n;i++)
{s=getw(a[i].L); e=getw(a[i].R-1);
insert(1,s,e,i);
}
for(i=n;i>=1;i--)
{s=getw(a[i].L); e=getw(a[i].R-1);
int t=find(1,s,e);
//printf("%d\n",t);
//system("pause");
if(t<=i) ans++;
else ans+=2;
}
printf("%d\n",ans+1);
}
int main()
{
init(); build(1,1,zz);
work();
return 0;
}