8.20T2 黑色大桥（函数处理、李超线段树）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141362275

http://cplusoj.com/d/senior/p/NODSX2301B

有一个显然的dp： dpj=max⁡i≤j(dpi−1+Fi(j−(i−1)))dp_j=\max_{i\le j}(dp_{i-1}+F_i(j-(i-1)))

答案是 dpndp_n ，复杂度 O(n2)O(n^2) 。

考虑 FiF_i ：

如果只有前面的一次函数，我们直接李超就行。但是后面还有两个二次函数，怎么处理呢？

发现对于 (r−l)2(r-l)^2 ，可以 r2−2rl+l2r^2-2rl+l^2 ，我们成功把二次项提到了外面，里面就可以愉快李超了。

整理可以得到三段函数的一次函数表达式：

  1. f1(r)=−kr+(kl+b)f_1(r)=-k r + (kl + b)

  2. f2(r)=2(a+l)r+(−l2−2al−k(a−d)+b+d2−a2)−r2f_2(r)=2(a + l) r + (- l^2 - 2 a l- k (a - d) + b + d^2 - a^2)-r^2

  3. f3(r)=2(l+a+d)r+(Z(l)+2(a+d)l−k(a−d)+b+(a+d)2)+r2f_3(r)=2 (l + a + d) r + ( Z(l) + 2 (a + d) l- k (a - d) + b + (a + d)^2)+r^2

拿3棵李超维护即可。

但有个问题，我们如果区间加一次函数，复杂度容易炸，我们考虑是否能全局加。

对于第1、2段区间是容易的，它们不会对最大值产生影响：

在这里插入图片描述

但是第3段区间会有问题，我们的处理方式也很简单，我们留到 a+da+d 的时候再加入第三段区间就行。

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 1000010
struct node {
	int a, b, d, k; 
}a[N];
int n, m, i, j, k, T;
vector<int>E[N]; 

namespace Sol1 {
	int f[N]; 
	struct Line {
		int k, b; 
		void set() { b = -1e9; k = 0; }
		int f(int x) { return k * x + b; }
	}s[N << 3];
	int ls[N << 3], rs[N << 3], tot; 
	struct Segment_tree {
//		int tot = 0;  
		void add(int &u, int l, int r, Line t) {
			if(!u) u = ++tot, s[u].set();  
			debug("Add(%lld %lld)\n", t.k, t.b); 
			int mid = (l + r) >> 1; 
			if(t.f(mid) > s[u].f(mid)) swap(s[u], t); 
			if(t.f(l) > s[u].f(l)) add(ls[u], l, mid, t); 
			if(t.f(r) > s[u].f(r)) add(rs[u], mid + 1, r, t); 
		}
		int cha(int u, int l, int r, int x) {
			if(!u) return -1e9; 
			int mid = (l + r) >> 1, ans = s[u].f(x); 
			if(x <= mid) ans = max(ans, cha(ls[u], l, mid, x)); 
			else ans = max(ans, cha(rs[u], mid + 1, r, x)); 
			return ans; 
		}
	}Seg1, Seg2, Seg3;
	int rt1, rt2, rt3; 
	node bilibili(int i) { return a[i]; }
	void add(int l, int op = 0) {
		node y = bilibili(l + 1); int a = y.a, b = y.b, k = y.k, d = y.d; 
		debug("(%lld %lld %lld %lld)\n", k, a, b, d); 
		if(!op) {
			Seg1.add(rt1, 1, n, {-k, k * l + b + f[l]}); 
			Seg2.add(rt2, 1, n, {2 * (a + l), - Z(l) - 2 * a * l- k * (a - d) + b + Z(d) - Z(a) + f[l]}); 
		}
		else {
			Seg3.add(rt3, 1, n, {- 2 * (l + a + d),  Z(l) + 2 * (a + d) * l- k * (a - d) + b + Z(a + d) + f[l]}); 
		}
	}
	int F(node y, int l, int r) {
		int x = r - l; 
		int a = y.a, b = y.b, k = y.k, d = y.d; 
		if(x <= a - d) return  (-k) * r + (k * l + b); 
		if(x < a + d) 
			return (- Z(r)) 
				+ (2 * a + 2 * l) * r + (- Z(l) - 2 * a * l- k * (a - d) + b + Z(d) - Z(a)); 
		return Z(r)
				- 2 * (l + a + d) * r + ( Z(l) + 2 * (a + d) * l- k * (a - d) + b + Z(a + d)); 
	}
	int cha(int r) {
		int s1 = Seg1.cha(rt1, 1, n, r); 
		int s2 = Seg2.cha(rt2, 1, n, r) - Z(r); 
		int s3 = Seg3.cha(rt3, 1, n, r) + Z(r); 
		debug("# (%lld %lld %lld)\n", s1, s2, s3); 
		return max({s1, s2, s3}); 
	}
	void main() {
		memset(f, 0x80, sizeof(f)); 
		f[0] = 0; 
		for(i = 1; i <= n; ++i) {
//			add(i - 1); 
//			for(auto t : E[i]) add(t - 1, 1); 
//			f[i] = cha(i); 
//			if((k = a[i].a + a[i].d) <= n) E[k].pb(i); 
			
			for(j = 1; j <= i; ++j) {
				f[i] = max(f[i], f[j - 1] + F(a[j], j - 1, i)); 
			}
			debug("> %lld\n", f[i]); 
		}
		printf("%lld", f[n]); 
	}
}

namespace Sol2 {
	int f[N]; //, g[N]; 
	void main() {
//		g[n + 1] = Z(n + 1); 
		for(i = n; i >= 1; --i) {
//			for(j = i + 1; j <= n; ++j) {
//				f[i] = max(f[i], f[j] + Z(n) - Z(n - (j - i))); 
//			}
			f[1] += a[i].b + n + n - 1; 
//			f[i] += 2 * n * i
		}
		printf("%lld", f[1]); 
	}
}

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n = read(); //int flg1 = 1; 
	for(i = 1; i <= n; ++i) {
		a[i].k = read(); a[i].a = read(); 
		a[i].b = read(); a[i].d = read(); 
//		if(a[i].a != n || a[i].d != n) flg1 = 0; 
	}
//	if(n <= 5000) 
	return Sol1 :: main(), 0; 
//	if(flg1) return Sol2 :: main(), 0; 
	return 0;
}