P5025 [SNOI2017]炸弹

不难发现，在引爆一个炸弹之后发生的一串连锁反应中，只有两种情况：

1.左边（右边）的炸弹依旧引爆左边（右边）的炸弹。

2.左边（右边）的炸弹引爆了原本右边（左边）引爆不了的炸弹。

并且第二种情况可能会在反应中反复很多次。

假设在第二种情况中连缩反应是从$a->b$开始的，对于$a$的答案的计算，只需要从$b$递推过来即可。

于是考虑先从左往右递推处理出来每一个点左边的所有能够引爆的炸弹，以及引爆了左边的炸弹之后新增加的炸弹的半径对于右边炸弹的影响。

不难发现第$n$个炸弹目前的答案就是第$n$个炸弹最终的答案。

然后从右往左倒着推一遍，处理出每个点右边的范围，这时第$n-1$个炸弹的答案是从第$n$个炸弹推过来的，又因为第$n$个炸弹的答案是最终的答案，只需要把第$n$个炸弹的答案合并到第$n-1$个就好了，这样使得第$n-1$个炸弹的答案也是最终的正确答案了。

这样一直递推，一定会使得最后的答案都是正确答案。

考虑时间复杂度的计算，一个点的递推次数取决于它的爆炸范围内有多少个互相不可达的子块。如果有一个点的爆炸范围内有很多的不可达的子块，那么它便会和这些子块合并，不难发现，每个点至多会被用到2次，所以复杂度线性。

#include<bits/stdc++.h>

#define REP(i,a,b) for(int i=a,i##_end_=b;i<=i##_end_;++i)
#define DREP(i,a,b) for(int i=a,i##_end_=b;i>=i##_end_;--i)
typedef long long ll;

using namespace std;

void File(){
    freopen("bzoj5017.in","r",stdin);
    freopen("bzoj5017.out","w",stdout);
}

template<typename T>void read(T &_){
    T __=0,mul=1; char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')mul=-1;
        ch=getchar();
    }
    while(isdigit(ch))__=(__<<1)+(__<<3)+(ch^'0'),ch=getchar();
    _=__*mul;
}

const int maxn=5e5+10;
const ll mod=1e9+7;
int n,l[maxn],r[maxn];
ll x[maxn],y[maxn],ans;

int main(){
//  File();
    read(n);
    REP(i,1,n)read(x[i]),read(y[i]),l[i]=r[i]=i;
    REP(i,1,n)while(l[i]>1 && x[i]-x[l[i]-1]<=y[i]){
        y[i]=max(y[i],x[l[i]-1]+y[l[i]-1]-x[i]);
        //cout<<x[l[i]-1]+y[l[i]-1]-x[i]<<" ";
        l[i]=l[l[i]-1];
        y[i]=max(y[i],x[l[i]]+y[l[i]]-x[i]);
        //cout<<x[l[i]]+y[l[i]]-x[i]<<endl;
    }
    DREP(i,n,1)while(r[i]<n && x[r[i]+1]-x[i]<=y[i]){
        l[i]=min(l[i],l[r[i]+1]);
        //cout<<l[r[i]+1]<<" ";
        r[i]=r[r[i]+1];
        l[i]=min(l[i],l[r[i]]);
        //cout<<l[r[i]]<<endl;
    }
    REP(i,1,n){
        ans=(ans+1ll*i*(r[i]-l[i]+1)%mod)%mod;
        //cout<<l[i]<<" "<<r[i]<<endl;
    }
    printf("%lld\n",(ans+mod)%mod);
    return 0;
}