题意
link.
题解
我们充分发扬人类智慧。
考虑到可能连锁爆炸，我们不能通过一个单纯的二分来解决问题。
考虑 \(dp\)。
记 \(f(i)\) 为第 \(i\) 个点爆炸，最远能引爆到哪个坐标小于它的点。
\(g(i)\) 为第 \(i\) 个点爆炸，最远能引爆到哪个坐标大于它的点。
我们以 \(f\) 为例，\(g\) 可以通过同样的方法求得。
对于每一个 \(i\)，二分出一个最小的 \(l\) 满足 \(\lvert x_l - x_i \rvert \le r_i\)，此时区间 \(\left [ l, i - 1 \right ]\) 就是 \(i\) 通过一次爆炸能爆到的。
但是可以连锁爆炸，所以我们需要选出一个 \(t \in \left [ l, i - 1 \right ]\) 使得 \(f(t)\) 最小。
此时就可以转移了：
\[f(i) = \min \{ f(t), l\} \]但找出 \(t\) 的复杂度是 \(\mathcal O(n)\) 的，总时间复杂度是 \(\mathcal O (n^2 + n \log n)\) 的，这样就可以光荣的获得 \(55\) 分了。
考虑开一棵线段树，维护 \(x_i - r_i\) 的最小值和最小值的编号。
因为满足 \(f(t)\) 最小的 \(t\) 也一定满足 \(x_i - r_i\) 最小，反之同理。
此时只需要查询一下区间 \(\left [ l, i - 1 \right ]\) 最小值编号即可作为 \(t\) 转移了。
\(g\) 只需要开一棵最大值线段树即可。
然后你就会发现它错了（貌似样例都过不了）。
我们不能把思维固定在 \(f\) 转移 \(f\)，\(g\) 转移 \(g\) 上。
有可能我们先爆炸炸到 \(i\) 右边，然后通过引爆 \(i\) 右边一枚非常强悍的炸弹然后再引爆到左边。
所以要反着再转移一次。
然后你就会发现它又错了（貌似会错第二个点）。
因为我们通过走右边到达了左边，此时我们还需要再走一次左边，因为走过来不一定是最小的（真烦）。
右边同理。
然后你就会发现似乎可以无穷无尽地走下去了……
不管怎么说先重复几边上文的过程吧。
但值得庆幸的是，重复两遍就能过了，因为此时已经把所有方案考虑完了（或者是数据水了点）。
时间复杂度：\(\mathcal O (Q \times n \log n)\)，带一点线段树的并不小的常数（\(Q\) 取决于 \(dp\) 多少次，也就是数据强度，此时 \(Q = 2\)）。
如果你们想的话，可以把二分放到外面预处理，省掉了一点点 \(dp\) 的常数。
namespace zqh {
const int N = 5e5 + 5;
int n;
struct bomb { // 炸弹结构体
int x, r;
} a[N];
int dpl[N], dpr[N];
struct segment { // 线段
int mx, mx_id; // 最大值，最大值编号，下同
int mn, mn_id;
};
struct segment_tree { // 线段树
#define ls (id << 1)
#define rs (id << 1 | 1)
segment seg[N << 2];
void pushup(int id) {
if (seg[ls].mn < seg[rs].mn) {
seg[id].mn = seg[ls].mn;
seg[id].mn_id = seg[ls].mn_id;
} else {
seg[id].mn = seg[rs].mn;
seg[id].mn_id = seg[rs].mn_id;
}
if (seg[ls].mx > seg[rs].mx) {
seg[id].mx = seg[ls].mx;
seg[id].mx_id = seg[ls].mx_id;
} else {
seg[id].mx = seg[rs].mx;
seg[id].mx_id = seg[rs].mx_id;
}
}
void build(int id, int lft, int rht) { // 建树
seg[id].mn = LLONG_MAX;
seg[id].mx = LLONG_MIN;
if (lft == rht) {
seg[id].mn_id = seg[id].mx_id = lft;
seg[id].mn = a[lft].x - a[lft].r;
seg[id].mx = a[lft].x + a[lft].r;
return;
}
int mid = (lft + rht) / 2;
build(ls, lft, mid);
build(rs, mid + 1, rht);
pushup(id);
}
segment query(int id, int lft, int rht, int l, int r) {
if (rht < l || r < lft)
return {LLONG_MIN, -1, LLONG_MAX, -1};
if (l <= lft && rht <= r)
return seg[id];
int mid = (lft + rht) / 2;
segment t1 = query(ls, lft, mid, l, r),
t2 = query(rs, mid + 1, rht, l, r), ret;
if (t1.mn < t2.mn) {
ret.mn = t1.mn;
ret.mn_id = t1.mn_id;
} else {
ret.mn = t2.mn;
ret.mn_id = t2.mn_id;
}
if (t1.mx > t2.mx) {
ret.mx = t1.mx;
ret.mx_id = t1.mx_id;
} else {
ret.mx = t2.mx;
ret.mx_id = t2.mx_id;
}
return ret;
}
} st;
void dp() { // 跑一次 dp
for (int i = 2; i <= n; i++) { // 算 f（直接走左边）
int l = 1, r = i - 1, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (abs(a[mid].x - a[i].x) <= a[i].r) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (ans == -1)
continue;
segment t = st.query(1, 1, n, ans, i - 1);
dpl[i] = min(dpl[i],
min((dpl[t.mn_id] == -1 ? LLONG_MAX : dpl[t.mn_id]), ans));
}
for (int i = n - 1; i >= 1; i--) { // 算 g（直接走右边）
int l = i + 1, r = n, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (abs(a[mid].x - a[i].x) <= a[i].r) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if (ans == -1)
continue;
segment t = st.query(1, 1, n, i + 1, ans);
dpr[i] = max(dpr[i],
max((dpr[t.mx_id] == -1 ? LLONG_MIN : dpr[t.mx_id]), ans));
}
for (int i = 2; i <= n; i++) { // 算 g（走左边再走右边）
int l = 1, r = i - 1, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (abs(a[mid].x - a[i].x) <= a[i].r) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (ans == -1)
continue;
segment t = st.query(1, 1, n, ans, i - 1);
dpr[i] = max(dpr[i],
max((dpr[t.mx_id] == -1 ? LLONG_MIN : dpr[t.mx_id]), ans));
}
for (int i = n - 1; i >= 1; i--) { // 算 f（走右边再走左边）
int l = i + 1, r = n, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (abs(a[mid].x - a[i].x) <= a[i].r) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if (ans == -1)
continue;
segment t = st.query(1, 1, n, i + 1, ans);
dpl[i] = min(dpl[i],
min((dpl[t.mn_id] == -1 ? LLONG_MAX : dpl[t.mn_id]), ans));
}
}
void init() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].r;
dpl[i] = dpr[i] = i;
}
}
void solve() {
st.build(1, 1, n); // 建树
dp(); // 跑两次
dp();
int ans = 0;
for (int i = 1; i <= n; i++) { // 统计答案
// cout << dpl[i] << " " << dpr[i] << endl;
if (dpl[i] == -1 && dpr[i] == -1) {
ans = 1LL * (ans + 1 * i) % mod;
continue;
}
if (dpl[i] == -1) {
ans = (ans + 1LL * (1LL * (dpr[i] - i + 1) % mod * i) % mod) % mod;
continue;
}
if (dpr[i] == -1) {
ans = (ans + 1LL * (1LL * (i - dpl[i] + 1) % mod * i) % mod) % mod;
continue;
}
ans = (ans + 1LL * (1LL * (dpr[i] - dpl[i] + 1) % mod * i) % mod) % mod;
}
cout << ans;
}
void main() {
init();
solve();
}
} // namespace zqh
这样速度快得飞起，在 \(n = 500000\) 时都可以在 1820ms 内卡过
标签：int,题解,mx,seg,lft,SNOI2017,P5025,id,dp From： https://www.cnblogs.com/zphh/p/18474052