[SNOI 2017] 炸弹

题目描述: 给定炸弹和爆炸范围，求对于每个炸弹连锁爆炸的炸弹总和对\(1e9+7\)取膜

思路：

为啥都是线段树+TS+tarjan呢？

实在是搞不懂~~

线性\(O(n)\)递推即可.

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1000010;

const int mod = 1e9+7ull;

#define debug(x) cout<<"x:"<<x<<endl;

#define ll long long

inline ll read() {

	ll q=0,f=1;char ch=getchar();

	while(!isdigit(ch)) {

		if(ch=='-')f =-1;ch=getchar();

	}

	while(isdigit(ch)) {

		q=q*10+ch-'0';ch=getchar();

	}

	return q*f;

}

struct node{

	ll num;

	ll pos;

}nod[maxn];

ll n;

ll L[maxn];

ll R[maxn];

ll ans;

int main() {

	n = read();

	for(ll i = 1;i <= n; ++i) {

		nod[i].pos = read(),nod[i].num = read();

	}

	for(ll i = 1;i <= n; ++i) {

		L[i] = i;

		while(nod[i].pos - nod[L[i] - 1].pos <= nod[i].num && L[i] > 1) {

			L[i] = L[L[i] - 1];

			nod[i].num = max(nod[i].num,nod[L[i]].num - (nod[i].pos - nod[L[i]].pos));

		}

	}

	for(ll i = n;i >= 1; --i) {

		R[i] = i;

		while(nod[R[i] + 1].pos - nod[i].pos <= nod[i].num && R[i] < n) {

			R[i] = R[R[i] + 1];

			L[i] = min(L[i],L[R[i]]);

		}

	}

	for(ll i = 1;i <= n; ++i) {

//		debug(i);

//		debug(L[i]);

//		debug(R[i]);

		ans = (ans + (R[i] - L[i] + 1) * i) % mod;

	}

	printf("%lld\n",ans);

	return 0;

}

/*

题目有毒orz

*/

巴特西

[SNOI 2017] 炸弹

题目描述: 给定炸弹和爆炸范围，求对于每个炸弹连锁爆炸的炸弹总和对\(1e9+7\)取膜

最新文章

热门文章