李超线段树

丝之歌压轴版，李超线段树模板及应用

李超线段树牛逼
李超线段树用于一系列平面上的一次函数，维护对于每一个 \(\texttt{x}\) 最大或最小的 \(\texttt{y}\) 值。

模板题

这道模板题非常毒瘤，相比应用李超线段树的时候实现的东西要多的多：

• 一是给的是横纵坐标，所以斜率要用 \(\texttt{double}\) 类型，整个题的就都要考虑精度问题，非常麻烦。
• 二是输出的是线段编号，导致 \(\texttt{query}\) 函数要把值和标号一起传，同时因为要求输出编号小的，比较的时候也要多比较一个参数。
• 三是给的是线段而不是直线，导致还要多写一个函数去判断哪些区间被线段完全覆盖。
• 四是数据强制在线，更麻烦了。

所以第一次做李超线段树可以考虑做P4254，是一道更正常的模板题。

做法

先考虑如何在插入一条新的线段的时候维护答案。
显然查询完全被线段覆盖的区间是用普通线段树区间查询的方法容易实现的。

void modify(int x, int l, int r, int x0, int x1, int id){
	if(r < x0 || l > x1) return; 
	if(l >= x0 && r <= x1) update(x, l, r, id);
	else {
		int mid = (l + r) >> 1;
		modify(2 * x, l, mid, x0, x1, id);
		modify(2 * x + 1, mid + 1, r, x0, x1, id);
	}
}

然后是李超线段树的重点，当一条线段完全覆盖某个区间时，怎么用这条线段修改这个区间的答案。
设原本这个区间的答案直线为 \(\texttt{tg[x]}\)，要用于修改的直线为 \(\texttt{f}\)。
首先我们强制规定在区间中点 \(\texttt{mid}\) 处的值 \(\texttt{tg[x]}\) 大于 \(\texttt{f}\)，如果不是就 \(\texttt{swap}\)。
然后查看在 \(\texttt{l}\) 和 \(\texttt{r}\) 处两条直线的大小。因为强制规定了 \(\texttt{mid}\) 处 \(\texttt{f}\) 更小，如果哪边 \(\texttt{f}\) 更大，说明两条线在这边一定有交点， \(\texttt{f}\) 在这一边就有成为答案的可能，就递归去修改这边。因为两边至多有一边会被继续递归修改（否则 \(\texttt{f}\) 肯定会在第一步被 swap），复杂度为\(O(logn)\)。
因为我不会画图，光说肯定比较抽象，推荐看这篇博客：https://chuna2.787528.xyz/cold-jelly/p/18891748

int cmp(double a, double b){
	if(a - b > eps) return 1;
	else if(b - a > eps) return -1;
	else return 0;
}
void makeline(int x0, int y0, int x1, int y1){
	tot++;
	if(x0 == x1){
		l[tot].k = 0;
		l[tot].b = max(y0, y1);
	}
	else {
		l[tot].k = (double)(y1 - y0) / (x1 - x0);
		l[tot].b = y0 - l[tot].k * x0;
	}
}
double yz(int x, int id){
	return l[id].k * x + l[id].b;
}
void update(int x, int l, int r, int id){
	int &v = tg[x];
	int mid = (l + r) >> 1;
	int cp = cmp(yz(mid, id), yz(mid, v));
	if((cp == 1) || (!cp && id < v)) swap(id, v);
	int cp1 = cmp(yz(l, id), yz(l, v));
	int cp2 = cmp(yz(r, id), yz(r, v));
	if((cp1 == 1) || (!cp1 && id < v)) update(2 * x, l, mid, id);
	if((cp2 == 1) || (!cp2 && id < v)) update(2 * x + 1, mid + 1, r, id);
}

最后的 \(\texttt{query}\) 函数就很简单了，直接沿着有要查询的点 \(\texttt{k}\) 的区间跳 \(logn\) 次记录路径上的最大值即可。

out query(int x, int l, int r, int k){
	if(l > k || r < k) return out(0, 0);
	double ans = yz(k, tg[x]);
	if(l == r) return out(ans, tg[x]);
	int mid = (l + r) >> 1;
	return max(out(ans, tg[x]), max(query(2 * x, l, mid, k), query(2 * x + 1, mid + 1, r, k)));
}

奉上完整代码：
AC记录

还有简单的板子P4254的代码，这个的代码更简洁：
AC记录

应用

李超线段树常用于斜率优化，即将dp式子中需要动态维护的一个区间最值的式子化成一个一次函数，这样就可以用李超线段树来维护，\(O(logn)\) 的时间就能找到最值，从而优化时间复杂度。

