李超线段树模板及应用

· · 算法·理论

李超线段树模板及应用

博客园链接：link

李超线段树用于一系列平面上的一次函数，维护对于每一个 x 最大或最小的 y 值。

模板题

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

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

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

设 tg[x] 为原本这个直线最大的直线，要用于修改的新直线为 f。

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

那么怎么判断呢？

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

swap 后会有以下三种情况：

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

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

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

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

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 式子中需要动态维护的一个区间最值的式子化成一个一次函数，这样就可以用李超线段树来维护，O( \log n) 的时间就能找到最值，从而优化时间复杂度。

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

P3195

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

设长度 c_i 的前缀和为 s_i，那么长度 x = i - j - 1 + s_i - s_j，代入 x，得到：

\large dp_i = \min_{j<i}\{dp_j + (i - j + s_i - s_j - L - 1)^2 \}

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

\large dp_i = \min_{j<i}\{dp_j + (t_i - t_j - b)^2 \}

展开平方：

\large dp_i = \min_{j<i}\{t_i^2 - 2(t_j + b)t_i + (t_j + b)^2 \}

提出 t_i^2：

\large dp_i = t_i^2 + \min_{j<i}\{-2(t_j + b)t_i + (t_j + b)^2 \}

观察到 \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;
}

P4655

比较水的一道。

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

\large dp_i = \min_{j<i}\{dp_j + (h_i - h_j)^2 + s_{i - 1} - s_j\}

化简一下：

\large 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\}

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

\large dp_i = h_i^2 + s_{i-1} + \min_{j<i}\{-2h_j \times h_i + (h_j^2 - s_j + dp_j) \}

注意到 \min 里面是以 -2h_j 为 k，h_j^2 - s_j + dp_j 为 b 的一次函数，所以我们可以用李超线段树维护前面所有的一次函数，求 dp_i 时直接求 x = h_i 时一次函数的最小值。复杂度优化到 O(n \log n)。

代码

#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 二分，本题李超线段树复杂度比正解多一只 log，需要卡卡常。

首先显然价值式子可以化简把，平均数消掉，变为 (\sum{x_i} + 1)^2。

然后用 s 表示前缀和，可以写出最朴素的 O(n^3) 做法：

\large dp_{i,j} = \min_{k<i}\{dp_{k,j-1} + (s_i - s_k + 1)^2 \}

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

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

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

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

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

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

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

\large dp_i = \min_{j<i}\{dp_j + (s_i - s_j + 1)^2 \} - k

拆开得到：

\large dp_i =(s_i + 1)^2 + \min_{j<i}\{-2s_js_i + s_j^2 - 2s_j + dp_j \} - k

使用李超线段树即可，复杂度 O(n \log n \log V)，V 为 wqs 二分的值域，在这道题为 1 \times 10^{18}；n 为 1 \times 10^5，算下来大概是 1 \times 10^8，卡卡能过。

代码

#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

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

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

用 sumf 和 sumt 表示 f 和 t 的前缀和，那么可以写出 n^2 做法：

\large dp_i = \min_{j<i}\{dp_j + sumt_i \times (sumf_i - sumf_j) + s \times (sumf_n - sumf_j) \}

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

\large dp_i = s \times sumf_n + sumt_i \times sumf_i + \min_{j<i}\{-sumf_j * sumt_i + dp_j - s \times sumf_j \}

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

代码

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

P5896

wqs 二分被称为 "Aliens Trick" 的出处。所以显然需要前置芝士 wqs 二分（我这里面应该有一篇详细讲了一下，这道题就不详细讲 wqs 二分了）。

考虑一个坐标为 (x, y) 的兴趣点会被怎样的拍摄区域覆盖：对于每一个正方形，用 l 表示 \min (x, y)，r 表示 \max (x, y)，可以发现如果有一个左上角方格坐标为 (L, L)，右下角坐标为 (R, R) 的拍摄区域（因为一定在主对角线上，所以这两个方格的横纵坐标相等），当 L \le l 且 R \ge r 时这个拍摄区域可以覆盖这个兴趣点。

这时我们就可以转化一下题意：数轴上有 n 个范围分别为 (l_i, r_i) 的区间，你要新建 k 个区间去覆盖一开始的区间，新建一个覆盖范围为 (L, R) 的区间的代价为 (R - L + 1) ^ 2，求最小代价。

显然在一开始就已经被其他区间覆盖的区间是没有用的，因为覆盖它的区间被覆盖它也就会被覆盖。类似于 P6047 丝之割，把没用的区间去除，剩下的区间 l 单调递增，r 也单调递增。考虑 wqs 二分去掉 k 个限制，写出 dp 式子：

\large dp_i = \min_{j < i}\{dp_j + (r_i - l_{i + 1} + 1)^2 - \max (0, r_j - l_{j + 1} + 1)^2_{(\texttt{这里是去除重复覆盖})} \} - K_{wqs}

展开：

