当前位置：首页 > news >正文

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

news 2026/7/1 1:46:12

一是给的是横纵坐标，所以斜率要用类型，整个题的就都要考虑精度问题。
二是输出的是线段编号，所以函数要把值和标号一起传，同时因为要求输出编号小的，比较的时候也要多比较一个参数。
三是给的是线段而不是直线，要写一个函数去判断哪些区间被线段完全覆盖。
四是数据强制在线，这个有点毒瘤了。

第一次做李超线段树也可以先考虑做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); } }

然后是李超线段树的重点，当一条线段完全覆盖某个区间时，怎么用这条线段修改这个区间的答案。

设为原本这个直线最大的直线，要用于修改的新直线为。

首先一个最基本且显然的逻辑是如果对于整个区间，直线上的值都大于的值，那么就可以直接把修改为。

那么怎么判断呢？

我们先比较在区间中点，如果就更大就。

后会有以下三种情况：

没有交点：由于保证了在中点处更大，此时在整个区间内一定都更大，不需要再修改，直接return即可。
在左边有交点：递归修改左边即可。
在右边更大：递归修改右边即可。

怎么判断两条线段在两边有没有交点呢？因为我们知道在处更小，所以我们可以比较两条线段在和处的大小，如果在处更大，那么两条线段一定在左边有交点，同理。

因为两边至多有一边会被继续递归修改（否则肯定会在第一步被 swap），复杂度为。

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); }

最后的函数就很简单了，直接沿着有要查询的点的区间跳次记录路径上的最大值即可。

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))); }

板子的代码看起来很长，但是实际上在应用时数据大多都是整数类型，而且都是直线而不是线段，李超线段树的代码是很简洁的，一般来说大概长这样：

struct line{ int k, b; line(int x = 0, int y = 0){ k = x, b = y; } }; struct lctree{ line l[N]; int tg[4 * N]; inline int f(int x, int id){ return l[id].k * x + l[id].b; } inline 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); } inline pi query(int x, int l, int r, int k){ pi out; out.first = f(k, tg[x]); out.second = tg[x]; if(l == r) return out; int mid = (l + r) >> 1; if(k <= mid) return min(out, query(2 * x, l, mid, k)); else return min(out, query(2 * x + 1, mid + 1, r, k)); } }

奉上板子题完整代码：
AC记录

在斜率优化上的应用

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

以下题解按题号排序而非更新时间，所以讲解并非由详细到简略。

P3195

这道题式子化简还是相当麻烦的。

设长度的前缀和为，那么长度，代入，得到：

设，，那么：

展开平方：

提出：

观察到内为一次函数，用李超线段树维护，每次查询的最小值。

另外注意到前缀和的值域较大，所以需要离散化或动态开点。

代码

#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; }

P4655

比较水的一道。

用表示的前缀和，那么可以列出一个的dp式子：

化简一下：

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

注意到里面是以为，为的一次函数，所以我们可以用李超线段树维护前面所有的一次函数，求时直接求时一次函数的最小值。复杂度优化到。

代码

#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； }

P4983

前置芝士：wqs二分，本题李超线段树复杂度比正解多一只，需要卡卡常。

首先显然价值式子可以化简把，平均数消掉，变为。

然后用表示前缀和，可以写出最朴素的做法：

注意到如果没有划分个的限制，写出复杂度正确的dp是容易的，所以这是典型的“恰好选k个”的题目，可以用wqs二分。

具体的，如果以划分数为横坐标，划分数为时的答案为纵坐标建立坐标系，在坐标系内画出点对的连线，可以证明其是一个下凸的函数，所以切线斜率递增时，切点的横坐标也是递增的。所以可以二分斜率。

假设现在我们二分得到的一个新的斜率为，那么根据这个斜率可以得到哪些信息呢？根据，所以截距，由于这个函数是下凸的，所以过切点的那条直线截距是最小的。

那怎么求出最小值呢？由于现在的划分个数（也就是当前斜率对应直线切点的x）必须满足最小截距，也就是说现在是最小的截距决定当前的划分个数，所以我们可以不考虑划分个数限制直接做dp求最小值。

