题解 P6007 [USACO20JAN]Springboards G

N*N 的矩阵，从 (0,0) 走到 (N,N)，每次只能往右和往上走（求曼哈顿距离），有 P 个跳板可以从 \((x_1,y_1)\) 无代价转移到 \((x_2,y_2)\)，求需要行走的最少距离

\(N\le10^9,P\le 10^5\)

思路

问题转化

\(O(N^2)\) 和 \(O(P^2)\) 的最短路都显然不行，我们可以观察一些性质并考虑 dp。

每次答案距离只能从左下方转移而来，即 \(f(x_1,y_1)\rightarrow f(x_2,y_2)\) 满足 \(x1\le x_2,y1\le y_2\)。

直接 dp 需要考虑不从跳板走的距离，正难则反，我们设 \(f(x,y)\) 表示走到 \((x,y)\) 能够省下的最大距离。

我们需要维护 \(x1\le x_2,y1\le y_2\) 的最大 \(f(x_1,y_1)\)，至此我们将问题转化成二维偏序。

CDQ

现在的问题是，每个跳板有两个端点：起点 \((x_1,y_1)\) 和终点 \((x_2,y_2)\)，并且只能从前一个终点转移到其右上方的一个起点。

我们可以把一个跳板拆成两个点，起点作为查询，终点作为修改。

接下来就是 CDQ 的套路：处理左区间，更新左区间对右区间的贡献，处理右区间，一定要保证分治的先后顺序正确。

复杂度 \(O(nlog^2n)\)。

细节

写完交上去一直 WA 一个点，还下不了数据急躁半天。

后来想到，可能会有某个跳板的终点的另一个跳板的起点重合，排序不当会处理不了。

可以输入时提前处理掉，或者排序时保证位置重合的修改在询问之前就行（具体见代码的 cmp 函数）。

代码

#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;

template<typename TT> inline void read(TT &x) {}

const int N = 2e5 + 9;

struct Node {
    int x1, y1, x2, y2;
};
struct Point {
    int x, y, opt, id;
};

int n, m, cnt;
int f[N], ans[N], len[N];
Node a[N];
Point p[N];

inline int calc_dis(int x1, int y1, int x2, int y2) {
    return x2 - x1 + y2 - y1;
}

inline bool cmp_x(const Point &i, const Point &j) {
    if (i.x == j.x) {
        if (i.y == j.y) return i.opt > j.opt;// 位置重合，让修改在前
        return i.y < j.y;
    }
    return i.x < j.x;
}
inline bool cmp_y(const Point &i, const Point &j) {
    if (i.y == j.y) {
        if (i.x == j.x) return i.opt > j.opt;
        return i.x < j.x;
    }
    return i.y < j.y;
}

void CDQ(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    CDQ(l, mid), sort(p+mid+1, p+r+1, cmp_y);
    int maxn = 0;
    for (int i = mid+1, j = l, k = -1; i <= r; ++i) {
        if (p[i].opt) continue;
        int id = p[i].id;
        while (j <= mid && p[j].y <= p[i].y) {
            if (p[j].opt)
                maxn = max(maxn, ans[p[j].id]);
            j++;
        }
        ans[p[i].id] = max(ans[p[i].id], maxn + len[p[i].id]);
    }
    sort(p+mid+1, p+r+1, cmp_x);
    CDQ(mid+1, r);
    sort(p+l, p+r+1, cmp_y);
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= m; ++i)
        read(a[i].x1), read(a[i].y1), read(a[i].x2), read(a[i].y2);
    for (int i = 1; i <= m; ++i)
        p[++cnt] = (Point){a[i].x1, a[i].y1, 0, i}, p[++cnt] = (Point){a[i].x2, a[i].y2, 1, i};
    p[++cnt] = (Point){0, 0, 1, 0}, p[++cnt] = (Point){n, n, 0, m+1};
    sort(p+1, p+cnt+1, cmp_x);
    for (int i = 1; i <= m; ++i)
        len[i] = calc_dis(a[i].x1, a[i].y1, a[i].x2, a[i].y2);
    CDQ(1, cnt);
    printf("%d\n", n + n - ans[m+1]);
    return 0;
}