\large dp_i = (r_i + 1)^2 + \min_{j < i}\{-2l_{j+1}(r_i + 1) + dp_j + l_{j + 1}^2 - \max (0, r_j - l_{j+1} + 1)^2 \} - K

显然可以斜率优化。由于本题时限为 2s 所以李超线段树随便过。本题可以不用离散化。

代码

#include<bits/stdc++.h>
#define pi pair<int, int>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, k;
int ans, tot, cnt, len, tg[4 * N], dp[N], s[N], a[N];
struct line{
    int k, b;
    line(int x = 0, int y = 0){
        k = x, b = y;
    }
}l[N];
struct node{
    int l, r;
}b[N], c[N];
inline bool cmp(node a, node b){
    if(a.l == b.l) return a.r > b.r;
    return a.l < b.l;
}
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(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);
}
inline pi query(int x, int l, int r, int k){
    pi out;
    out.first = f(a[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)); 
}
inline bool check(int K){
    memset(tg, 0, sizeof(tg));
    l[0] = line(-2 * c[1].l, dp[0] + c[1].l * c[1].l);
    update(1, 1, len, 0);
    for(int i = 1; i <= n; i++){
        pi q = query(1, 1, len, g(c[i].r + 1));
        dp[i] = (c[i].r + 1) * (c[i].r + 1) + q.first - K;
        s[i] = s[q.second] + 1;
        l[i] = line(-2 * c[i + 1].l, dp[i] + c[i + 1].l * c[i + 1].l - max((long long)0, (c[i].r - c[i + 1].l + 1)) * max((long long)0, (c[i].r - c[i + 1].l + 1)));
        update(1, 1, len, i);
    }
    if(s[n] <= k) ans = dp[n] + k * K;
    return s[n] <= k;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        int x, y;
        cin >> x >> y;
        x++; y++;
        b[i].l = min(x, y); 
        b[i].r = max(x, y);
    }
    sort(b + 1, b + n + 1, cmp);
    for(int i = 1; i <= n; i++){
        if(b[i].r > c[tot].r){
            c[++tot] = b[i];
            a[++cnt] = c[tot].r + 1;    
        } 
    }
    len = unique(a + 1, a + cnt + 1) - a - 1;
    n = tot;
    int L = -1 * m * m, R = 0;
    while(L <= R){
        int mid = (L + R) >> 1;
        if(check(mid)) L = mid + 1;
        else R = mid - 1;
    }
    check(R);
    cout << ans;
    return 0;
}

P6047

是我最喜欢的丝之歌耶 (・̀ ω・́) y。

由于只能从左往右切割，那么可以注意到对于交叉的两根线，切割了左斜的那一条就一定能切割右斜的那一条。即对于题目中的图来说：对于左边的两根线来说，以上端点从左至右排序第一根线被切了，那么第二根也一定会被切掉。

由于所有的线都要切，所以类似于上图第二根线这样的线完全不用考虑，所以可以考虑先把这些线去掉。

由于交叉的线都去掉了一根，所以去掉之后的图案应该是左端点和右端点都单调递增的，那么就可以写出 dp 式子：

\large 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;
}

P6246

前置芝士：wqs 二分。

根据小学芝士对于每一个区间修在中间是最优的，用前缀和优化可以 O(1) 计算代价，然后就可以过掉绿题版本。

加上一个裸的 wqs 二分可以以 1e8 的理论复杂度，实际最慢的点也不超过 400ms 的速度过掉紫题版本（数据真水）。

对于本题，先 wqs 二分去掉选 m 个的限制，然后抛弃修在中间是最优的想法（那样不好斜率优化）。这样写出一个 O(n^3) 的 dp 柿子（s 为前缀和）：

\large dp_i = \min_{j \le i}\{(s_i-s_j)-(i-j)\times a_j + \min_{k<j}\{(j-k)\times a_j - (s_j-s_k) \}\}

设 f_i = \min_{k<j}\{(j-k)\times a_j - (s_j-s_k) \}\}，发现可以斜率优化求得。

然后发现 dp_i = \min_{j \le i}\{(s_i-s_j)-(i-j)\times a_j + f_j \}，也可以斜率优化。

代码

#include<bits/stdc++.h>
#define int long long
#define pi pair<int, int>
using namespace std;
const int N = 2e6 + 5;
int n, m, ans, mx, a[N], sum[N], dp[N], f[N], cnt1[N], cnt2[N];
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)); 
    }
}tr1, tr2;
inline bool check(int k){
    memset(tr1.tg, 0, sizeof(tr1.tg));
    memset(tr2.tg, 0, sizeof(tr2.tg));
    for(int i = 1; i <= n; i++) f[i] = cnt1[i] = cnt2[i] = 0;
    for(int i = 1; i <= n; i++){
        pi q = tr2.query(1, 1, mx + 1, a[i]);
        f[i] = i * a[i] -sum[i] + q.first;
        cnt2[i] = cnt1[q.second];
        tr1.l[i] = line(-a[i], i * a[i] - sum[i] + f[i]);
        tr1.update(1, 1, n, i);
        q = tr1.query(1, 1, n, i);
        dp[i] = sum[i] + q.first - k;
        cnt1[i] = cnt2[q.second] + 1;
        tr2.l[i] = line(-i, sum[i] + dp[i]);
        tr2.update(1, 1, mx + 1, i);
    }   
    if(cnt1[n] <= m) ans = dp[n] + m * k;
    return cnt1[n] <= m;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        mx = max(mx, a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    int l = -2e6, r = 0, res;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(mid)) res = mid, l = mid + 1;
        else r = mid - 1; 
    }
    check(res);
    cout << ans;
    return 0;
}

