题解 P5471 【[NOI2019]弹跳】
Ireliaღ
2019-09-12 13:26:45
**看到各路大佬又是优化建图打标记，又是一次松弛一个矩形，又是树上删点之类的，看不懂，这里提供一个更加简单的思路**
## 基本思路
NOI同步赛我打了个KDTree优化建图，当场MLE爆炸，40分。但是通过最基本的KDTree优化建图思路可以想出正解，我们可以大概了解一下。
- 首先，KDTree的每个节点维护着一个坐标和一个矩形的信息。所以我们把原图上的点就叫做实点，编号范围为$[1, n]$，KDTree上的节点叫做虚点，编号范围为$[n + 1, 2n]$
- 我们对于每一个实点，遍历装在这个位置的所有弹跳机，假设当前弹跳机的时间为$t$，起点为$u$，我们上树查询。
- 对于在树上的一个节点$x$
- 如果$x$管辖的矩形完全在弹跳机的目标矩形外，`return`
- 如果$x$管辖的矩形完全在弹跳机的目标矩形内，从$u$向$x$建边，权值为$t$，`return`
- 两区间交叉情况
- 如果$x$上维护的坐标在目标矩形内，从$u$向$x - n$建边，权值为$t$
- 递归查询两个儿子
- 最后对于$\forall x \in [1, n]$，从$x + n$向$x$建边即可
以上为KDTree优化建图的基本思路。代码如下（如果有铁憨憨把这份代码粘上去交了我也拦不住
```cpp
// luogu-judger-enable-o2
#include <algorithm>
#include <iostream>
#include <cstring>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 7e4 + 5;
const int INF = 0x3f3f3f3f;
int n, m, W, H;
int ID(int x, int y) {
if (y == 0) return x;
else return x + n;
}
struct Edge{
int to, val;
Edge(int v, int w) {
to = v;
val = w;
}
};
vector<Edge> g[MAXN << 1];
int vis[MAXN << 1], dis[MAXN << 1];
typedef vector<Edge> :: iterator ITE;
typedef pair<int, int> POI;
void AddEdge(int u, int v, int w) {
g[u].push_back(Edge(v, w));
}
void Dijkstra(int s) {
priority_queue<POI> q;
memset(dis, INF, sizeof(dis));
dis[s] = 0; vis[s] = true; q.push(make_pair(dis[s], s));
while (!q.empty()) {
int u = q.top().second; q.pop(); vis[u] = false;
for (ITE it = g[u].begin(); it != g[u].end(); it++) {
int v = it->to;
if (dis[v] > dis[u] + it->val) {
dis[v] = dis[u] + it->val;
if (!vis[v]) {
q.push(make_pair(dis[v], v));
vis[v] = true;
}
}
}
}
}
struct Data{
int pos[2];
int id;
};
int Cmp0(Data x, Data y) {
return x.pos[0] != y.pos[0] ? (x.pos[0] < y.pos[0]) : (x.pos[1] < y.pos[1]);
}
int Cmp1(Data x, Data y) {
return x.pos[1] != y.pos[1] ? (x.pos[1] < y.pos[1]) : (x.pos[0] < y.pos[0]);
}
Data data[MAXN];
struct Node{
Data data;
int mn[2], mx[2], d;
Node *ch[2];
Node() {}
Node(Data data, int d) : data(data), d(d) {
ch[0] = NULL;
ch[1] = NULL;
for (int i = 0; i < 2; i++) {
mn[i] = data.pos[i];
mx[i] = data.pos[i];
}
}
}pool[MAXN << 1];
Node *NewNode(Data data, int d) {
static int p = 0;
pool[p] = Node(data, d);
return pool + p++;
}
Node *rt = NULL;
void Update(Node *now) {
for (int i = 0; i < 2; i++) {
if (now->ch[i]) {
for (int j = 0; j < 2; j++) {
now->mn[j] = min(now->mn[j], now->ch[i]->mn[j]);
now->mx[j] = max(now->mx[j], now->ch[i]->mx[j]);
}
}
}
}
void Build(Node *&now, int l, int r, int d) {
if (l > r) return;
int mid = l + r >> 1;
if (d == 0) {
nth_element(data + l, data + mid, data + r + 1, Cmp0);
now = NewNode(data[mid], d);
} else {
nth_element(data + l, data + mid, data + r + 1, Cmp1);
now = NewNode(data[mid], d);
}
Build(now->ch[0], l, mid - 1, (d + 1) % 2);
Build(now->ch[1], mid + 1, r, (d + 1) % 2);
Update(now);
if (now->ch[0]) AddEdge(ID(now->data.id, 1), ID(now->ch[0]->data.id, 1), 0);
if (now->ch[1]) AddEdge(ID(now->data.id, 1), ID(now->ch[1]->data.id, 1), 0);
}
void Jump(Node *now, int u, int mn[], int mx[], int w) {
if (!now) return;
int allin = true, allout = false, insq = true;
for (int i = 0; i < 2; i++) {
if (now->mx[i] < mn[i] || now->mn[i] > mx[i]) allout = true;
if (now->mx[i] > mx[i] || now->mn[i] < mn[i]) allin = false;
if (now->data.pos[i] < mn[i] || now->data.pos[i] > mx[i]) insq = false;
}
if (allout) return;
if (allin) {
AddEdge(ID(u, 0), ID(now->data.id, 1), w);
//cerr << '#';
return;
}
if (insq) {
AddEdge(ID(u, 0), ID(now->data.id, 0), w);
//cerr << '$';
}
Jump(now->ch[0], u, mn, mx, w);
Jump(now->ch[1], u, mn, mx, w);
}
void Init() {
cin >> n >> m >> W >> H;
for (int i = 1; i <= n; i++) {
cin >> data[i].pos[0] >> data[i].pos[1];
data[i].id = i;
}
for (int i = 1; i <= n; i++) AddEdge(ID(i, 1), ID(i, 0), 0);
Build(rt, 1, n, 0);
//cerr << '*';
int mn[2], mx[2], x, y;
for (int i = 1; i <= m; i++) {
cin >> x >> y;
cin >> mn[0] >> mx[0];
cin >> mn[1] >> mx[1];
Jump(rt, x, mn, mx, y);
//cerr << '*';
}
//cerr << '*';
}
void Work() {
Dijkstra(1);
for (int i = 2; i <= n; i++) cout << dis[ID(i, 0)] << endl;
}
int main() {
ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
//freopen("jump.in", "r", stdin);
//freopen("jump.out", "w", stdout);
Init();
Work();
return 0;
}
```
## 优化
这里提供可以优化的两条锦囊妙计。
1. **首先，我们可以假装我们把图建了出来，不建边**
假装把图建出来？你可能要问了，我们都没有建边，怎么知道从一个点出发，能到达哪些点？
我们当然可以知道！就像在赛场上切掉此题的某位银牌大佬 @龙之吻—水货 所说：
> 首先你有一棵树
> 你要把这棵树完全变成你的工具
> 你建边的目的是要知道从一个点出发能到达哪些点
想通了就OK了，根据刚才建图的思路，我们完全知道从一个节点出发能到达哪些节点。
- 对于一个虚点$u$，能到达的节点如下
- 它的两个儿子对应的虚点
- 它所对应的实点
- 对于一个实点$u$
- 在跑`SPFA`最短路时，如果从队列中拿出实点，直接遍历从$x$出发的弹跳机，上树查询
- 对于在树上的一个虚点$x$
- 如果$x$管辖的区间完全在目标区间外，`return`
- 如果$x$管辖的区间完全在目标区间内，松弛$x$
- 对于区间交叉情况
- 如果$x$对应的坐标在目标区间内，松弛$x - n$
- 递归查询两个儿子
- 松弛时加上的距离为弹跳机用时
你看完这个思路，感觉有点眼熟，返回去看了一眼40分思路
完全一样？是的。
代码如下
```cpp
// luogu-judger-enable-o2
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 7e4 + 5;
const int MAXM = 15e4 + 5;
const int INF = 0x3f3f3f3f;
int n, m, W, H;
struct Edge{
Edge *nxt;
int val;
int mn[2], mx[2];
Edge() {}
Edge(int val, int l[], int r[], Edge *nxt) : val(val), nxt(nxt) {
memcpy(mn, l, sizeof(mn));
memcpy(mx, r, sizeof(mx));
}
}epool[MAXM];
Edge *NewEdge(int val, int l[], int r[], Edge *nxt) {
static int ecnt = 0;
epool[ecnt] = Edge(val, l, r, nxt);
return &epool[ecnt++];
}
Edge *head[MAXN];
void AddEdge(int u, int w, int l[], int r[]) {
head[u] = NewEdge(w, l, r, head[u]);
}
struct Point{
int id;
int x[2];
Point() {}
Point(int id, int a, int b) : id(id) {
x[0] = a;
x[1] = b;
}
}data[MAXN];
int Comp0(Point a, Point b) {
return (a.x[0] == b.x[0]) ? (a.x[1] < b.x[1]) : (a.x[0] < b.x[0]);
}
int Comp1(Point a, Point b) {
return (a.x[1] == b.x[1]) ? (a.x[0] < b.x[0]) : (a.x[1] < b.x[1]);
}
struct Node{
Point pos;
Node *ch[2];
int mn[2], mx[2];
Node() {}
Node(Point pos) : pos(pos) {
ch[0] = ch[1] = NULL;
for (int i = 0; i < 2; i++) mn[i] = mx[i] = pos.x[i];
}
}npool[MAXN];
void Update(Node *now) {
for (int i = 0; i < 2; i++) {
if (now->ch[i]) {
for (int j = 0; j < 2; j++) {
now->mn[j] = min(now->mn[j], now->ch[i]->mn[j]);
now->mx[j] = max(now->mx[j], now->ch[i]->mx[j]);
}
}
}
}
Node *NewNode(Point pos) {
static int ncnt = 0;
npool[ncnt] = Node(pos);
return &npool[ncnt++];
}
Node *rt = NULL;
Node *ima[MAXN];
void Build(Node *&now, int l, int r, int d) {
if (l > r) return;
int mid = l + r >> 1;
if (d == 0) nth_element(data + l, data + mid, data + r + 1, Comp0);
else nth_element(data + l, data + mid, data + r + 1, Comp1);
now = NewNode(data[mid]);
ima[now->pos.id] = now;
Build(now->ch[0], l, mid - 1, d ^ 1);
Build(now->ch[1], mid + 1, r, d ^ 1);
Update(now);
}
int q[MAXN << 1], hd, tl, len;
int dis[MAXN << 1];
int vis[MAXN << 1];
void Relax(int v, int w) {
if (dis[v] > w) {
dis[v] = w;
if (!vis[v]) {
q[++tl % len] = v;
vis[v] = 1;
}
}
}
int AllIn(Node *now, int mn[], int mx[]) {
for (int i = 0; i < 2; i++) {
if (now->mn[i] < mn[i] || now->mx[i] > mx[i]) return 0;
}
return 1;
}
int AllOut(Node *now, int mn[], int mx[]) {
for (int i = 0; i < 2; i++) {
if (now->mn[i] > mx[i] || now->mx[i] < mn[i]) return 1;
}
return 0;
}
int Inside(Node *now, int mn[], int mx[]) {
for (int i = 0; i < 2; i++) {
if (now->pos.x[i] < mn[i] || now->pos.x[i] > mx[i]) return 0;
}
return 1;
}
void Jump(Node *now, int mn[], int mx[], int w) {
if (!now) return;
if (AllOut(now, mn, mx)) return;
if (AllIn(now, mn, mx)) {
Relax(now->pos.id + n, w);
return;
}
if (Inside(now, mn, mx)) Relax(now->pos.id, w);
Jump(now->ch[0], mn, mx, w);
Jump(now->ch[1], mn, mx, w);
}
void Spfa(int s) {
memset(dis, INF, sizeof(dis));
dis[s] = 0;
hd = 1; tl = 0; q[++tl % len] = s; vis[s] = 1;
while (hd <= tl) {
int u = q[hd++ % len]; vis[u] = 0;
if (u > n) {
Relax(u - n, dis[u]);
if (ima[u - n]->ch[0]) Relax(ima[u - n]->ch[0]->pos.id + n, dis[u]);
if (ima[u - n]->ch[1]) Relax(ima[u - n]->ch[1]->pos.id + n, dis[u]);
} else {
for (Edge *e = head[u]; e; e = e->nxt) {
Jump(rt, e->mn, e->mx, dis[u] + e->val);
}
}
}
}
void Init() {
cin >> n >> m >> W >> H;
len = n * 2;
for (int i = 1; i <= n; i++) {
data[i].id = i;
cin >> data[i].x[0] >> data[i].x[1];
}
Build(rt, 1, n, 0);
int l[2], r[2], u, t;
for (int i = 1; i <= m; i++) {
cin >> u >> t >> l[0] >> r[0] >> l[1] >> r[1];
AddEdge(u, t, l, r);
}
}
void Work() {
Spfa(1);
// for (int i = 1; i <= n * 2; i++) cerr << dis[i] << " ";
// cerr << "\n";
for (int i = 2; i <= n; i++) cout << dis[i] << "\n";
}
int main() {
Init();
Work();
return 0;
}
```
88分到手，（如果有铁憨憨抄上去我也没啥说的
我们可以使用第二条锦囊妙计：
2. **关于SPFA，它死了**
van♂van♂没想到，NOI2018卡了SPFA，NOI2019竟然还要卡
行了不墨迹了，直接换Dijkstra，以下为AC代码
```cpp
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int, int> POI;
const int MAXN = 7e4 + 5;
const int MAXM = 15e4 + 5;
const int INF = 0x3f3f3f3f;
int n, m, W, H;
struct Edge{
Edge *nxt;
int val;
int mn[2], mx[2];
Edge() {}
Edge(int val, int l[], int r[], Edge *nxt) : val(val), nxt(nxt) {
memcpy(mn, l, sizeof(mn));
memcpy(mx, r, sizeof(mx));
}
}epool[MAXM];
Edge *NewEdge(int val, int l[], int r[], Edge *nxt) {
static int ecnt = 0;
epool[ecnt] = Edge(val, l, r, nxt);
return &epool[ecnt++];
}
Edge *head[MAXN];
void AddEdge(int u, int w, int l[], int r[]) {
head[u] = NewEdge(w, l, r, head[u]);
}
struct Point{
int id;
int x[2];
Point() {}
Point(int id, int a, int b) : id(id) {
x[0] = a;
x[1] = b;
}
}data[MAXN];
int Comp0(Point a, Point b) {
return (a.x[0] == b.x[0]) ? (a.x[1] < b.x[1]) : (a.x[0] < b.x[0]);
}
int Comp1(Point a, Point b) {
return (a.x[1] == b.x[1]) ? (a.x[0] < b.x[0]) : (a.x[1] < b.x[1]);
}
struct Node{
Point pos;
Node *ch[2];
int mn[2], mx[2];
Node() {}
Node(Point pos) : pos(pos) {
ch[0] = ch[1] = NULL;
for (int i = 0; i < 2; i++) mn[i] = mx[i] = pos.x[i];
}
}npool[MAXN];
void Update(Node *now) {
for (int i = 0; i < 2; i++) {
if (now->ch[i]) {
for (int j = 0; j < 2; j++) {
now->mn[j] = min(now->mn[j], now->ch[i]->mn[j]);
now->mx[j] = max(now->mx[j], now->ch[i]->mx[j]);
}
}
}
}
Node *NewNode(Point pos) {
static int ncnt = 0;
npool[ncnt] = Node(pos);
return &npool[ncnt++];
}
Node *rt = NULL;
Node *ima[MAXN];
void Build(Node *&now, int l, int r, int d) {
if (l > r) return;
int mid = l + r >> 1;
if (d == 0) nth_element(data + l, data + mid, data + r + 1, Comp0);
else nth_element(data + l, data + mid, data + r + 1, Comp1);
now = NewNode(data[mid]);
ima[now->pos.id] = now;
Build(now->ch[0], l, mid - 1, d ^ 1);
Build(now->ch[1], mid + 1, r, d ^ 1);
Update(now);
}
//int q[MAXN << 1], hd, tl, len;
priority_queue<POI, vector<POI>, greater<POI> > q;
int dis[MAXN << 1];
int vis[MAXN << 1];
void Relax(int v, int w) {
if (dis[v] > w) {
q.push(make_pair(dis[v] = w, v));
}
}
int AllIn(Node *now, int mn[], int mx[]) {
for (int i = 0; i < 2; i++) {
if (now->mn[i] < mn[i] || now->mx[i] > mx[i]) return 0;
}
return 1;
}
int AllOut(Node *now, int mn[], int mx[]) {
for (int i = 0; i < 2; i++) {
if (now->mn[i] > mx[i] || now->mx[i] < mn[i]) return 1;
}
return 0;
}
int Inside(Node *now, int mn[], int mx[]) {
for (int i = 0; i < 2; i++) {
if (now->pos.x[i] < mn[i] || now->pos.x[i] > mx[i]) return 0;
}
return 1;
}
void Jump(Node *now, int mn[], int mx[], int w) {
if (!now) return;
if (AllOut(now, mn, mx)) return;
if (AllIn(now, mn, mx)) {
Relax(now->pos.id + n, w);
return;
}
if (Inside(now, mn, mx)) Relax(now->pos.id, w);
Jump(now->ch[0], mn, mx, w);
Jump(now->ch[1], mn, mx, w);
}
void Dijkstra(int s) {
memset(dis, INF, sizeof(dis));
dis[s] = 0;
// hd = 1; tl = 0; q[++tl % len] = s; vis[s] = 1;
q.push(make_pair(dis[s], s));
int cnt = 0;
while (!q.empty()) {
if (q.top().first != dis[q.top().second]) {
q.pop();
continue;
}
int u = q.top().second; q.pop();
if (u > n) {
Relax(u - n, dis[u]);
if (ima[u - n]->ch[0]) Relax(ima[u - n]->ch[0]->pos.id + n, dis[u]);
if (ima[u - n]->ch[1]) Relax(ima[u - n]->ch[1]->pos.id + n, dis[u]);
} else {
for (Edge *e = head[u]; e; e = e->nxt) {
Jump(rt, e->mn, e->mx, dis[u] + e->val);
}
}
}
}
void Init() {
ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m >> W >> H;
// len = n * 2;
for (int i = 1; i <= n; i++) {
data[i].id = i;
cin >> data[i].x[0] >> data[i].x[1];
}
Build(rt, 1, n, 0);
int l[2], r[2], u, t;
for (int i = 1; i <= m; i++) {
cin >> u >> t >> l[0] >> r[0] >> l[1] >> r[1];
AddEdge(u, t, l, r);
}
}
void Work() {
Dijkstra(1);
// for (int i = 1; i <= n * 2; i++) cerr << dis[i] << " ";
// cerr << "\n";
for (int i = 2; i <= n; i++) cout << dis[i] << "\n";
}
int main() {
Init();
Work();
return 0;
}
```