Luogu

LOJ

分析

最简单的想法是每个炸弹向能炸到的所有炸弹连一条边，然后统计每个炸弹能到达多少个点。

然而这样子边数是 $O(n^2)$ 级别的。注意到一个炸弹一定是向一段区间连边，那么线段树优化连边即可。

统计的话，注意到每个炸弹能到达的的点一定是一段区间。那么缩点后按拓扑序算一下能到达的最小编号和最大编号就好了。

代码

`// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=(500000<<2)+10;
const int mod=1e9+7;

int n; ll x[N],r[N];

vector<int> E[N],G[N];
int id[N];

#define ls (o<<1)
#define rs (o<<1|1)
inline void build(int o,int l,int r) {
    if (l==r) { id[l]=o; return; }
    int mid=(l+r)>>1;
    E[o].push_back(ls),build(ls,l,mid);
    E[o].push_back(rs),build(rs,mid+1,r);
}
inline void link(int o,int l,int r,int ql,int qr,int u) {
    if (ql<=l&&r<=qr) { E[u].push_back(o); return; }
    int mid=(l+r)>>1;
    if (ql<=mid) link(ls,l,mid,ql,qr,u);
    if (qr>mid) link(rs,mid+1,r,ql,qr,u);
}
#undef ls
#undef rs

int dfn[N],low[N],tim=0,sta[N],in[N],top=0,bl[N],tot=0;
inline void tarjan(int u) {
    dfn[u]=low[u]=++tim,sta[++top]=u,in[u]=1;
    for (re int v:E[u]) {
        if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
        else if (in[v]) low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u]) { ++tot;
        while ("%longge") {
            int t=sta[top--]; bl[t]=tot,in[t]=0;
            if (u==t) break;
        }
    }
}

int deg[N],mx[N],mn[N];
inline void dfs(int u) {
    for (re int v:G[u])
        dfs(v),mx[u]=max(mx[u],mx[v]),mn[u]=min(mn[u],mn[v]);
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) x[i]=read(),r[i]=read();
    build(1,1,n);
    for (re int i=1;i<=n;++i) {
        int L=lower_bound(x+1,x+n+1,x[i]-r[i])-x;
        int R=upper_bound(x+1,x+n+1,x[i]+r[i])-x-1;
        link(1,1,n,L,R,id[i]);
    }
    for (re int i=1;i<=n<<1;++i) if (!dfn[i]) tarjan(i);
    for (re int u=1;u<=n<<1;++u)
        for (re int v:E[u]) {
            if (bl[u]==bl[v]) continue;
            G[bl[u]].push_back(bl[v]),++deg[bl[v]];
        }
    for (re int i=1;i<=tot;++i) mx[i]=-2e9,mn[i]=2e9;
    for (re int i=1;i<=n;++i) { int t=bl[id[i]];
        mx[t]=max(mx[t],i),mn[t]=min(mn[t],i);
    }
    for (re int i=1;i<=tot;++i) if (!deg[i]) dfs(i);
    int ans=0;
    for (re int i=1;i<=n;++i) { int t=bl[id[i]];
        ans=(ans+1ll*i*(mx[t]-mn[t]+1))%mod;
    }
    printf("%d\n",ans);
    return 0;
}