[LOJ#2255][BZOJ5017][Snoi2017]炸弹
2024-10-21 05:56:00
[LOJ#2255][BZOJ5017][Snoi2017]炸弹
试题描述
在一条直线上有 N 个炸弹,每个炸弹的坐标是 Xi,爆炸半径是 Ri,当一个炸弹爆炸时,如果另一个炸弹所在位置 Xj 满足:
Xi−Ri≤Xj≤Xi+Ri,那么,该炸弹也会被引爆。
现在,请你帮忙计算一下,先把第 i 个炸弹引爆,将引爆多少个炸弹呢?
输入
第一行,一个数字 N,表示炸弹个数。
第 2∼N+1行,每行 2 个数字,表示 Xi,Ri,保证 Xi 严格递增。
N≤500000
−10^18≤Xi≤10^18
0≤Ri≤2×10^18
输出
一个数字,表示Sigma(i*炸弹i能引爆的炸弹个数),1<=i<=N mod10^9+7。
输入示例
输出示例
数据规模及约定
见“输入”
题解
显然一个炸弹能引爆的范围一定是一段连续的区间,于是我们就考虑求它的左右端点。
考虑一种容易漏掉的情况:一个炸弹 a 引爆左边一个炸弹 b,b 引爆 a 右侧的 c,c 引爆 b 左侧的 d……这种情况我们不难发现从 a 到 d,炸弹的爆炸半径一定倍增(比如若 b 的半径小于 a 半径的两倍,由于 b 可以引爆 a 右边的 c,所以 a 可以直接引爆 c,不需要借助 b)。
剩下的情况就是连锁爆炸(即爆炸只往一个方向传递),处理这个东西我们只需要用单调栈正反扫一遍处理出每个炸弹向左向右连锁爆炸能炸到的最远的炸弹就可以了(不妨设向左向右最远的炸弹编号分别为 lft[i] 和 rgt[i])。
最后我们用 RMQ 维护一下 lft[i] 的最小值,rgt[i] 的最大值;若要求炸弹 i 的范围,就是不停扩张的过程,最多扩张 log(n) 次。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define LL long long const int BufferSize = 1 << 16;
char buffer[BufferSize], *Head, *Tail;
inline char Getchar() {
if(Head == Tail) {
int l = fread(buffer, 1, BufferSize, stdin);
Tail = (Head = buffer) + l;
}
return *Head++;
}
LL read() {
LL x = 0, f = 1; char c = Getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }
return x * f;
} #define maxn 500010
#define maxlog 19
#define MOD 1000000007 int n, q[maxn], top, lft[maxn], rgt[maxn];
LL X[maxn], R[maxn]; int Log[maxn], mn[maxlog][maxn], mx[maxlog][maxn];
void init() {
for(int i = 1; i <= n; i++) mn[0][i] = lft[i], mx[0][i] = rgt[i];
for(int j = 1; (1 << j) <= n; j++)
for(int i = 1; i + (1 << j) - 1 <= n; i++)
mn[j][i] = min(mn[j-1][i], mn[j-1][i+(1<<j-1)]),
mx[j][i] = max(mx[j-1][i], mx[j-1][i+(1<<j-1)]);
return ;
}
int _l, _r;
void query(int ql, int qr) {
int t = Log[qr-ql+1];
_l = min(mn[t][ql], mn[t][qr-(1<<t)+1]);
_r = max(mx[t][ql], mx[t][qr-(1<<t)+1]);
return ;
} int main() {
n = read();
for(int i = 1; i <= n; i++) X[i] = read(), R[i] = read(); Log[1] = 0;
for(int i = 2; i <= n; i++) Log[i] = Log[i>>1] + 1; lft[1] = 1;
q[top = 1] = 1;
for(int i = 2; i <= n; i++) {
int l = 1, r = top;
while(l < r) {
int mid = l + r >> 1;
if(X[q[mid]] < X[i] - R[i]) l = mid + 1; else r = mid;
}
if(X[q[l]] < X[i] - R[i]) lft[i] = i;
else lft[i] = lft[q[l]];
while(top && lft[i] <= lft[q[top]]) top--;
q[++top] = i;
}
rgt[n] = n;
q[top = 1] = n;
for(int i = n - 1; i; i--) {
int l = 1, r = top;
while(l < r) {
int mid = l + r >> 1;
if(X[q[mid]] > X[i] + R[i]) l = mid + 1; else r = mid;
}
// printf("%d: %d | %d %lld\n", i, l, q[l], X[q[l]]);
if(X[q[l]] > X[i] + R[i]) rgt[i] = i;
else rgt[i] = rgt[q[l]];
while(top && rgt[i] >= rgt[q[top]]) top--;
q[++top] = i;
}
// for(int i = 1; i <= n; i++) printf("LR [%d %d]\n", lft[i], rgt[i]);
init();
int ans = 0;
for(int i = 1; i <= n; i++) {
int l = lft[i], r = rgt[i];
_l = n + 1; _r = 0;
for(;;) {
query(l, r);
if(l == _l && r == _r) break;
l = _l; r = _r;
}
ans += ((LL)i * (r - l + 1)) % MOD;
if(ans >= MOD) ans -= MOD;
// printf("[%d, %d]\n", l, r);
} printf("%d\n", ans); return 0;
}
最新文章
- Centos YUM 升级PHP
- iOS---searchBar 搜索框 光标初始位置后移
- mono 开发
- Android开发快速入门(环境配置、Android Studio安装)
- 配置JDK环境变量
- JavaScript Math 对象方法
- 【20160924】GOCVHelper MFC增强算法(5)
- TLS学习总结
- 基于Apache2配置Radius认证
- asp.net EasyUI DataGrid 实现增删改查
- arcGis引入Dll报无法嵌入互操作类型错误解决方法
- 在Mac OS X下安装Android Studio
- Spring二 Bean详解
- Harris Corner(Harris角检测)
- [SCOI2005]王室联邦
- 没人看系列----css 随笔
- 使用 ctypes 进行 Python 和 C 的混合编程
- 初识mysql数据库
- Skip level 1 on 1
- windows 10 开发学习资料,Windows-universal-samples学习笔记系列一:App settings