例题1：P4655

用 \(s_i\) 表示 \(w_i\) 的前缀和，那么可以列出一个 \(n^2\) 的dp式子：

\[dp[i] = \min_{j<i}\{dp[j] + (h_i - h_j)^2 + s_{i - 1} - s_j\} \]

化简一下：

\[dp[i] = \min_{j<i}\{dp[j] + h_i^2 - 2 \times h_i \times h_j + h_j^2 + s_{i - 1} - s_j\} \]

把固定的给提出来可以得到：

\[dp[i] = h_i^2 + s_{i-1} + \min_{j<i}\{-2h_j \times h_i + (h_j^2 - s_j + dp[j]) \} \]

注意到 \(\texttt{min}\) 里面是以 \(-2h_j\) 为 \(\texttt{k}\)，\(h_j^2 - s_j + dp[j]\) 为 \(\texttt{b}\)的一次函数，所以我们可以用李超线段树维护前面所有的一次函数，求 \(dp[i]\)时直接求 \(x = h_i\) 时一次函数的最小值。复杂度优化到 \(O(nlogn)\)
代码较短直接贴上：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
int n, tot, h[N], w[N], sum[N], dp[N], tg[M * 4];
struct line{
	int k, b;
	line(int x = 0, int y = 0){
		k = x; b = y;
	}
}l[N];
int f(int x, int id){
	return l[id].k * x + l[id].b;
}
void update(int x, int l, int r, int id){
	int &v = tg[x];
	int mid = (l + r) >> 1;
	if(f(mid, id) < f(mid, v)) swap(v, id);
	if(f(l, id) < f(l, v)) update(2 * x, l, mid, id);
	if(f(r, id) < f(r, v)) update(2 * x + 1, mid + 1, r, id);	
}
int query(int x, int l, int r, int k){
	if(r < k || l > k) return 1e18;
	int ans = f(k, tg[x]);
	if(l == r) return ans; 
	int mid = (l + r) >> 1;
	return min(ans, min(query(2 * x, l, mid, k), query(2 * x + 1, mid + 1, r, k)));
}
signed main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> h[i];	
	}
	for(int i = 1; i <= n; i++){
		cin >> w[i];
		sum[i] = sum[i - 1] + w[i];
	}
	l[0].b = 1e18;
	l[++tot] = line(-2 * h[1], dp[1] + h[1] * h[1] - sum[1]);
	update(1, 0, M, tot);
	for(int i = 2; i <= n; i++){
		dp[i] = (h[i] * h[i] + sum[i - 1]) + query(1, 0, M, h[i]);
		l[++tot] = line(-2 * h[i], dp[i] + h[i] * h[i] - sum[i]);
		update(1, 0, M, tot);
	}
	cout << dp[n];
	return 0；
}

例题二：P3195

这道题式子化简还是相当麻烦的，难度是大于上一道题。
设长度 \(c_i\) 的前缀和为 \(s_i\)，那么长度 \(x = i - j - 1 + s_i - s_j\)，代入 \(x\)，得到：

\[dp[i] = \min_{j<i}\{dp[j] + (i - j + s_i - s_j - L - 1)^2 \} \]

设 \(t_i = s_i + i\)，\(b = L + 1\)，那么：

\[dp[i] = \min_{j<i}\{dp[j] + (t_i - t_j - b)^2 \} \]

展开平方：

\[dp[i] = \min_{j<i}\{t_i^2 - 2(t_j + b)t_i + (t_j + b)^2 \} \]

提出 \(t_i^2\)：

\[dp[i] = t_i^2 + \min_{j<i}\{-2(t_j + b)t_i + (t_j + b)^2 \} \]

