Description

在一条直线上有 N 个炸弹，每个炸弹的坐标是 Xi，爆炸半径是 Ri，当一个炸弹爆炸时，如果另一个炸弹所在位置 Xj 满足：

Xi−Ri≤Xj≤Xi+Ri,那么，该炸弹也会被引爆。

现在，请你帮忙计算一下，先把第 i 个炸弹引爆，将引爆多少个炸弹呢？

Input

第一行，一个数字 N，表示炸弹个数。

第 2∼N+1行，每行 2 个数字，表示 Xi，Ri，保证 Xi 严格递增。

N≤500000

−10^18≤Xi≤10^18

0≤Ri≤2×10^18

Output

一个数字，表示Sigma(i*炸弹i能引爆的炸弹个数),1<=i<=N mod10^9+7。

题解

因为每一个炸弹爆炸后引爆的是一个区间的炸弹，所以想到线段树优化建图。

然后可能有环所以跑Tarjan求强连通分量。最后拓扑合并答案。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int N=;

 const int mod=1e9+;

 queue<int> q;

 int cnt,cnt1,head[N*],head1[N*];

 int num,id[N*],di[N*];

 int dfn[N*],low[N*],tot1,top,stack[N*],book[N*],num1,col[N*],tmp;

 long long a[N],r[N],b[N],maxx[N*],minn[N*];

 int n,tot,in[N*];

 long long ans;

 struct tree{

     int l,r;

 }tr[N*];

 struct edge{

     int to,nxt,u;

 }e[N*],e1[N*];

 void add(int u,int v){

     cnt++;

     e[cnt].nxt=head[u];

     e[cnt].u=u;

     e[cnt].to=v;

     head[u]=cnt;

 }

 void add1(int u,int v){

     cnt1++;

     e1[cnt1].nxt=head1[u];

     e1[cnt1].to=v;

     head1[u]=cnt1;

 }

 void build(int l,int r,int now){

     num=max(num,now);

     tr[now].l=l;tr[now].r=r;

     if(r==l){

         id[l]=now;

         di[now]=l;

         return;

     }

     int mid=(tr[now].l+tr[now].r)>>;

     build(l,mid,now*);

     build(mid+,r,now*+);

     add(now,now*);

     add(now,now*+);

 }

 void update(int l,int r,int now,int u){

     if(tr[now].l==l&&tr[now].r==r){

         add(u,now);

         return;

     }

     int mid=(tr[now].l+tr[now].r)>>;

     if(l>mid)update(l,r,now*+,u);

     else if(r<=mid)update(l,r,now*,u);

     else{

         update(l,mid,now*,u);

         update(mid+,r,now*+,u);

     }

 }

 void Tarjan(int u){

     dfn[u]=low[u]=++tot1;

     stack[++top]=u;

     book[u]=;

     for(int i=head[u];i;i=e[i].nxt){

         int v=e[i].to;

         if(dfn[v]==){

             Tarjan(v);

             low[u]=min(low[u],low[v]);

         }

         else if(book[v])low[u]=min(low[u],dfn[v]);

     }

     if(dfn[u]==low[u]){

         int x;

         num1++;

         minn[num1]=4e18;

         maxx[num1]=-4e18;

         bool flag=false;

         do{

             x=stack[top--];

             book[x]=;

             col[x]=num1;

             if(di[x]){

                 if(!flag){

                     minn[num1]=a[di[x]]-r[di[x]];

                     maxx[num1]=a[di[x]]+r[di[x]];

                     flag=true;

                 }

                 else{

                     minn[num1]=min(minn[num1],a[di[x]]-r[di[x]]);

                     maxx[num1]=max(maxx[num1],a[di[x]]+r[di[x]]);

                 }

             }

         }while(x!=u);

     }

 }

 int lower(long long x){

     int ll=;int rr=tot+;

     while(ll<=rr){

         int mid=(ll+rr)>>;

         if(b[mid]>=x){

             tmp=mid;

             rr=mid-;

         }

         else ll=mid+;

     }

     return tmp;

 }

 int uppr(long long x){

     int ll=;int rr=tot+;

     while(ll<=rr){

         int mid=(ll+rr)>>;

         if(b[mid]>x){

             tmp=mid;

             rr=mid-;

         }

         else ll=mid+;

     }

     return tmp;

 }

 int main(){

     scanf("%d",&n);

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

         scanf("%lld%lld",&a[i],&r[i]);

         b[i]=a[i];

     }

     tot=unique(b+,b++n)-(b+);

     b[tot+]=4e18;

     build(,n,);

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

         int x=lower(a[i]-r[i]);

         int y=uppr(a[i]+r[i])-;

         update(x,y,,id[i]);

     }

     for(int i=;i<=num;i++){

         if(!dfn[i])Tarjan(i);

     }

     for(int i=;i<=cnt;i++){

         if(col[e[i].u]==col[e[i].to])continue;

         add1(col[e[i].to],col[e[i].u]);

         in[col[e[i].u]]++;

     }

     for(int i=;i<=num1;i++){

         if(in[i]==)q.push(i);

     }

     while(!q.empty()){

         int u=q.front();

         q.pop();

         for(int i=head1[u];i;i=e1[i].nxt){

             int v=e1[i].to;

             in[v]--;

             if(in[v]==)q.push(v);

             minn[v]=min(minn[v],minn[u]);

             maxx[v]=max(maxx[v],maxx[u]);

         }

     }

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

         int x=uppr(maxx[col[id[i]]])-;

         int y=lower(minn[col[id[i]]]);

         ans+=(long long)((long long)(x-y+)*(long long)i)%mod;

         ans%=mod;

     }

     printf("%lld",ans);

     return ;

 }

巴特西

BZOJ5017 炸弹（线段树优化建图+Tarjan+拓扑）

Description

Input

Output

题解

最新文章

热门文章