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。 

 

Sample Input

4
1 1
5 1
6 5
15 15

Sample Output

32
   

题解

• 这题我们可以选择用并查集来做

• 对于一个炸弹i，如果它的爆炸范围能到达另一个炸弹，那么炸弹i所能爆炸的范围就是两个炸弹左区间取min，右区间取max的

• 那我们就先处理出当前点并到所能到达的最远点
• 然后就进行tarjan缩点，就会缩成一个DAG，答案就是DAG中的可到达的点数
• 考虑怎么做？然后我们会发现对于取的点一定是在一段连续的区间内
• 然后就用并查集维护size就好了

代码

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #define ll long long
 7 using namespace std;
 8 const int N=5e5+10,mo=1e9+7;
 9 ll ans;
10 int n,cnt,num,tot,top,fa[N],head[N],last[N],bel[N],size[N],val[N],dfn[N],low[N],vis[N],stack[N];
11 struct node {ll x,r;} b[N];
12 struct edge {int from,to;}e[N*4],E[N*4];
13 void insert(int x,int y) { e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt; }
14 void ins(int x,int y) { E[++tot].to=y,E[tot].from=last[x],last[x]=tot; }
15 int getfather(int x) { return fa[x]==x?x:fa[x]=getfather(fa[x]); }
16 void tarjan(int x)
17 {
18     dfn[x]=low[x]=++dfn[0],stack[++top]=x,vis[x]=1;
19     for (int i=head[x];i;i=e[i].from)
20         if (!dfn[e[i].to]) tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]); else if (vis[e[i].to]) low[x]=min(low[x],dfn[e[i].to]);
21     if (dfn[x]==low[x])
22     {
23         int p=0; num++;
24         while (p!=x) p=stack[top--],vis[p]=0,bel[p]=num,++size[num],val[num]=(val[num]+p)%mo;
25     }
26 }
27 void count(int x)
28 {
29     if (vis[x]) return;
30     for (int i=last[x];i;i=E[i].from)
31     {
32         int u=getfather(x),v=getfather(E[i].to);
33         if (u^v) fa[v]=u,size[u]+=size[v];
34     }
35     vis[x]=1;
36 }
37 int main()
38 {
39     scanf("%d",&n);
40     for (int i=1;i<=n;i++) scanf("%lld%lld",&b[i].x,&b[i].r);
41     for (int i=1;i<=n;i++) fa[i]=i;
42     for (int i=2;i<=n;i++)
43     {
44         int p=i-1;
45         while (p) if (b[i].x-b[i].r<=b[p].x) insert(i,p),fa[getfather(i)]=getfather(p),p=getfather(i)-1; else break;
46     }
47     for (int i=1;i<=n;i++) fa[i]=i;
48     for (int i=n-1;i;i--)
49     {
50         int p=i+1;
51         while (p<=n) if (b[i].x+b[i].r>=b[p].x) insert(i,p),fa[getfather(i)]=getfather(p),p=getfather(i)+1; else break;
52     }
53     for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i);
54     for (int u=1;u<=n;u++) for (int i=head[u];i;i=e[i].from) if (bel[u]!=bel[e[i].to]) ins(bel[u],bel[e[i].to]);
55     for (int i=1;i<=num;i++) fa[i]=i;
56     for (int i=1;i<=num;i++) count(i),ans=(ans+1ll*val[i]*size[i]%mo)%mo;
57     printf("%lld",ans);
58 }