题目大意

在一条直线上有\(N\)个炸弹，每个炸弹的坐标是\(X_i\)，爆炸半径是 \(R_i\)，

当一个炸弹爆炸时，如果另一个炸弹所在位置\(X_j\)满足：

$ X_i-R_i\leq X_j \leq X_i+R_i $

那么，该炸弹也会被引爆。

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

\(0\leq N \leq 500000\)，\(-10^{18} \leq X_i \leq 10^{18}\)

题目分析

考试的时候想到的是一个\(n\ log^2n\)的倍增做法。

令\(mi[i][j]\),\(mx[i][j]\)表示引爆第\(i\)个炸弹，连锁反应引爆\(2^j\)次炸弹后爆炸范围的最左端与最右端。

那么由\(2^j\)向\(2^{j+1}\)更新时，我们需要得知目前爆炸范围内其他炸弹的\(mi[i][j]\)的最小值以及\(mx[i][j]\)的最大值。这个可以用\(RMQ\)或者线段树维护。

因此总时间复杂度\(O(n\ log^2n)\)，有点爆炸。

标解是线段树优化建边后，\(tarjan\)缩点+拓扑排序。

\(TLE:\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Maxn=500005,mod=1e9+7;
template<class T>
void read(T&x){
    x=0;T f=1;char ch=getchar();
    while(!isdigit(ch))ch!='-'?:f=-1,ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    x*=f;
}
int n,mx[Maxn][21],mi[Maxn][21],bl[Maxn][2],br[Maxn][2],Lg[Maxn];
ll a[Maxn],r[Maxn],tmp[Maxn];
void Build(int x){
    for(int i=1;i<=n;++i)mi[i][0]=bl[i][x],mx[i][0]=br[i][x];
    for(int j=1;j<=18;++j)
        for(int i=1;i+(1<<j)-1<=n;++i){
            mi[i][j]=min(mi[i][j-1],mi[i+(1<<j-1)][j-1]);
            mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]);
        }
}
inline int ask_min(int x,int y){
    int k=Lg[y-x+1];
    return min(mi[x][k],mi[y-(1<<k)+1][k]);
}
inline int ask_max(int x,int y){
    int k=Lg[y-x+1];
    return max(mx[x][k],mx[y-(1<<k)+1][k]);
}
int main(){
    read(n);
    for(int i=1;i<=n;++i)read(a[i]),read(r[i]);
    for(int i=1;i<=n;++i)tmp[i]=a[i],Lg[i]=log2(i);
    int cur=0,pre=1;
    for(int i=1;i<=n;++i){
        a[i]=i;
        bl[i][0]=lower_bound(tmp+1,tmp+n+1,tmp[i]-r[i])-tmp;
        br[i][0]=upper_bound(tmp+1,tmp+n+1,tmp[i]+r[i])-tmp-1;
    }
    for(int j=1;j<=19;++j){
        pre=cur;cur^=1;
        Build(pre);
        for(int i=1;i<=n;++i){
            bl[i][cur]=ask_min(bl[i][pre],br[i][pre]);
            br[i][cur]=ask_max(bl[i][pre],br[i][pre]);
        }
    }
    ll ans=0;
    for(int i=1;i<=n;++i){
        ans=(ans+1ll*(br[i][cur]-bl[i][cur]+1)*i)%mod;
    }
    cout<<ans<<"\n";
}

\(AC:\)

#include <bits/stdc++.h>
using namespace std;
template<class T>
void read(T &x){
    x=0;T f=1;char ch=getchar();
    while(!isdigit(ch))ch!='-'?:f=-1,ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    x*=f;
}
const int Maxn=500005,mod=1e9+7;
typedef long long ll;
int n,Pos[Maxn],h[Maxn*4];
ll a[Maxn],r[Maxn];
struct edge{int to,next;}e[Maxn*20];
void addedge(int x,int y){
    static int cnt;
    e[++cnt]=(edge){y,h[x]};h[x]=cnt;
}
#define ls v<<1
#define rs v<<1|1
int L[Maxn*4],R[Maxn*4],Min[Maxn*4],Max[Maxn*4];
void Build(int v,int l,int r){
    L[v]=l;R[v]=r;
    if(l==r)return Pos[l]=v,void();
    int mid=l+r>>1;
    Build(ls,l,mid);Build(rs,mid+1,r);
    addedge(v,ls);addedge(v,rs);
}
void Insert(int v,int l,int r,int a,int b,int p){
    if(l>b||r<a)return;
    if(a<=l&&r<=b)return addedge(p,v);
    int mid=l+r>>1;
    Insert(ls,l,mid,a,b,p);Insert(rs,mid+1,r,a,b,p);
}
int dfn[Maxn*4],low[Maxn*4],bel[Maxn*4],st[Maxn*4],rd[Maxn*4],top,Scc,Sign;
bool in[Maxn*4];
struct info{int x,i,y;};
void dfs(int x){
    static vector<info>S;
    int i,y;
call:
    dfn[x]=low[x]=++Sign;st[++top]=x;in[x]=1;
    for(i=h[x];i;i=e[i].next){
        y=e[i].to;
        if(!dfn[y]){
            S.push_back((info){x,i,y});
            x=y;goto call;
Return:;
            low[x]=min(low[x],low[y]);
        }
        else if(in[y])low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]){
        Scc++;
        Max[Scc]=0;Min[Scc]=n;
        for(;;){
            y=st[top--];in[y]=0;
            Max[Scc]=max(Max[Scc],R[y]);
            Min[Scc]=min(Min[Scc],L[y]);
            bel[y]=Scc;if(y==x)break;
        }
    }
    if(S.size()){x=S.back().x;i=S.back().i;y=S.back().y;S.pop_back();goto Return;}
}
vector<int>G[Maxn*4];
void Topsort(){
    queue<int>Q;
    for(int i=1;i<=Scc;i++)if(!rd[i])Q.push(i);
    while(Q.size()){
        int x=Q.front();Q.pop();
        for(int i=0;i<G[x].size();i++){
            int y=G[x][i];
            if(!--rd[y])Q.push(y);
            Min[y]=min(Min[y],Min[x]);
            Max[y]=max(Max[y],Max[x]);
        }
    }
}
int main(){
    read(n);
    for(int i=1;i<=n;i++)read(a[i]),read(r[i]);
    for(int i=1;i<=4*n;i++)L[i]=n+1,R[i]=0;
    Build(1,1,n);
    for(int i=1;i<=n;i++){
        Insert(1,1,n,lower_bound(a+1,a+n+1,a[i]-r[i])-a,upper_bound(a+1,a+n+1,a[i]+r[i])-a-1,Pos[i]);
    }
    for(int i=1;i<=4*n;i++)if(!dfn[i])dfs(i);
    for(int x=1;x<=4*n;x++)
        for(int i=h[x];i;i=e[i].next){
            int y=e[i].to;
            if(bel[x]!=bel[y]){
                G[bel[y]].push_back(bel[x]);
                rd[bel[x]]++;
            }
        }
    Topsort();
    ll Ans=0;
    for(int i=1;i<=n;i++){
        Ans=(Ans+1ll*i*(Max[bel[Pos[i]]]-Min[bel[Pos[i]]]+1))%mod;
    }
    cout<<Ans<<"\n";
}
/*
4
1 1
5 1
6 5
15 15

*/