天神下凡

并查集 栈

题面

给出$n$个圆心同在$x$轴上的圆，问圆的轮廓将平面分为几块？（保证圆互不相交）

• $n\leq3*10^5$
• $r\leq10^9,x\leq10^9$

解析

经过观察，可以发现，如果一个圆的直径被其它小圆的直径完全覆盖，就会产生额外一贡献。
因为圆在一条直线上，我们只用关心其在直线上的一部分，即可以用直径代替一个圆。
一条直线再次被覆盖？能想到什么？
线段树？栈？

$method\ 1$ 并查集

据说这是我的原创方法？
在手玩样例时，我发现，每次产生贡献的前一步都是把已联通（通过圆相切的方式）的两个点作为一个圆直径的两端点。
如何判断两点是否联通？
每覆盖一条直线，两端点就连通了，此时两端点中间的点就没用了，直接把两端点纳入同一并查集即可。
当然，两端点联通有一种方式叫在同一圆直径的两端，即存在同圆，这会影响答案，要排序除掉。
由于半径范围（即直径两端点范围）过大，要用$map$。
于是复杂度达到了$O(nlog^2n)$，但时间比为$1.16s/3s$，不虚。（并查集+$map$）
可以通过离散化达到$O(nlogn)$，时间比为$0.54s/3s$。
更有趣的是，如果不$STL$离散化而是用$unordered\_map$,时间比可达$0.37s/3s$
（复习一下离散化部分）

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=3e5+100;
int n,tot;
struct node
{
  ll l,r;
  bool operator < (const node &o) const {return (l<o.l)||(l==o.l&&r<o.r);}
}a[N],b[N];
ll f[N],ans=1,o[N<<1],top;
bool vis[N<<1];
il ll gi() 
{
  re ll x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}
int main()
{
  freopen("god.in","r",stdin);
  freopen("god.out","w",stdout);
  n=gi();
  fp(i,1,n) f[i]=i;
  fp(i,1,n)
    {
      re ll x=gi(),r=gi();
      a[i].l=x-r,a[i].r=x+r;o[++top]=a[i].l;o[++top]=a[i].r;
    }
  sort(a+1,a+1+n);
  -----离散化-----
  sort(o+1,o+1+top);
  re int len=unique(o+1,o+1+top)-o-1;
  fp(i,1,n)
    {
      a[i].l=lower_bound(o+1,o+1+len,a[i].l)-o;
      a[i].r=lower_bound(o+1,o+1+len,a[i].r)-o;
      }
  -----离散化-----
  b[++tot]=a[1];
  fp(i,2,n)
    if(a[i-1]<a[i]) b[++tot]=a[i];
  fp(i,1,tot)
    {
      re int tag=0;
      re int u1=i,v1=vis[a[i].l],fu1=find(u1),fv1=find(v1);
      re int u2=i,v2=vis[a[i].r],fu2=find(u2),fv2=find(v2);
      if(v1&&v2&&fv1==fv2) ++ans;
      if(v1) f[fu1]=fv1;
      if(v2) f[fu2]=fv2;
      vis[a[i].l]=vis[a[i].r]=i;
    ++ans;
    }
  printf("%lld\n",ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}

如何定义$unorderes\_map$:

#include<tr1/unordered_map>
std::tr1::unordered_map<ll,int>vis;

$method\ 2$ 栈

把圆以左端点为第一关键字(从小到大），右端点为第二关键字(从大到小)排序。
想象一个圆，其中直径被若干个小圆覆盖。（这好像是产生贡献的唯一方式）
如果新加入一个小圆，与原有一个大圆内切于左端点，那么大圆就可能有贡献，入栈。
然后产生贡献的要求是覆盖不断且右端点相切。
即如果新圆左端点大于栈顶圆右端点，就说明栈顶圆无贡献，弹出。
如果新圆右端点同栈顶圆右端点，产生贡献，弹出栈顶。
本来时间复杂度$O(nlogn)$（$sort$)
然而因为数据是按圆心从小到大给出，所以复杂度可达$O(n)$。
时间比$0.18s/3s$。比不得。。。

n=read();
    for(rg int i=1,x,r;i<=n;i++)
    {
        x=read();
        r=read();
        c[i]=(circle){x-r,x+r};
    }
    sort(c+1,c+n+1,cmp);
    Ans=2;
    for(rg int i=2;i<=n;i++)
    {
        if(c[i].l==c[i-1].l&&c[i].r==c[i-1].r)continue;
        Ans++;
        if(c[i].l==c[i-1].l&&c[i].r<c[i-1].r)
            st[++top]=c[i-1];
        if(c[i].l>c[i-1].r)
            if(top)top--;
        if(c[i].r==st[top].r)Ans++,top--;
    }
    printf("%d\n",Ans);

$method\ 3$ 线段树

从小往大加“直径边”，用线段树维护该段是否被完全覆盖过，如是则产生贡献。
复杂度为$O(nlogn)$,时间比$0.65s/3s$。