题目描述：

# P6007 [USACO20JAN] Springboards G

## 题目描述

Bessie 在一个仅允许沿平行于坐标轴方向移动的二维方阵中。她从点 $(0,0)$ 出发，想要到达 $(N,N)$（$1 \leq N \leq 10^9$）。为了帮助她达到目的，在方阵中有 $P$（$1 \leq P \leq 10^5$）个跳板。每个跳板都有其固定的位置 $(x_1,y_1)$，如果 Bessie 使用它，会落到点 $(x_2,y_2)$。

Bessie 是一个过程导向的奶牛，所以她仅允许她自己向上或向右行走，从不向左或向下。类似地，每个跳板也设置为不向左或向下。Bessie 需要行走的距离至少是多少？

## 输入格式

输入的第一行包含两个空格分隔的整数 $N$ 和 $P$。

以下 $P$ 行每行包含四个整数 $x_1,y_1,x_2,y_2$，其中 $x_1 \leq x_2$ 且 $y_1 \leq y_2$。

所有跳板的位置和目标位置均不相同。

## 输出格式

输出一个整数，为 Bessie 到达点 $(N,N)$ 需要行走的最小距离。

## 输入输出样例 #1

### 输入 #1

```
3 2
0 1 0 2
1 2 2 3
```

### 输出 #1

```
3
```

## 说明/提示

### 样例解释

Bessie 的最佳路线为：

- Bessie 从 (0,0) 走到 (0,1)（1 单位距离）。
- Bessie 跳到 (0,2)。
- Bessie 从 (0,2) 走到 (1,2)（1 单位距离）。
- Bessie 跳到 (2,3)。
- Bessie 从 (2,3) 走到 (3,3)（1 单位距离）。

Bessie 总共走过的路程为 3 单位距离。

### 子任务

- 测试点 $2 \sim 5$ 满足 $P \leq 1000$。
- 测试点 $6 \sim 15$ 没有额外限制。

解析：

先将所有坐标的 y 坐标离散化。

然后把所有坐标按照 x 为第一关键字, y 为第二关键字排序。

从前往后遍历, 用 dpi​ 表示从 (0,0) 到 xi​,yi​ 的答案。

怎么更新信息?

考虑用 k 节点更新 i 节点。

如果 k 节点可以直接用跳板直接跳到 i 节点, 那么 dp 值相同。

否则要一步一步走过去。如果能更新, 那么 dpi​=dpk​+xi​−xk​+yi​−yk​

那么 dpi​−xi​−yi​=dpk​−xk​−yk​

如果设 fi​=dpi​−xi​−yi​，那么 fi​=fk​ !

那么现在丢掉 dp 数组然后使用 f 数组。

现在如果k 节点可以直接用跳板直接跳到 i 节点

fi​=dpi​−xi​−xj​=dpk​−xi​−yi​=fk​+xk​+yk​−xi​−yi​

那么考虑谁能够更新他呢？

只有 x 坐标小于等于他而且 y 坐标小于等于他的节点可以更新。

这时显然 x 坐标小于等于 i 节点已经满足, 而 y 坐标没有满足。 现在要求 y 坐标处于 0...yi​ 的节点。

fi​ 是 min(f1,2...i−1​) , 显然每次把 f 值丢进树状数组里面就可以单次 O(logn) 维护了

如果 i 是一个跳板的末端, 直接更新一下就好了qwq

最后答案就是 min(fi​+n+n) (如果把他当作一个节点, 那么 f 值就是 min(fi​), 所以答案是 min(fi​+n+n))

code：

#include<bits/stdc++.h>
#define N 200010
using namespace std;
int n, m, a[N], fr[N], to[N], Ans;
struct node {
	int x, y, yy, id;
} p[N];
bool cmp(node aa, node bb) {
	return aa.x == bb.x ? aa.y < bb.y : aa.x < bb.x;
}
bool ycmp(node aa, node bb) {
	return aa.y < bb.y;
}
int ans[N];
void add(int x, int val) {
	for(; x <= m * 2; x += (x & -x)) ans[x] = min(ans[x], val);
} 
int qzh(int x) {
	int Ans = 0; 
	for(; x; x -= (x & -x)) Ans = min(Ans, ans[x]);
	return Ans;
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++) {
		scanf("%d%d", &p[i].x, &p[i].y), p[i].id = i;
		scanf("%d%d", &p[i + m].x, &p[i + m].y), p[i + m].id = i;
	}
	sort(p + 1, p + m * 2 + 1, ycmp);
	p[0].y = -1;
	for(int i = 1; i <= 2 * m; i++) p[i].yy = p[i - 1].yy + (p[i - 1].y != p[i].y);
	sort(p + 1, p + m * 2 + 1, cmp);
	for(int i = 1; i <= m * 2; i++) {
		if(fr[p[i].id]) to[p[i].id] = i;
		else fr[p[i].id] = i;
	}
	for(int i = 1; i <= m * 2; i++) {
		a[i] = min(a[i], qzh(p[i].yy));
		if(fr[p[i].id] == i) a[to[p[i].id]] = min(a[to[p[i].id]], 
			a[i] + p[i].x + p[i].y - p[to[p[i].id]].x - p[to[p[i].id]].y);
		add(p[i].yy, a[i]);
		Ans = min(Ans, a[i]);
	}
	printf("%d\n", Ans + n * 2);
	return 0;
}