P5025

高效高效，坚持高效，耶( •̀ ω •́ )y
首先，我们考虑引爆每个炸弹，它能引爆的区间是多少（即：它能对答案做出什么贡献）
易得炸一个=炸这个区间
为什么？
你只要引爆了一个大炸弹（例如沙皇）
它就会把它的左边和右边一起抬走
所以考虑线性维护每个炸弹向左/向右能炸到哪里
代码十分精华：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,l[500005],r[500005];
long long ans,a[500005],range[500005];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",a+i,range+i);
		l[i]=r[i]=i;
	}
	for(int i=2;i<=n;i++){
		while(l[i]>1&&a[i]-a[l[i]-1]<=range[i]){
			range[i]=max(range[i],range[l[i]-1]-(a[i]-a[l[i]-1]));
			l[i]=l[l[i]-1];
		}
	}
	for(int i=n-1;i>=1;i--){
		while(r[i]<n&&a[r[i]+1]-a[i]<=range[i]){
			l[i]=min(l[i],l[r[i]+1]);
			r[i]=r[r[i]+1];
		}
	}
	for(int i=1;i<=n;i++)
		ans=(ans+1ll*i*(r[i]-l[i]+1))%mod;
	printf("%lld\n",ans);
	return 0;
}