Springboards (USACO Gold 2020 January)

这是一个难度比较大的二维数点 + 区间查询 + DP的题目，步骤比较多，思维有难度，实现也有一定困难。

首先，比较容易看到每个springboard可以看成是节省 $x_2-x_1+y_2-y_1$ 个step，所以题意就是求最优路径下，最多能够节省多少个step。可以看出来，这个是由走了哪些board决定的，和其它路怎么走没有关系。

所以朴素的解法，是把springboard之间可以互相到达的图建出来（是一个DAG），然后简单DP求路径上节点价值和的最大值就行。但这个只能过15个中的5个测试点，因为这个复杂度是 $\mathcal{O}(P^2)$ ，而 $P=10^5$ 。

一条出路是我们看到这些边中间有很多冗余，一些路径肯定是不优的，比如 $a \rightarrow b \rightarrow c$ 存在的时候， $a \rightarrow c$ 这条边就不需要存在。这边往下走，有人做出了解答。

我们看另外一个角度，建边的方法不行，主要原因是没有用到boards之间的空间关系。仔细观察，我们会发现DP状态转移所依赖的状态，在平面上是在一个矩形区域中，如下图所示：

每条斜线都是一个左下到右上的spring board，蓝色点是DP正在处理的board的起点。红色的board是我们要考虑的前续状态，而DP状态转移非常简单，就是取这些线段的DP最大值。有了这个图之后，我们就可以想到，这个最大值是可以一次性求出来的，就是一个二维数点+区间查询最大值的问题。

二维数点：把线段按左上角坐标先x再y排序，然后随着DP过程逐渐加入到线段树中，存储 $\text{tree}[y]=\text{dp}[i]$ 。
区间查询：通过线段树查询 $[0,y]$ 内的dp最大值，再加当前线段的长度，就是新的DP值。

有以下需要注意的细节：

坐标需要首先离散化，这样才能使用 $y$ 作为线段树的下标。
DP计算出来是不能立即加到线段树中的，因为加入线段树的标准是右上角坐标，而DP计算时是左下角坐标。这个时间差的处理办法，就是可以有按左下角和右下角坐标排序的两个board列表，DP按左下角坐标顺序进行，加入线段树按右上角坐标进行。容易看到一个board加入线段树时，DP值肯定已经算好了。
线段树大小是离散化之后y坐标的范围，也就是 $2P$ 。

程序实现有不少细节，见下方代码。最终复杂度是 $\mathcal{O}(P \log P)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, p;
pair<pi, pi> bs[100005];    // sorted by x1,y1
int idx2[100005];           // sorted by x2,y2
int len[100005];
#define f first
#define s second
int ans;
int dp[100005];
int tree[400005];           // y -> dp
int sn;                     // segment tree size
 
void set(int k, int x) {  // 更新元素k为x
    k += sn;
    tree[k] = x;
    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = max(tree[2*k],tree[2*k+1]);
    }
}
int rmax(int a, int b) { // 返回区间[a,b]的最大值
    a += sn; b += sn;
    int ma = 0;
    while (a <= b) {
        if (a%2 == 1) ma = max(ma, tree[a++]); // 左边界如果是右子树，则合并进结果，并右移
        if (b%2 == 0) ma = max(ma, tree[b--]); // 右边界如果是左子树，则合并进结果，然后左移
        a /= 2; b /= 2;
    }
    return ma;
}
 
bool cmp(int i1, int i2) {      // sort index by x2 then y2
    return    bs[i1].s.f == bs[i2].s.f && bs[i1].s.s < bs[i2].s.s 
           || bs[i1].s.f < bs[i2].s.f;
}
 
int length(pair<pi,pi> a) {
    return a.s.f - a.f.f + a.s.s - a.f.s;
}
 
void discretize() {
    vector<int> xs, ys;
    for (int i = 0; i < p; i++) {
        xs.push_back(bs[i].f.f);
        xs.push_back(bs[i].s.f);
        ys.push_back(bs[i].f.s);
        ys.push_back(bs[i].s.s);
    }
    sort(xs.begin(), xs.end()); sort(ys.begin(), ys.end());
    xs.resize(unique(xs.begin(), xs.end())-xs.begin());
    ys.resize(unique(ys.begin(), ys.end())-ys.begin());
    for (int i = 0; i < p; i++) {
        bs[i].f.f = lower_bound(xs.begin(),xs.end(),bs[i].f.f)-xs.begin();
        bs[i].s.f = lower_bound(xs.begin(),xs.end(),bs[i].s.f)-xs.begin();
        bs[i].f.s = lower_bound(ys.begin(),ys.end(),bs[i].f.s)-ys.begin();
        bs[i].s.s = lower_bound(ys.begin(),ys.end(),bs[i].s.s)-ys.begin();
    }
}
 
int main() {
    scanf("%d %d", &n, &p);
    for (int i = 0; i < p; i++) {
        scanf("%d %d %d %d", &bs[i].f.f, &bs[i].f.s, &bs[i].s.f, &bs[i].s.s);
        idx2[i] = i;
    }
    sort(bs, bs+p);             // sort by x1 then y1
    sort(idx2, idx2+p, cmp);    // sort by x2 then y2
    for (int i = 0; i < p; i++)
        len[i] = length(bs[i]);
    discretize();
    SN = p*2;
 
    int j = 0;                  // index into idx2[]
    for (int i = 0; i < p; i++)  {
        int x = bs[i].f.f, y = bs[i].f.s;
        // add all springboards with x2,y2 <= x,y to segtree
        for (; j < p && bs[idx2[j]].s.f < x || bs[idx2[j]].s.f == x && bs[idx2[j]].s.s < y; j++) {
            int Y = bs[idx2[j]].s.s;
            if (rmax(Y,Y) < dp[idx2[j]])    // only set segtree when current number is larger
                set(Y, dp[idx2[j]]);
        }
        dp[i] = rmax(0, y) + len[i];
        // assert(dp[i] >= 0);
        ans = max(ans, dp[i]);
    }
    printf("%d", 2*n-ans);
    return 0;
}