题目描述

样例

4
1 1
5 1
6 5
15 15

32

分析

虽然这题正解是tarjan,但我决定不用tarjan(实际上是我没想出来)，很容易想到，对于每一个炸弹，我们看它是否能波及到下一

个炸弹，然后从下一个炸弹找它能波及到的炸弹，想一想实际上不是很复杂，用线性递推可以搞，每一个炸弹对每一个炸弹的贡

献只有能炸或不能炸，所以只需要用记忆化处理一下最左能波及到的和最右能波及到的位置就可以了，因为有记忆化，每一个炸

弹最多被遍历一遍，其他炸弹再遍历到相同炸弹时用之前处理的就行了，由此复杂度O(n),十分优秀。

下面就是怎么实现了，对于左边界，每次去更新到新的炸弹的距离是否满足，满足就更新一下最左边界，因为由前向后遍历，之

前炸弹能炸到的炸弹越往后是逐渐累积的，这里需要更新一下能波及的最大右边界，因为有可能左边炸弹范围更大，所以要提前

处理，右边界方法相同，处理右边界时要多处理一次左边界，因为上面处理左边界是是从左向右的，有可能右面范围更大，思路

毕。。。

solution

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=500010,mod=1e9+7;
int n,l[maxn],r[maxn],ans;
struct node{int site,fan;}m[maxn];
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&m[i].site,&m[i].fan);
		l[i]=r[i]=i;//预处理左右边界 
	}
	for(int i=1;i<=n;i++)//找左边界 
	{
		while(m[i].site-m[l[i]-1].site<=m[i].fan&&l[i]>1)//下一个未判定的炸弹可以被现在的最大波及范围攻击到 
		{
			m[i].fan=max(m[i].fan,m[l[i]-1].fan-(m[i].site-m[l[i]-1].site));
			/*
			更新可以波及到的右边界 
			这里不用将范围更新成m[l[i]-1].fan，因为如果它减去区间还比m[i].fan大，那么在
			之前它一定会更新它的最左边界，所以这里只要更新右边界即可
			*/ 
			l[i]=l[l[i]-1];//左边界变成这个炸弹能波及到的左边界 
		}
	}
	for(int i=n;i>=1;i--)
	{
		while(m[r[i]+1].site-m[i].site<=m[i].fan&&r[i]<n)//原理同上，上面已经更新过最大右边界范围了 
		{
//			cout<<"!";
			l[i]=min(l[i],l[r[i]+1]);//同上，更新的是下一个炸弹，不是下一个炸弹波及到的右边界 
			r[i]=r[r[i]+1];
		}
	}
	for(int i=1;i<=n;i++)
	{
		ans+=(r[i]-l[i]+1)*i;//l[i],r[i]都是闭区间，要加一 
	}
	printf("%lld\n",ans%mod);
	
	return 0;
}