在一条直线上有 N 个炸弹,每个炸弹的坐标是 Xi,爆炸半径是 Ri,当一个炸弹爆炸时,如果另一个炸弹所在位置 Xj 满足: Xi?Ri≤Xj≤Xi+Ri,那么,该炸弹也会被引爆。
现在,请你帮忙计算一下,先把第 i 个炸弹引爆,将引爆多少个炸弹呢?
N≤500000
?10^18≤Xi≤10^18
0≤Ri≤2×10^18
大概就是说,每个炸弹可以向一段连续的区间连边,要求每个炸弹能到达的编号最小和最大的点。
因为是区间,显然可以用线段树优化建图。然后就是tarjan+拓扑排序的套路了。
#include#include #include #include #include #define MAX(x,y) x=max(x,y) #define MIN(x,y) x=min(x,y) using namespace std; typedef long long LL; const int N=500005; const int MOD=1000000007; const int inf=1000000000; int n,sz,cnt,last[N*5],num[N*4],dfn[N*5],low[N*5],tim,deg[N*5],tot,mn[N*5],mx[N*5],a[N*5],stack[N*5],top,bel[N*5]; LL p[N],r[N]; bool ins[N*5]; struct edge{int to,next,from;}e[N*50]; void addedge(int u,int v) { e[++cnt].from=u;e[cnt].to=v;e[cnt].next=last[u];last[u]=cnt; } void build(int d,int l,int r) { num[d]=++sz; if (l==r) {addedge(num[d],l);return;} int mid=(l+r)/2; build(d*2,l,mid);build(d*2+1,mid+1,r); addedge(num[d],num[d*2]);addedge(num[d],num[d*2+1]); } void work(int d,int l,int r,int x,int y,int id) { if (l==x&&r==y) {addedge(id,num[d]);return;} int mid=(l+r)/2; if (y<=mid) work(d*2,l,mid,x,y,id); else if (x>mid) work(d*2+1,mid+1,r,x,y,id); else work(d*2,l,mid,x,mid,id),work(d*2+1,mid+1,r,mid+1,y,id); } void tarjan(int x) { dfn[x]=low[x]=++tim; stack[++top]=x;ins[x]=1; for (int i=last[x];i;i=e[i].next) if (!dfn[e[i].to]) tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]); else if (ins[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); if (dfn[x]==low[x]) { tot++;mn[tot]=inf;mx[tot]=0;int y=0; while (y!=x) { y=stack[top];top--; ins[y]=0;bel[y]=tot; if (y<=n) MIN(mn[tot],y),MAX(mx[tot],y); } } } void solve() { int a1=0; for (int i=1;i<=tot;i++) if (!deg[i]) a[++a1]=i; for (int i=1;i<=a1;i++) for (int j=last[a[i]];j;j=e[j].next) { deg[e[j].to]--; if (!deg[e[j].to]) a[++a1]=e[j].to; } for (int i=tot;i>=1;i--) { int x=a[i]; for (int j=last[x];j;j=e[j].next) MIN(mn[x],mn[e[j].to]),MAX(mx[x],mx[e[j].to]); } } int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%lld%lld",&p[i],&r[i]); sz=n;build(1,1,n); for (int i=1;i<=n;i++) { int x=lower_bound(p+1,p+n+1,p[i]-r[i])-p; int y=upper_bound(p+1,p+n+1,p[i]+r[i])-p-1; work(1,1,n,x,y,i); } for (int i=1;i<=sz;i++) if (!dfn[i]) tarjan(i); memset(last,0,sizeof(last)); int tmp=cnt; for (int i=1;i<=tmp;i++) if (bel[e[i].from]!=bel[e[i].to]) { addedge(bel[e[i].from],bel[e[i].to]); deg[bel[e[i].to]]++; } solve(); int ans=0; for (int i=1;i<=n;i++) ans+=(LL)i*(mx[bel[i]]-mn[bel[i]]+1)%MOD,ans-=ans>=MOD?MOD:0; printf("%d",ans); return 0; }