本文共 6654 字，大约阅读时间需要 22 分钟。

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

前言

这题是哈老师给的神题
然后他给了我一个有一点点复杂的做法
于是帅爷爷就又教了我一个方法
然后我在今天做操的时候仔细斟酌了一下，觉得很对，于是就A了

题解

首先，我们可以建图。。
就是每个点对他可以炸到的范围连一条边。。
然后对于每个点dfs一次，他可以从他连的点得到新的l和r
这里要注意的时，虽然说每个点必须要访问，更新答案，这样才能确保他的答案是对的
然后由于可能边数很大，于是要用线段树优化建图，就好了

CODE:

#include<cstdio>#include<cstdlib>#include<iostream>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const LL N=2000010;int n;LL X[N],R[N];const int MOD=1e9+7;struct qq{    int x,y,last;}s[N*8];int Num,last[N];int ll[N],rr[N];void init (int x,int y){    Num++;    s[Num].x=x;s[Num].y=y;    s[Num].last=last[x];    last[x]=Num;    return ;}void Ins (){    Num=0;memset(last,-1,sizeof(last));    scanf("%d",&n);    for (int u=1;u<=n;u++)        scanf("%lld%lld",&X[u],&R[u]);}struct qr{    int l,r;    int s1,s2;}tr[N];int num;int pos[N];void bt (int l,int r){    int a=++num;    tr[a].l=l;tr[a].r=r;    ll[a]=l;rr[a]=r;    if (l==r)     {        pos[l]=a;        return ;    }    int mid=(l+r)>>1;    tr[a].s1=num+1;bt(l,mid);    tr[a].s2=num+1;bt(mid+1,r);    init(a,tr[a].s1);init(a,tr[a].s2);}void Link (int now,int l,int r,int x){    if (tr[now].l==l&&tr[now].r==r)    {        init(x,now);        return ;    }    int mid=(tr[now].l+tr[now].r)>>1;    int s1=tr[now].s1,s2=tr[now].s2;    if (r<=mid) Link(s1,l,r,x);    else if (l>mid) Link(s2,l,r,x);    else Link(s1,l,mid,x),Link(s2,mid+1,r,x);}void Bt (){    num=0;bt(1,n);    //for (int u=1;u<=n;u++) printf("%d ",pos[u]);    for (int u=1;u<=n;u++)    {        int l=1,r=u;        int p;        while (l<=r)        {            int mid=(l+r)>>1;            if (X[mid]+R[u]>=X[u]) {p=mid;r=mid-1;}            else l=mid+1;        }        if (p!=u) Link(1,p,u-1,pos[u]);    //  printf("%d %d %d\n",p,u-1,pos[u]);        l=u;r=n;        while (l<=r)        {            int mid=(l+r)>>1;            if (X[mid]-R[u]<=X[u]) {p=mid;l=mid+1;}            else r=mid-1;        }        if (p!=u) Link(1,u+1,p,pos[u]);    //  printf("%d %d %d\n",u+1,u-1,pos[u]);    }}bool vis[N];int mymax (int x,int y){  return x>y?x:y;}int mymin (int x,int y){  return x<y?x:y;}void dfs (int x){    vis[x]=true;    for (int u=last[x];u!=-1;u=s[u].last)    {        int y=s[u].y;        if (vis[y]==false) dfs(y);        ll[x]=mymin(ll[x],ll[y]);        rr[x]=mymax(rr[x],rr[y]);    }}void solve (){    memset(vis,false,sizeof(vis));    for (int u=1;u<=num;u++)         dfs(u);    long long ans=0;    for (int u=1;u<=n;u++)     {        //printf("YES:%d %d\n",ll[pos[u]],rr[pos[u]]);        ans=(ans+(long long)u*(rr[pos[u]]-ll[pos[u]]+1)%MOD)%MOD;    }    printf("%lld\n",ans);}int main(){    Ins();    Bt();    solve();    return 0;}

Update 9.9 方法被人hack了。。
其实是bzoj的数据太水了。。
上面的方法其实有很大的漏洞，也跑不出来。。
其实有环的时候就会有很大的问题。。
这个自己对拍一下，就应该能找到了
所以我们要用强连通缩点，就可以跑过去了。。
我用的Claris的代码对拍

新的CODE:

#include<cstdio>#include<cstdlib>#include<iostream>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int N=2000010;int n;LL X[N],R[N];const int MOD=1e9+7;struct qq{    int x,y,last;}s[N*8];int Num,last[N];int ll[N],rr[N];void init (int x,int y){    Num++;    s[Num].x=x;s[Num].y=y;    s[Num].last=last[x];    last[x]=Num;    return ;}void Ins (){    Num=0;memset(last,-1,sizeof(last));    scanf("%d",&n);    for (int u=1;u<=n;u++)        scanf("%lld%lld",&X[u],&R[u]);}struct qr{    int l,r;    int s1,s2;}tr[N];int num;int pos[N];void bt (int l,int r){    int a=++num;    tr[a].l=l;tr[a].r=r;    ll[a]=l;rr[a]=r;    if (l==r)     {        pos[l]=a;        return ;    }    int mid=(l+r)>>1;    tr[a].s1=num+1;bt(l,mid);    tr[a].s2=num+1;bt(mid+1,r);    init(a,tr[a].s1);init(a,tr[a].s2);}void Link (int now,int l,int r,int x){    if (tr[now].l==l&&tr[now].r==r)    {        init(x,now);        return ;    }    int mid=(tr[now].l+tr[now].r)>>1;    int s1=tr[now].s1,s2=tr[now].s2;    if (r<=mid) Link(s1,l,r,x);    else if (l>mid) Link(s2,l,r,x);    else Link(s1,l,mid,x),Link(s2,mid+1,r,x);}void Bt (){    num=0;bt(1,n);    //for (int u=1;u<=n;u++) printf("%d ",pos[u]);    for (int u=1;u<=n;u++)    {        int l=1,r=u;        int p;        while (l<=r)        {            int mid=(l+r)>>1;            if (X[mid]+R[u]>=X[u]) {p=mid;r=mid-1;}            else l=mid+1;        }        if (p!=u) Link(1,p,u-1,pos[u]);    //  printf("%d %d %d\n",p,u-1,pos[u]);        l=u;r=n;        while (l<=r)        {            int mid=(l+r)>>1;            if (X[mid]-R[u]<=X[u]) {p=mid;l=mid+1;}            else r=mid-1;        }        if (p!=u) Link(1,u+1,p,pos[u]);    //  printf("%d %d %d\n",u+1,u-1,pos[u]);    }}bool vis[N];int mymax (int x,int y){  return x>y?x:y;}int mymin (int x,int y){  return x<y?x:y;}int L1[N],R1[N];void dfs (int x){    vis[x]=true;    for (int u=last[x];u!=-1;u=s[u].last)    {        int y=s[u].y;        if (vis[y]==false) dfs(y);        L1[x]=mymin(L1[x],L1[y]);        R1[x]=mymax(R1[x],R1[y]);    }}int dfn[N],low[N],belong[N],cnt,sta[N],lalal,shen;bool in[N];void dfs1 (int x){    dfn[x]=low[x]=++lalal;    sta[++cnt]=x;    in[x]=true;    for (int u=last[x];u!=-1;u=s[u].last)    {        int y=s[u].y;        if (dfn[y]==-1)        {            dfs1(y);            low[x]=mymin(low[x],low[y]);        }        else if (in[y]) low[x]=mymin(dfn[y],low[x]);    }    if (low[x]==dfn[x])    {        shen++;        L1[shen]=1<<30;        R1[shen]=0;        int now;        do        {            now=sta[cnt--];            belong[now]=shen;            L1[shen]=mymin(ll[now],L1[shen]);            R1[shen]=mymax(rr[now],R1[shen]);            in[now]=false;        }while (now!=x);    }}void solve (){    shen=lalal=cnt=0;    memset(dfn,-1,sizeof(dfn));    memset(in,false,sizeof(in));    for (int u=1;u<=num;u++)        if (dfn[u]==-1)            dfs1(u);   // for (int u=1;u<=num;u++) printf("%d %d\n",u,belong[u]);    num=0;memset(last,-1,sizeof(last));    for (int u=1;u<=Num;u++)        if (belong[s[u].x]!=belong[s[u].y])        {            int X=belong[s[u].x],Y=belong[s[u].y];            num++;            s[num].x=X;s[num].y=Y;            s[num].last=last[X];            last[X]=num;        }    memset(vis,false,sizeof(vis));    for (int u=1;u<=shen;u++)         dfs(u);    long long ans=0;    for (int u=1;u<=n;u++)     {        ans=(ans+(long long)u*(R1[belong[pos[u]]]-L1[belong[pos[u]]]+1)%MOD)%MOD;    }    printf("%lld\n",ans);}int main(){    Ins();    Bt();    solve();    return 0;}