P8726

斜率优化水题，n^2 的式子及其明显：

\large dp_i = \max_{j<i}\{T_i \times T_j + \lfloor\frac{dp_j}{2}\rfloor\ - F_j \}

然后发现这个式子本身就是一次函数，不需要做任何化简就可以直接套李超线段树。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
const int M = 2e4 + 5;
int n, tot, t[N], f[N], dp[N], tg[N * 4], ans;
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(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 res = F(k, tg[x]);
    if(l == r) return res;
    int mid = (l + r) >> 1;
    return max(res, max(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 >> t[i];
    for(int i = 1; i <= n; i++) cin >> f[i];
    l[0].b = -1e18;
    l[++tot] = line(t[1], dp[1] / 2 - f[1]);
    update(1, 0, M, tot);
    for(int i = 2; i <= n; i++){
        dp[i] = query(1, 0, M, t[i]);
        ans = max(ans, dp[i]);
        l[++tot] = line(t[i], dp[i] / 2 - f[i]);
        update(1, 0, M, tot);
    }
    cout << ans;
    return 0; 
}

直接维护直线或线段的应用

这些题可以把操作转化为维护一些直线或线段，然后直接用李超线段树。

P11728

容易发现每一个机器人离原点的距离是关于 t 的一次函数。也就是说，以时间为横坐标，离原点的距离为纵坐标建立平面直角坐标系，可以用一条条线段（也就是有定义域限制的一次函数）。

那现在有 command 操作，线段变成了一段折线，又该怎么做呢？很容易发现，折线中的每一段还是一条条限制了定义域的一次函数，所以本质上没区别。

为了确定每一条线段的定义域，需要把操作离线，然后对于每一个机器人分别操作，把它对应的折线一段一段加进去。

注意由于是离原点的距离，y 的负半轴也要考虑，所以函数求值时要加绝对值。另外 t 的值域过大，但是我不想写动态开点，所以写了离散化。

代码

#include<bits/stdc++.h>
#define int long long
#define pi pair<int, int> 
using namespace std;
const int N = 6e5 + 5;
int n, m, maxt, len, tot, c[N], a[N], tg[4 * N], dp[N];
vector<int> ask;
vector<pi> cg[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 abs(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);
}
void modify(int x, int l, int r, int cl, int cr, int id){
    if(r < cl || l > cr) return; 
    if(l >= cl && r <= cr) update(x, l, r, id);
    else {
        int mid = (l + r) >> 1;
        modify(2 * x, l, mid, cl, cr, id);
        modify(2 * x + 1, mid + 1, r, cl, cr, id);
    }
}
int query(int x, int l, int r, int k){
    int ans = f(a[k], tg[x]);
    if(l == r) return ans;
    int mid = (l + r) >> 1;
    if(k <= mid) return max(ans, query(2 * x, l, mid, k));
    return max(ans, query(2 * x + 1, mid + 1, r, k));
}
signed main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> c[i];
        cg[i].push_back({0, 0});
    }
    a[1] = 0;
    for(int i = 1; i <= m; i++){
        int t, k, x;
        string s;
        cin >> t >> s;
        maxt = max(maxt, t);
        a[i + 1] = t;
        if(s[0] == 'c'){
            cin >> k >> x;
            if((*cg[k].rbegin()).first == t) cg[k].pop_back();
            cg[k].push_back({t, x});
        }
        else ask.push_back(t);
    }
    m++;
    sort(a + 1, a + 1 + m);
    len = unique(a + 1, a + m + 1) - a - 1;
    for(int i = 1; i <= n; i++){
        cg[i].push_back({maxt + 1, 0});
        int h = c[i];
        for(int j = 0; j < cg[i].size() - 1; j++){
            l[++tot] = line(cg[i][j].second, h - cg[i][j].first * cg[i][j].second);
            modify(1, 0, len + 1, g(cg[i][j].first), g(cg[i][j + 1].first - 1), tot);
            h += (cg[i][j + 1].first - cg[i][j].first) * l[tot].k;
        }
    }
    for(int i = 0; i < ask.size(); i++){
        cout << query(1, 0, len + 1, g(ask[i])) << '\n';
    }
    return 0;
}