斜率优化什么的太难写了啊。。。。

题目链接

首先发现，一个三角形高度越高，它新增一格高度的时候增加的面积就越多。那么一个三角形要么就不选，要么就提升到最高。

那么把每个三角形按照右端点排序，然后dp。假设$f(i)$表示决定了第前$i - 1$个三角形的选择情况，且选择了第$i$个三角形的最优收益，那么$f(i) = \max \lbrace f(j) - s(i, j) | 1 \le j < i \rbrace + a_i - cost_i$（$s(i, j)$表示第$i$个三角形和第$j$个三角形重合的面积，$a_i$表示第$i$个三角形的面积，$cost_i$表示把第$i$个三角形提到最高的代价）。

设$l_i$为第$i$个三角形的左端点，$r_i$为第$i$个三角形的右端点，那么如果$r_j < l_i$，那么$s(i, j) = 0$，否则$s(i, j) = \frac{(r_j - l_i)^2}{4}$。注意的$l_j > l_i$的时候，这个式子是不对的，但是可以证明直接这么计算并没有关系。证明如下：

  • 可以发现$f(i)$不会从$l_j > l_i$的三角形转移过来，因为这样三角形$i$包含了三角形$j$，显然是不优的。但是可以把这样的$j$的考虑进来，因为这样算出来的重合面积$>$实际的重合面积。

处理$r_j < l_i$的转移的时候，可以维护一下前缀的$\max$，然后二分出最大的$j$满足$r_j < l_i$。

处理剩下的的转移的时候，可以直接忽视$r_j \ge l_i$的限制，直接把$s(i, j)$视作$\frac{(r_j - l_i)^2}{4}$。因为这样的话$s(i, j) \ge 0$，肯定不比把$s(i, j)$视作$0$优。

然后使用斜率优化就可以解决此题了。

然而由于我太懒了，写了一个$O(n \log^2 n)$的好写做法。

因为可以使用斜率优化，所以这个问题是决策单调的。决策单调如果离线，有一个好写的分治做法。由于这题是在线的，在外面套一层cdq分治即可。

实现的时候为了避免小数，把所有值都乘了$4$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5;
int t, n, c[maxn + 10];

struct data {
	int l, r;
	ll w;

	bool operator < (const data &t) const {
		return r < t.r;
	}
}a[maxn + 10];

bool cmp(int x, int y) {
	return a[x].l < a[y].l;
}

ll suf[maxn + 10], f[maxn + 10], ans;

ll work(int x, int y) {
	return f[x] - 1ll * (a[x].r - a[y].l) * (a[x].r - a[y].l);
}

void calc(int l, int r, int ls, int rs) {
	if (l > r) return;
	int mid = (l + r) >> 1, id = -1;
	ll val = -1e18;
	for (int i = ls; i <= rs; ++i) {
		ll w = work(i, c[mid]);
		if (w > val) {
			val = w; id = i;
		}
	}
	f[c[mid]] = max(f[c[mid]], val);
	calc(l, mid - 1, ls, id);
	calc(mid + 1, r, id, rs);
}

void solve(int l, int r) {
	if (l == r) {
		int ls = 1, rs = l - 1, p = 0;
		while (ls <= rs) {
			int mid = (ls + rs) >> 1;
			if (a[mid].r < a[l].l) p = mid, ls = mid + 1;
			else rs = mid - 1;
		}
		f[l] = max(f[l], suf[p]) + a[l].w;
		suf[l] = max(suf[l - 1], f[l]);
		ans = max(ans, f[l]);
	} else {
		int mid = (l + r) >> 1;
		solve(l, mid);
		for (int i = mid + 1; i <= r; ++i) c[i] = i;
		sort(c + mid + 1, c + r + 1, cmp);
		calc(mid + 1, r, l, mid);
		solve(mid + 1, r);
	}
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n); ans = 0;
		for (int i = 1; i <= n; ++i) {
			int x, y, c; scanf("%d%d%d", &x, &y, &c);
			a[i] = (data){x - y, x + y, 4ll * y * y - 4ll * c * y};
			f[i] = suf[i] = 0;
		}
		sort(a + 1, a + n + 1);
		solve(1, n);
		printf("%lld.%02lld\n", ans / 4, ans % 4 * 25);
	}
}