观察到 \(\texttt{min}\) 内为一次函数，用李超线段树维护，每次查询 \(x=t_i\) 的最小值。
另外注意到前缀和的值域较大，所以需要离散化处理。
代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 5;
int n, L, c[N], len, tot, sum[N], t[N], a[N], dp[N], tg[4 * N];
struct line{
	int k, b;
	line(int x = 0, int y = 0){
		k = x; b = y;
	}
}l[N];
int g(int x){
	return lower_bound(a + 1, a + len + 1, x) - a;
}
int f(int x, int id){
	return l[id].k * x + l[id].b;
}
void update(int x, int l, int r, int id){
	int &v = tg[x];
	int mid = (l + r) >> 1;
	if(f(a[mid], id) < f(a[mid], v)) swap(v, id);
	if(f(a[l], id) < f(a[l], v)) update(2 * x, l, mid, id);
	if(f(a[r], id) < f(a[r], v)) update(2 * x + 1, mid + 1, r, id); 
}
int query(int x, int l, int r, int k){
	if(l > k || r < k) return 1e18;
	int ans = f(a[k], tg[x]);
	if(l == r) return ans;
	int mid = (l + r) >> 1;
	return min(ans, min(query(2 * x, l, mid, k), query(2 * x + 1, mid + 1, r, k)));
}
signed main(){
	cin >> n >> L;
	for(int i = 1; i <= n; i++){
		cin >> c[i];
		sum[i] = sum[i - 1] + c[i];
		t[i] = sum[i] + i;
		a[i] = t[i];
	}
	sort(a + 1, a + n + 1);
	len = unique(a + 1, a + n + 1) - a - 1;
	L++;
	l[0].k = -2 * L;
	l[0].b = L * L;	
	dp[1] = (c[1] - L + 1) * (c[1] - L + 1);
	l[++tot] = line(-2 * t[1], t[1] * t[1] + 2 * t[1] * L + dp[1]);
	update(1, 1, len, tot);
	for(int i = 2; i <= n; i++){
		int u = g(t[i]);
		dp[i] = t[i] * t[i] + query(1, 1, len, u);
		l[++tot] = line(-2 * (t[i] + L), (t[i] + L) * (t[i] + L) + dp[i]);
		update(1, 1, len, tot);
	}
	cout << dp[n];
	return 0;
}

例题三：P6047

是我最喜欢的丝之歌耶( •̀ ω •́ )y
由于只能从左往右切割，那么可以注意到对于交叉的两根线，切割了左斜的那一条就一定能切割右斜的那一条。即对于题目中的图来说：

对于左边的两根线来说，以上端点从左至右排序第一根线被切了，那么第二根也一定会被切掉。
由于所有的线都要切，所以类似于上图第二根线这样的线完全不用考虑，所以可以考虑先把这些线去掉。
由于交叉的线都去掉了一根，所以去掉之后的图案应该是左端点和右端点都单调递增的，那么就可以写出dp式子：

\[dp[i] = \min_{j<i}\{dp[j] + \min^{j - 1}_{k=1}\{a_k \} \times \min^n_{k=i + 1}\{b_k \} \} \]

后面的两个最小值都是可以预处理出来的，可以发现其实是一个一次函数，用李超线段树维护，每次查询查 \(x=\min^n_{k=i + 1}\{b_k \}\) 处的最小值即可。
代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5;
const int M = 1e6 + 5;
int n, m, cnt, tot, a[N], b[N], tg[4 * M], ma[N], mb[N], dp[N];
struct line{
	int k, b;
	line(int x = 0, int y = 0){
		k = x; b = y;
	}
}l[N];
struct silk{
	int u, v;
}song[N], s[N];
bool cmp(silk x, silk y){
	if(x.u == y.u) return x.v > y.v;
	return x.u < y.u;
}
void prework(){
	sort(song + 1, song + m + 1, cmp);
	for(int i = 1; i <= m; i++){
		if(song[i].v > s[cnt].v) s[++cnt] = song[i];
	}
	ma[1] = a[1];
	for(int i = 2; i <= n; i++){
		if(a[i] < ma[i - 1]) ma[i] = a[i];
		else ma[i] = ma[i - 1];
	}
	mb[n] = b[n];
	for(int i = n - 1; i >= 1; i--){
		if(b[i] < mb[i + 1]) mb[i] = b[i];
		else mb[i] = mb[i + 1];
	}
	l[0].b = 1e18;
}
int f(int x, int id){
	return l[id].k * x + l[id].b;
}
void update(int x, int l, int r, int id){
	int &v = tg[x]; int mid = (l + r) >> 1;
	if(f(mid, id) < f(mid, v)) swap(id, v);
	if(f(l, id) < f(l, v)) update(2 * x, l, mid, id);
	if(f(r, id) < f(r, v)) update(2 * x + 1, mid + 1, r, id);
}
int query(int x, int l, int r, int k){
	if(l > k || r < k) return 1e18;
	int ans = f(k, tg[x]);
	if(l == r) return ans;
	int mid = (l + r) >> 1;
	return min(ans, min(query(2 * x, l, mid, k), query(2 * x + 1, mid + 1, r, k)));
}
signed main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) cin >> b[i];
	for(int i = 1; i <= m; i++) cin >> song[i].u >> song[i].v;
	prework();
	for(int i = 1; i <= cnt; i++){
		l[++tot] = line(ma[s[i].u - 1], dp[i - 1]);
		update(1, 0, M, tot);
		dp[i] = query(1, 0, M, mb[s[i].v + 1]);
	} 
	cout << dp[cnt];
	return 0;
}