题解：CF1083E The Fair Nut and Rectangles

斜率优化好题。当笔记了。

注意到这里的矩阵是互不包含，且具有固定端点 (0,0) 并在同一象限，可以考虑按横坐标先排序。

对于这种选点问题，就考虑上一个从哪个矩形转移过来更优。

Tips：横坐标在数组存储里是行，也就是数组里的纵坐标。注意不要混淆。

故令 dp_i 表示选到第 i 个矩形的最大价值，然后转移的话枚举 1\sim i-1，找到最优的一个转移。怎么算价值呢？首先要明确价值（新加入的） W=x_i\times y_i-w_i-X。X 是和上一个矩阵的交。怎么算 X 呢？发现对于按横坐标排序的矩阵两两交可以快速得到，假设上一个从 j 转移，那么有 X=x_j\times y_i。这里读者自行画图理解，不放图了。

故朴素转移有：

整理一下：

这显然是 O(N^2) 的，不可取，考虑优化。注意到 y_i\times(x_i-x_j) 这一项，典型的斜率优化形式。

这里假设 j 比 k 更优。那么有：

整理并移项：

然后就可以用单调队列维护这个凸包，属于类板板题，时间复杂度 O(N)。

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(0), cin.tie(nullptr), cout.tie(nullptr);
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define pre(i, j, k) for(int i = j; i >= k; --i)
#define pb push_back
#define int long long
#define inf 0x3fffffff
#define PII pair<int, int>
#define fi first
#define se second

using namespace std;

const int N = 2e6 + 5;

int n, C, L, l, r, res, h[N];
int dp[N], f[N], q[N << 1]; 

struct Martix {
    int w, x, y;
    bool operator < (const Martix &a) const {return x == a.x ? y < a.y : x < a.x;}
} a[N];

int X(int i) {//这里没有判，严谨点可以加上除数为 0 的情况
    return a[i].x;
}

int Y(int i) {
    return dp[i];
}

double slope(int i, int j) {
    return 1.0 * (Y(j) - Y(i)) / (X(j) - X(i));
} 

void insert(int i) {
    while(l < r && slope(q[r - 1], q[r]) <= slope(q[r - 1], i)) --r;
    q[++r] = i;
}

signed main() {
    FASTIO

    cin >> n;
    rep(i, 1, n) cin >> a[i].x >> a[i].y >> a[i].w;
    sort(a + 1, a + 1 + n);

    l = 0, r = 1, q[++l] = 0;
    rep(i, 1, n) {
        while(l < r && slope(q[l], q[l + 1]) >= a[i].y) ++l;
        dp[i] = max(dp[i], dp[q[l]] + (a[i].x - a[q[l]].x) * a[i].y - a[i].w);
        res = max(res, dp[i]);
//      cout << i << ' ' << q[l] << '\n';
        insert(i);
    }
    cout << res;
    return 0;
}