\(\text{Code}\)
#include <bits/stdc++.h>
#define IN inline
#define eb emplace_back
using namespace std;
template<typename Tp>
IN void read(Tp &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); f |= (ch == '-'), ch = getchar());
for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());
if (f) x = ~x + 1;
}
typedef long long LL;
const int N = 2e5 + 5, M = 1e6 + 5;
const LL INF = 1e18;
struct point{int x, y;}a[N];
int lis[N], n, m;
LL f[N], g[N];
vector<int> G[N];
IN LL calc(int x1, int y1, int x0, int y0){return (LL)(x1 - x0) * (y1 - y0);}
struct SegmentTree {
#define ls (p << 1)
#define rs (ls | 1)
vector<int> Q[N << 2];
void build(int p, int l, int r) {
Q[p].clear(); if (l == r) return;
int mid = l + r >> 1; build(ls, l, mid), build(rs, mid + 1, r);
}
void insert(int p, int l, int r, int x, int y, int z) {
if (x > r || y < l) return;
if (x <= l && r <= y) return Q[p].eb(z), void();
int mid = l + r >> 1;
insert(ls, l, mid, x, y, z), insert(rs, mid + 1, r, x, y, z);
}
void solve(int p, int l, int r, int L, int R, int cur) {
if (r < l || R < L) return;
int mid = l + r >> 1, bst = 0;
for(int i = L; i <= R; i++) {
LL s = f[G[cur - 1][i]] + calc(a[Q[p][mid]].x, a[Q[p][mid]].y, a[G[cur - 1][i]].x, a[G[cur - 1][i]].y);
if (g[Q[p][mid]] > s) g[Q[p][mid]] = s, bst = i;
}
solve(p, l, mid - 1, bst, R, cur), solve(p, mid + 1, r, L, bst, cur);
}
void dfs(int p, int l, int r, int cur) {
for(auto v : Q[p]) g[v] = INF;
solve(p, 0, Q[p].size() - 1, l, r, cur);
for(auto v : Q[p]) f[v] = min(f[v], g[v]);
if (l == r) return; int mid = l + r >> 1;
dfs(ls, l, mid, cur), dfs(rs, mid + 1, r, cur);
}
}T;
struct BIT {
int c[M];
IN int lowbit(int x){return x & -x;}
IN void add(int x, int v){for(; x <= m; x += lowbit(x)) c[x] = max(c[x], v);}
IN int query(int x){int s = 0; for(; x; x -= lowbit(x)) s = max(c[x], s); return s;}
}bit;
IN void solve() {
for(int i = 1; i <= n; i++) lis[i] = bit.query(a[i].y) + 1, bit.add(a[i].y, lis[i]);
for(int i = 0; i <= n; i++) G[lis[i]].eb(i);
for(int i = 1; i <= n; i++) sort(G[i].begin(), G[i].end(), [](int x, int y){return a[x].x < a[y].x;});
for(int i = 1; i <= n; i++) f[i] = INF;
for(int i = 1; i <= n && G[i].size(); i++) {
T.build(1, 0, G[i - 1].size() - 1);
int p = 0, q = 0;
for(auto j : G[i]) {
while (p < G[i - 1].size() && a[G[i - 1][p]].x <= a[j].x) ++p;
while (q < G[i - 1].size() && a[G[i - 1][q]].y > a[j].y) ++q;
T.insert(1, 0, G[i - 1].size() - 1, q, p - 1, j);
}
T.dfs(1, 0, G[i - 1].size() - 1, i);
}
}
int main() {
freopen("mowing.in", "r", stdin);
freopen("mowing.out", "w", stdout);
read(n), read(m);
for(int i = 1; i <= n; i++) read(a[i].x), read(a[i].y);
sort(a + 1, a + n + 1, [](point a, point b){return a.x < b.x;});
solve();
int mx = 0;
for(int i = 1; i <= n; i++) mx = max(mx, lis[i]);
LL ans = INF;
for(int i = 1; i <= n; i++) if (lis[i] == mx) ans = min(ans, f[i] + calc(m, m, a[i].x, a[i].y));
printf("%lld\n", ans);
}
标签:LG,ch,Mischief,cur,int,void,mid,P5244,return
From: https://www.cnblogs.com/leiyuanze/p/17149526.html