Solution. LG5244 [USACO19FEB] Mowing Mischief P

Description

在 $T\times T$ 的正方形网格上（左下角格点坐标为 $(0,0)$，右上角为 $(T,T)$，共 $(T+1)^2$ 个格点），给定 $n$ 个关键点，保证横纵坐标都互不相同。要求选出尽可能多的关键点，使其按横坐标从小到大排序后，纵坐标也单调增。在此基础上，最小化以相邻两点为对角线的长方形面积总和。

$1\le n\le 2\times 10^5,1\le T\le 10^6$

Solution

首先要做一个二维 LIS，按横坐标排序后用树状数组维护转移即可。这部分是平凡的。

按照以每个点结尾的最长 LIS 长度分层，第二问的转移都应当发生在相邻层之间，这样我们就有了一个 $O(n^2)$ 的做法。

接下来考虑优化。由于涉及到正方形面积，很容易让人想到决策单调性。

对于同层的点，如果我们将其按横坐标从小到大排序，纵坐标一定单调减。考虑第 $t-1$ 层的两点 $A(x_a,y_a),B(x_b,y_b),x_a<x_b,y_a>y_b$ 和第 $t$ 层的两点 $C(x_c,y_c),D(x_d,y_d),x_c<x_d,y_c>y_d$，这里假设 $A,B$ 均能转移到 $C,D$。则我们考虑
$$
\begin{array}{}
f(A, C)+f(B, D)=(x_c-x_a)(y_c-y_a)+(x_d-x_b)(y_d-y_b)\\
f(A, D)+f(B, C)=(x_d-x_a)(y_d-y_a)+(x_c-x_b)(y_c-y_b)
\end{array}
$$
两式联立化简后，问题转化为判断 $(x_a-x_b)(y_c-y_d)+(x_c-x_d)(y_a-y_b)$ 的正负，于是我们得到
$$
f(A,C)+f(B,D)>f(A,D)+f(B,C)
$$
中间的计算过程不多赘述，也很推荐通过画图来理解这一不等式，更加直观，只不过用电脑画个好看的图放题解里太麻烦 。

这是反向的四边形不等式，故本题有递减的决策单调性（link），常规的做法是用二分栈来维护决策点，或者由于分层转移的特性，我们也可以使用分治，但本题中由于每个决策点只能向一个区间进行转移，直接应用这两种方法都行不通。

对于二分栈来说，我们可能会想在到达某个决策点作用域左端点时将其插入单调栈，但问题在于，此时这个决策点可能是劣的，无法替代栈顶，但这并不意味着这个决策点就可以被舍弃，因为其可能拥有比栈顶更大的作用域，可以在离开栈顶作用域后入栈，如果对一个决策点多次尝试入栈，时间复杂度就难以保证了。

对于分治也存在类似的问题，我们无法直接将决策点一分为二，分配给左右两侧的 dp 数组。

于是，我们不得不付出一个 $\log$ 的代价来解决这一问题。考虑使用和线段树分治类似的方法，将每个决策点放到作用域内的 $\log$ 个线段树结点上，然后遍历线段树，对于每个结点，现在每个决策点的作用域都覆盖当前结点对应的整个区间，所以直接使用二分栈或分治进行转移即可。总复杂度 $O(n\log^2 n)$。

每个线段树结点都应视作一个子问题，所以应在 dp 值算出后再进行合并，否则可能会出现在另一个结点上做出的决策优于当前结点上的所有决策点，导致当前结点无法转移的问题。

值得一提的是，我们需要线段树分治的本质原因在于决策单调性和可转移区间的移动方向不一致，如果移动方向一致的话，例如本题如果改为最大化面积，决策单调性变为递增，则直接使用二分队列或分治都是没有问题的。

Code

namespace Main{
    const int N = 200005;
    const int V = 1000005;
    int n, t, f[N];
    pair<int, int> flower[N];
    vector<pair<int, int>> layer[N];
    vector<ll> dp[N];
    struct bit{
        int t[V];
        inline int lowbit(int x) { return x & -x; }
        void modify(int x, int k) { for(; x < V; x += lowbit(x)) t[x] = max(t[x], k); }
        int query(int x) { int res = 0; for(; x; x -= lowbit(x)) res = max(res, t[x]); return res; }
    }tree;
    struct segtree{
        struct segtree_node{
            int l, r;
            vector<int> trans;
        }t[N<<2];
        #define ls p<<1
        #define rs p<<1|1
        void build(int p, int l, int r){
            t[p].l = l, t[p].r = r, t[p].trans.clear();
            if(l == r) return;
            int mid = l + r >> 1;
            build(ls, l, mid), build(rs, mid + 1, r);
        }
        void add(int p, int l, int r, int k){
            if(t[p].l >= l && t[p].r <= r){
                t[p].trans.push_back(k);
                return;
            }
            int mid = t[p].l + t[p].r >> 1;
            if(mid >= l) add(ls, l, r, k);
            if(mid < r) add(rs, l, r, k);
        }
        void calc(int d, vector<int> &sp, int l, int r, int sl, int sr){
            if(l > r) return;
            int mid = l + r >> 1, s = -1;
            ll val = 1e18;
            for(int i = sl; i <= sr; i++){
                ll tmp = dp[d - 1][sp[i]] + 1ll * (layer[d][mid].first - layer[d - 1][sp[i]].first) * (layer[d][mid].second - layer[d - 1][sp[i]].second);
                if(tmp < val) { val = tmp; s = i; }
            }
            dp[d][mid] = min(dp[d][mid], val);
            calc(d, sp, l, mid - 1, s, sr), calc(d, sp, mid + 1, r, sl, s);
        }
        void solve(int p, int d){
            if(!t[p].trans.empty()) calc(d, t[p].trans, t[p].l, t[p].r, 0, t[p].trans.size() - 1);
            if(t[p].l == t[p].r) return;
            solve(ls, d), solve(rs, d);
        }
        #undef ls
        #undef rs
    }t2;
    void Main(){
        input(n, t);
        for(int i = 0; i < n; i++) input(flower[i].first, flower[i].second);
        sort(flower, flower + n);
        int mx = 0;
        for(int i = 0; i < n; i++){
            f[i] = tree.query(flower[i].second) + 1;
            tree.modify(flower[i].second, f[i]);
            layer[f[i]].push_back(flower[i]);
            mx = max(mx, f[i]);
        }
        layer[0].emplace_back(0, 0), layer[++mx].emplace_back(t, t);
        dp[0] = {0};
        for(int i = 1; i <= mx; i++){
            t2.build(1, 0, layer[i].size() - 1);
            dp[i].resize(layer[i].size(), 1e18);
            for(int j = 0; j < layer[i - 1].size(); j++){
                int l = lower_bound(layer[i].begin(), layer[i].end(), layer[i - 1][j]) - layer[i].begin();
                int r = lower_bound(layer[i].begin(), layer[i].end(), layer[i - 1][j], [](pair<int, int> a, pair<int, int> b){
                    return a.second > b.second;
                }) - layer[i].begin() - 1;
                if(l <= r) t2.add(1, l, r, j);
            }
            t2.solve(1, i);
        }
        write(dp[mx][0]);
        return;
    }
} // namespace Main

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。