由于要求的是整体的最小值，所以在每次划分（也就是每次转移）的时候 -k 即可。同时在做dp时记录划分的个数，就可以把当前切点对应的给求出来。我们的目标是找到一个对应切点的横坐标等于的斜率，所以就可以根据当前的继续二分斜率。

假设最后找到的斜率是，那么以为 k 再做一次dp，再加上就是最终的答案了。

最后考虑如何做 dp，由于现在我们不需要考虑划分数的限制，所以直接写出式子：

拆开得到：

使用李超线段树即可，复杂度，为wqs二分的值域，在这道题为；为，算下来大概是，卡卡能过。

代码

#include<bits/stdc++.h> #define int long long #define pi pair<int, int> using namespace std; const int N = 1e5 + 5; int n, m, len, a[N], sum[N], tg[4 * N], dp[N], cnt[N]; 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*10+ch-48;ch=getchar();} return x*f; } struct line{ int k, b; line(int x = 0, int y = 0){ k = x, b = y; } }l[N]; inline pi min(pi a, pi b){ if(a.first < b.first) return a; return b; } inline int g(int x){ return lower_bound(a + 1, a + len + 1, x) - a; } inline int f(int x, int id){ return l[id].k * x + l[id].b; } inline 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(id, v); 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); } inline pi query(int x, int l, int r, int k){ pi out; out.second = tg[x]; out.first = f(a[k], tg[x]); if(l == r) return out; int mid = (l + r) >> 1; if(k <= mid) return min(out, query(2 * x, l, mid, k)); return min(out, query(2 * x + 1, mid + 1, r, k)); } inline int check(int k){ memset(tg, 0, sizeof(tg)); for(int i = 1; i <= n; i++){ pi out = query(1, 1, len, g(sum[i])); dp[i] = (sum[i] + 1) * (sum[i] + 1) + out.first - k; l[i] = line(-2 * sum[i], sum[i] * sum[i] - 2 * sum[i] + dp[i]); update(1, 1, len, i); cnt[i] = cnt[out.second] + 1; } return cnt[n]; } signed main(){ n = read(); m = read(); for(int i = 1; i <= n; i++){ sum[i] = read(); sum[i] += sum[i - 1]; a[i] = sum[i]; } sort(a + 1, a + n + 1); len = unique(a + 1, a + n + 1) - a - 1; int l = -1e18, r = 0; while(l <= r){ int mid = (l + r) >> 1; if(check(mid) >= m) r = mid - 1; else l = mid + 1; } check(r); cout << dp[n] + m * r; return 0; }

P5785

双倍经验：P10979

这道题的的做法还是挺不好想的，这里不赘述，可以看弱化版 P2365 的题解。

大概思路是先把每个的代价提前计算，再加上前缀和优化。

用和表示和的前缀和，那么可以写出做法：

化简一下就可以很容易化出一次函数的形式：

果断使用李超线段树，需要离散化或动态开点。

代码

#include<bits/stdc++.h> #define int long long using namespace std; const int N = 3e5 + 5; int n, s, len, tot, f[N], t[N], sumf[N], sumt[N], a[N], tg[4 * N], dp[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(id, v); 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; if(k <= mid) return min(ans, query(2 * x, l, mid, k)); return min(ans, query(2 * x + 1, mid + 1, r, k)); } signed main(){ cin >> n >> s; for(int i = 1; i <= n; i++){ cin >> t[i] >> f[i]; sumt[i] = sumt[i - 1] + t[i]; sumf[i] = sumf[i - 1] + f[i]; a[i] = sumt[i]; } sort(a + 1, a + 1 + n); len = unique(a + 1, a + n + 1) - a - 1; for(int i = 1; i <= n; i++){ dp[i] = sumf[n] * s + sumf[i] * sumt[i] + query(1, 1, len, g(sumt[i])); l[++tot] = line(-sumf[i], dp[i] - sumf[i] * s); update(1, 1, len, tot); } cout << dp[n]; return 0; }