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 需要行走的距离至少是多少？
分析
最优化问题，考虑DP
那么，这个空间明显只能开下一维数组，若我们设\(f[i]\)表示使用前\(i\)个跳板且必须使用第\(i\)个跳板，能够节省的最大距离(因为直接判断到底是多少比较困难，正难则反，考虑维护这玩意)
设木板\(i\)在\((x_{i,1},y_{i,1})\),可以跳到\((x_{i,2},y_{i,2})\)
则考虑转移，先按\(x\)为第一关键字\(y\)为第二关键字排序，那么转移即为
\(f[i]=\max{\lbrace f[j]+s[i]\rbrace}(x_{j,2}\le x_{i,1},y_{j,2}\le y_{i,1})\)
其中\(s[i]=x_{i,2}+y_{i,2}-x_{i,1}-x_{i,2}\)
考虑如何优化，我们发现，一个跳板可以拆成两个点分别统计影响，假设我们拆成三元组\((1,x_1,y_1),(-1,x_2,y_2)\)
那么因为排序满足了转移的第一维条件，而时间复杂度只能是\(n\log n\)级别左右，这启发我们考虑优化条件\(y_{j,2}\le y_{i,1}\)
这个条件的维护扔进一只BIT就好了
那么算法流程为：
- 离散化坐标，统计\(s\)数组，拆点
- 将\(2p\)个点排序
- DP，从小到大扫描各个点
(1). 当目前的点属于\(1\)类型，此时我们统计这个点的id的答案，在树状数组中查询\(\le y\)的最大值即可
(2). 否则，将这个点的答案扔进树状数组的\(y\)位置
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
#define scanf scanf_s
#define N 1000500
struct node {
int id, x, y, lz;
}a[N << 1];
int b[N << 1], c[N << 2], n, m, f[N], cnt, s[N], tot;
bool cmp1(node a, node b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
#define lowbit(x) (x & - x)
void add(int x, int k) {
while (x <= cnt) {
c[x] = max(c[x], k);
x += lowbit(x);
}
}
int ask(int x) {
int ans = -0x3f3f3f3f;
while (x) {
ans = max(ans, c[x]);
x -= lowbit(x);
}
return ans;
}
void init() {
memset(c, 0, sizeof c);
memset(f, 0xcf, sizeof f);
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%lld%lld%lld%lld", &b[cnt + 1], &b[cnt + 2], &b[cnt + 3], &b[cnt + 4]);
cnt += 4;
a[++tot] = { i,b[cnt - 3],b[cnt - 2] ,1 };
a[++tot] = { i,b[cnt - 1],b[cnt] ,-1 };
s[i] = f[i] = b[cnt - 1] + b[cnt] - b[cnt - 2] - b[cnt - 3];
// printf("%lld\n",f[i]);
}
}
void lsh() {
sort(b + 1, b + cnt + 1);
cnt = unique(b + 1, b + cnt + 1) - b - 1;
for (int i = 1; i <= m << 1; i++) {
// printf("%d %d\n",a[i].x,a[i].y);
a[i].x = lower_bound(b + 1, b + cnt + 1, a[i].x) - b;
a[i].y = lower_bound(b + 1, b + cnt + 1, a[i].y) - b;
// printf("%d %d\n",a[i].x,a[i].y);
}
sort(a + 1, a + m + m + 1, cmp1);
}
void solve() {
for (int i = 1; i <= m << 1; i++) {
if (a[i].lz == 1) {
// puts("A");
f[a[i].id] = max(f[a[i].id], ask(a[i].y) + s[a[i].id]);
}
else {
// puts("B");
add(a[i].y, f[a[i].id]);
}
}
int ans = 0;
for (int i = 1; i <= m; i++)ans = max(ans, f[i]);
printf("%lld\n", n + n - ans);
}
signed main() {
// freopen("P6007_2.in","r",stdin);
init();
lsh();
solve();
}