题解：P17741 [ICPC 2019 Xuzhou R] K-rectangle

· · 题解

最后两分钟场切了，应当为我颁发顽强拼搏奖。

首先所有点按照 x 坐标排序，x 坐标相同的保留较大的。

注意到矩形的底边都在 x 轴上且互相不相交，不难想到一个 dp 做法，每次枚举最后一个矩形覆盖了那一个区间的点。设 f_i 表示覆盖了 1\sim i 的最小代价，有转移式：

f_i=\min_{1\le j\le i}\left\{f_{j-1} + \left(\max_{j\le t\le i}y_t\right)\times (x_i - x_j+k)\right\}

拆开来看看：

f_i=\min_{1\le j\le i}\left\{\left(\max_{j\le t\le i}y_t\right)\times x_i+\left(f_{j-1} - (x_j-k)\times \left(\max_{j\le t\le i}y_t\right)\right) \right\}

又有 \max 又是相乘形式，看起来非常的唬人，但实际上可以用一些李超树科技直接做到 O(n\log V)。

首先设 v_i(j) 表示 i\sim j 的 y 的最大值，不难发现，一些后缀最大值的位置会把 v_i(x) 划分为 O(n) 段，每一段内转移式里的那个 \max 值都是相同的。

所以对于每一段里面，只需要维护下面式子的最大值：

\left(f_{j-1} - (x_j-k)\times \left(\max_{j\le t\le i}y_t\right)\right)

假设某一个段里的最大 y 值为 h。这一段内上面式子的最大值为 C，还需要对于所有段的信息，查询：

f_i=\min_{1\le j\le i}\left\{x_ih+C\right\}

外部再用一个李超树维护所有段的信息即可。

注意到我们 i\to i+1 时，需要更新 v_i(j) 的段划分，所以可能要在外部李超树删掉一些直线。但是注意到我们更新的是一个后缀，直接撤销，可以做到 O(n\log V)。

注意到当我们插入一个新的段时，他可能和前面若干段合并，为了合并后能快速求出这一段内的最优决策，需要每一段上维护李超树，合并段的时候做李超树合并。

总而言之复杂度为 O(n\log V)，空间复杂度为 O(n\log V)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e5 + 10;
const int M = N * 30;
const int V = 1e6;
const int inf = 1e18;
int n, k, f[N], top, stk[N], rec[N];
struct node { int x, y; } p[N];
struct seg { int l, r, v, u; } w[N];
struct LCT1 {
    int k[N], b[N], rt[N], cnt;
    int mx[M], lc[M], rc[M];
    int val(int id, int x) {
        return k[id] * x + b[id];
    }
    void upd(int &p, int l, int r, int x) {
        if (!p) p = ++cnt;
        if (!mx[p]) {mx[p] = x; return;}
        int mid = (l + r) >> 1;
        if (val(mx[p], mid) > val(x, mid)) swap(mx[p], x);
        if (val(mx[p], l) > val(x, l)) upd(lc[p], l, mid, x);
        if (val(mx[p], r) > val(x, r)) upd(rc[p], mid + 1, r, x);
        return;
    }
    int ask(int p, int l, int r, int x) {
        if (!p) return inf;
        int tmp = val(mx[p], x), mid = (l + r) >> 1;
        if (l == r) return tmp;
        if (x <= mid) tmp = min(tmp, ask(lc[p], l, mid, x));
        if (x > mid) tmp = min(tmp, ask(rc[p], mid + 1, r, x));
        return tmp;
    }
    int unite(int p, int q, int l, int r) {
        if (!p || !q) return p + q;
        if (mx[q]) upd(p, l, r, mx[q]);
        if (l == r) return p;
        int mid = (l + r) >> 1;
        lc[p] = unite(lc[p], lc[q], l, mid);
        rc[p] = unite(rc[p], rc[q], mid + 1, r);
        return p;
    }
    void merge(int p, int q) {
        rt[p] = unite(rt[p], rt[q], 1, V);
    }
    void ins(int id, int _k, int _b) {
        k[id] = _k, b[id] = _b;
        upd(rt[id], 1, V, id);
    }
    int qry(int id, int x) {
        return ask(rt[id], 1, V, x);
    }
} T;
struct LCT2 {
    int top, *pos[M], vaw[M];
    int k[N], b[N], rt, cnt;
    int lc[M], rc[M], mx[M]; 
    void push(int &x) {
        ++top, pos[top] = &x, vaw[top] = x;
        return;
    }
    void pop() {
        *pos[top] = vaw[top];
        return;
    }
    int val(int id, int x) {
        return k[id] * x + b[id];
    }
    void upd(int &p, int l, int r, int x) {
        if (!p) push(p), p = ++cnt;
        if (!mx[p]) {push(mx[p]), mx[p] = x; return;}
        int mid = (l + r) >> 1;
        if (val(mx[p], mid) > val(x, mid)) {
            push(mx[p]);
            swap(mx[p], x);
        }
        if (val(mx[p], l) > val(x, l)) upd(lc[p], l, mid, x);
        if (val(mx[p], r) > val(x, r)) upd(rc[p], mid + 1, r, x);
        return;
    }
    void ins(int id, int _k, int _b) {
        k[id] = _k, b[id] = _b;
        upd(rt, -V, V, id);
    }
    int ask(int p, int l, int r, int x) {
        if (!p) return inf;
        int tmp = val(mx[p], x), mid = (l + r) >> 1;
        if (l == r) return tmp;
        if (x <= mid) tmp = min(tmp, ask(lc[p], l, mid, x));
        if (x > mid) tmp = min(tmp, ask(rc[p], mid + 1, r, x));
        return tmp;
    }
    int qry(int x) {
        return ask(rt, -V, V, x);
    }
    void pop(int rec) {
        while (top > rec) pop(), top--;
    }
} tr;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].x >> p[i].y;
    }
    sort(p + 1, p + 1 + n, [&](node u, node v) {
        return u.x == v.x ? u.y < v.y : u.x < v.x;
    });
    int _n = n; n = 0; p[0].x = -1e9;
    for (int i = 1; i <= _n; i++) {
        if (p[i].x == p[n].x) {
            p[n] = p[i];
        } else {
            p[++n] = p[i];
        }
    }
    for (int i = 1; i <= n; i++) {
        T.ins(i, -p[i].x, f[i - 1]);
        while (top && p[i].y > p[stk[top]].y) {
            T.merge(i, stk[top]);
            tr.pop(rec[stk[top]]);
            top -= 1; 
        }
        rec[i] = tr.top; stk[++top] = i;
        tr.ins(i, p[i].y, T.qry(i, p[i].y) + p[i].y * k);
        f[i] = tr.qry(p[i].x);
    }
    cout << f[n] << '\n';
    return 0;

}

如有错误，请指出。