P5025 【[SNOI2017]炸弹】
四倍空间四倍空间四倍空间！ (我好弱啊因为这个多交两遍
这道题的难点（恶心之处）在于一个小炸弹的爆炸可能会引发一个大炸弹的爆炸就会直接对答案产生很大的影响
（蒟蒻第一次看到这题直接掉到了坑里qwq
如果一个点向整段区间都有边可以考虑线段树优化建图
边数可以从
算是很大的优化了qwq
这道题的线段树优化建图其他题解里的大佬们讲得很清楚，就不说太多了qwq
连完边之后呢qwqwq
这些边这么鬼畜，直接乱搞整来整去的我这样的蒟蒻一定会写挂的叭qwq
直接乱搞似乎没有什么太优秀的复杂度（假装正经
缩个点试试叭
受不了了，太清新了，wsl
然后这题就不难了
对于这样的一个DAG ，我们阔以维护每个点所能达到的最左边的端点和最右边的端点
那么直接反向建边然后跑一个拓扑排序即可处理出这个东西
（这句话有点绕，代码里的一堆数组嵌套也是因为这个qwq
到这里这题思路就差不多了qwq
详细的代码实现就在代码里加注释吧qwq
下面贴出来代码
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
// 才不是什么猛男写法qwqwq
using namespace std;
inline int read() {
int op = 1, a = 0; char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') op = -1;
for (; c >= '0' && c <= '9'; c = getchar()) a = a * 10 + c - '0';
return op * a;
}
const int mod = 1e9 + 7;
const int maxn = 500003;
int n;
int X[maxn], R[maxn];
int cnt;
int head[maxn << 2];
struct Edge {
int fr, to, nxt;
Edge(int _fr, int _to, int _nxt) {
this -> fr = _fr;
this -> to = _to;
this -> nxt = _nxt;
} Edge() {}
} e[maxn << 3];
inline void add_edge(int u, int v) {e[++cnt] = Edge(u, v, head[u]); head[u] = cnt;}
#define lc (u << 1)
#define rc (u << 1 | 1)
struct Seg {
int l, r, id; //id表示线段树上的这个节点对应的炸弹的编号
// id为0就代表是一段区间而不是单个的炸弹
void init(int x) {l = r = x; id = l;}
Seg operator + (const Seg& rhs) const {
Seg u; u.l = l, u.r = rhs.r;
u.id = 0; return u;
}
} tr[maxn << 2];
int ind[maxn];// 一个点在线段树中对应的节点编号
inline void update(int u) {tr[u] = tr[lc] + tr[rc];}
// 先把朴素的线段树建出来
void build(int u, int l, int r) {
if (l == r) {tr[u].init(l); ind[l] = u; return;}
int mid = l + r >> 1;
build(lc, l, mid), build(rc, mid + 1, r);
add_edge(u, lc), add_edge(u, rc);
update(u);
}
// 然后把每个炸弹给它管辖的区间连边
void modify(int u, int l, int r, int x) {
if (l <= tr[u].l && r >= tr[u].r) {
if (x != u) add_edge(x, u);
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(lc, l, r, x);
if (r > mid) modify(rc, l, r, x);
}
// 再次强调四倍空间（并感叹一下我的弱qwqwq
int siz[maxn << 2]; //siz存一个点中有几个炸弹
bool vis[maxn << 2];
int r, s[maxn << 2];
int num, belong[maxn << 2];
int Time, dfn[maxn << 2], low[maxn << 2];
int leftest[maxn << 2], rightest[maxn << 2];
// 表示缩点后的每一个点能到达的左端点和右端点
void Tarjan(int u) {
dfn[u] = low[u] = ++Time;
s[++r] = u, vis[u] = 1; int R = r;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (vis[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
num++;
leftest[num] = 0x3f3f3f3f, rightest[num] = 0;
for (int i = R; i <= r; i++) {
vis[s[i]] = 0;
belong[s[i]] = num;
if (tr[s[i]].id) siz[num]++;
leftest[num] = min(leftest[num], tr[s[i]].l);
rightest[num] = max(rightest[num], tr[s[i]].r);
}
r = R - 1;
}
}
int in[maxn << 2];
void rebuild() {
int tmp = cnt;
cnt = 0;
memset(head, 0, sizeof head);
for (int i = 1; i <= tmp; i++) {
int u = belong[e[i].fr], v = belong[e[i].to];
if (u == v) continue;
add_edge(v, u); in[u]++;
}
}
// 其实就是完善leftest数组和rightest数组
void Topo() {
queue<int> q;
for (int i = 1; i <= num; i++)
if (in[i] == 0) q.push(i);
for (; q.size(); ) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
leftest[v] = min(leftest[v], leftest[u]);
rightest[v] = max(rightest[v], rightest[u]);
in[v]--; if (!in[v]) q.push(v);
}
}
}
int ans;
signed main() {
n = read();
for (int i = 1; i <= n; i++) X[i] = read(), R[i] = read();
build(1, 1, n);
for (int i = 1; i <= n; i++) {
int l = lower_bound(X + 1, X + n + 1, X[i] - R[i]) - X;
int r = upper_bound(X + 1, X + n + 1, X[i] + R[i]) - X - 1;
if (l <= r) modify(1, l, r, ind[i]);
}
Tarjan(1); rebuild(); Topo();
// 因为是线段树所以不会存在一些不连通的情况
// 直接 Tarjan(1) 即可
for (int i = 1; i <= n; i++) {
ans += i * (rightest[belong[ind[i]]] - leftest[belong[ind[i]]] + 1);
ans %= mod;
}
cout << ans << '\n';
return 0;
}2020.2.17 UPD
关于复杂度： 由于建图是