[vijos1883]月光的魔法<递归>

题目链接：https://vijos.org/p/1883

这道题还有另外一种版本叫天神下凡，属于模拟题，可是模拟题数据太水以至于模拟题A了都不一定在vijos上A。。。。

在模拟题里我用的是一种类似扫描线的方式，完美AC，然后在vijos上就是只能过2组

最后经同学提点改为递归才A了

这道题我们把圆看成线段，所以这题就是线段覆盖，然后答案是被完全覆盖的线段数+所有线段数+1

被完全覆盖的线段的数量就用递归找，不断的找被当前线段完全包含的线段，然后判断是否在里面

然后这道题有一种特殊情况可以不用执行程序，就是所有圆都是同心圆的时候，因为这种状态只存在重合和包含（本题重合不算完全覆盖），直接输出圆的数量+1即可

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 #define maxn 300005

 #define ll long long

 using namespace std;

 ll n,cnt,can,ans;

 struct node{

     ll l,r;

 }e[maxn];

 ll read(){

     ll xx=;ll ff=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')ff=-;ch=getchar();}

     while(ch>=''&&ch<=''){xx=xx*+ch-'';ch=getchar();}

     return xx*ff;

 }

 int cmp(node a,node b){

     if(a.l==b.l ){

         return a.r>b.r;

     }return a.l<b.l;

 }

 int t;

 int check (ll id){

     int now=e[id].l,add=,ret=;

     while(t!=n+&&e[t].r<=e[id].r){

         if(e[t].l!=now)add=;

         now=e[t].r;

         ret+=check(t++);

     }

     if(now!=e[id].r )add=;

     return +ret+add;

 }

 int main(){

     n=read();

     for(ll i=;i<=n;i++){

         ll x,R;

         x=read();R=read();

         e[i].l=x-R;e[i].r=x+R;

         if(cnt==)cnt=x;

         if(cnt!=x)can=;

     }

     if(!can){cout<<n+;return ;    }//同一个圆心可以不管了

     sort(e+,e+n+,cmp);t=;

     while(t!=n+){

         ans+=check(t++);

     } ans=ans+;

     cout<<ans;

 }

然后这道题还有一个解法就是线段树，因为不存在相交的情况，所以不需要使用lazy标记，没有lazy标记的线段树就很简单了

但是要注意一点就是这些左右端点在坐标轴上，坐标轴有可能很大，所以要用到离散化