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

一是给的是横纵坐标所以斜率要用 类型整个题的就都要考虑精度问题。二是输出的是线段编号所以 函数要把值和标号一起传同时因为要求输出编号小的比较的时候也要多比较一个参数。三是给的是线段而不是直线要写一个函数去判断哪些区间被线段完全覆盖。四是数据强制在线这个有点毒瘤了。第一次做李超线段树也可以先考虑做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这道题式子化简还是相当麻烦的。设长度 的前缀和为 那么长度 代入 得到设 那么展开平方提出 观察到 内为一次函数用李超线段树维护每次查询 的最小值。另外注意到前缀和的值域较大所以需要离散化或动态开点。代码#includebits/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式子化简一下把固定的给提出来可以得到注意到 里面是以 为 为 的一次函数所以我们可以用李超线段树维护前面所有的一次函数求 时直接求 时一次函数的最小值。复杂度优化到 。代码#includebits/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二分的值域在这道题为为算下来大概是卡卡能过。代码#includebits/stdc.h #define int long long #define pi pairint, 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 x0,f1;char chgetchar(); while (ch0||ch9){if (ch-) f-1;chgetchar();} while (ch0ch9){xx*10ch-48;chgetchar();} 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 的题解。大概思路是先把每个 的代价提前计算再加上前缀和优化。用 和 表示 和 的前缀和那么可以写出 做法化简一下就可以很容易化出一次函数的形式果断使用李超线段树需要离散化或动态开点。代码#includebits/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; }P5896wqs二分被称为Aliens Trick的出处。所以显然需要前置芝士wqs二分我这里面应该有一篇详细讲了一下这道题就不详细讲wqs二分了。考虑一个坐标为的兴趣点会被怎样的拍摄区域覆盖对于每一个正方形用 表示 表示 可以发现如果有一个左上角方格坐标为 右下角坐标为 的拍摄区域因为一定在主对角线上所以这两个方格的横纵坐标相等当 且 时这个拍摄区域可以覆盖这个兴趣点。这时我们就可以转化一下题意数轴上有 个范围分别为 的区间你要新建 个区间去覆盖一开始的区间新建一个覆盖范围为 的区间的代价为 求最小代价。显然在一开始就已经被其他区间覆盖的区间是没有用的因为覆盖它的区间被覆盖它也就会被覆盖。类似于P6047丝之割把没用的区间去除剩下的区间 单调递增 也单调递增。考虑wqs二分去掉 个限制写出 式子这里是去除重复覆盖展开显然可以斜率优化。由于本题时限为2s所以李超线段树随便过。本题可以不用离散化。代码#includebits/stdc.h