李超线段树

众所周知，李超线段树是一类在二维平面上维护最值线段的线段树，某些情况下具有着和动态凸包相类似的功用……

看一个栗子：

要求在平面直角坐标系中维护若干线段，支持加入一条线段和查询所有线段与直线 $x=k$ （$k$ 给出）交点纵坐标的最大值。
一条线段以两个端点 $(x_0,y_0),(x_1,y_1)$ 的形式给出。
$q,k,x_0,y_0,x_1,y_1\le 10^5$

考虑用线段树维护这些斜线。方便起见，我们将线段看成解析式的形式 $f_i(x)$。对于区间 $[l,r]$，它的中点是 $m$，我们定义 $f_i(x)$ 在这个区间上比 $f_j(x)$ 更具优势，当且仅当 $f_i(m)>f_j(m)$。对于线段树上的每个节点，我们只保留它的最优势线段，这样就可操作了。

剩余的是两个问题：一条当前区间的劣势线段可能是子区间的优势线段；统计 $p$ 点处的答案时，不一定 $[p,p]$ 上存的线段是最优秀的线段。

对于第二个问题，我们只需要将线段树上从根到 $[p,p]$ 的祖孙链上的所有线段都统计一遍即可；对于第一个问题，可以考虑把劣势线段下放到它和保留线段（优势线段）有交的那个子区间里，然后递归操作即可。

根据主定理，这一部分的复杂度（更新某个区间）是 $O(\log n)$ 的，因此李超树插入的总复杂度为 $O(\log^2 n)$，查询的总复杂度为 $O(\log n)$，不过它的常数很小。

代码：

#include<bits/stdc++.h>
using namespace std;
#define DB double
#define mp make_pair
const int CN = 1e5 + 50;
const DB EPS = 1e-10;
int read(){
    int s = 0, ne = 1; char c = getchar();
    for(;c < '0' || c > '9';c = getchar()) if(c == '-') ne = -1;
    for(;c >= '0' && c <= '9';c = getchar()) s = (s << 1) + (s << 3) + c - '0';
    return s * ne;
}
bool equ(DB a, DB b) {return abs(a - b) <= EPS;}
int n, lastans;
class SEG {public: 
    int l, r, id; DB yl, yr;  SEG() {l = id = 0, r = 1;}
    DB slp() {return (yr - yl) / (1.0 * (r - l));}
    DB mid() {return (yl + yr) / 2;}
    DB val(int x) {return l == r ? yl : yl + slp() * (x - l);}
    void cl(int x) {yl = val(x), l = x;}
    void cr(int x) {yr = val(x), r = x;}
} ;
SEG mk(int a, int b, int c, int d, int e){
    SEG o; o.l = a, o.yl = b, o.r = c, o.yr = d, o.id = e;
    return o;
}
bool le(SEG a, SEG b) {
    return a.mid() < b.mid() || (equ(a.mid(), b.mid()) && a.id > b.id);
}
class SGT {
  public: SEG d[CN << 2];
    #define lc k << 1
    #define rc k << 1 | 1
    void upd(int l, int r, int k, SEG x){
        if(x.l < l) x.cl(l); if(x.r > r) x.cr(r);
        if(le(d[k], x)) swap(d[k], x);
        if(l == r) return;
        int m = (l + r) >> 1;
        if(x.slp() < d[k].slp()) upd(l, m, lc, x);
        else upd(m + 1, r, rc, x);
    }
    void md(int l, int r, int k, SEG x){
        if(x.l < l) x.cl(l); if(x.r > r) x.cr(r);
        if(x.l == l && x.r == r) return (void)(upd(l, r, k, x));
        int m = (l + r) >> 1;
        if(x.l <= m) md(l, m, lc, x);
        if(m < x.r) md(m + 1, r, rc, x);
    } 
    pair<DB, int> qu(int l, int r, int k, int p){
        if(l == r) return mp(d[k].mid(), d[k].id);
        int m = (l + r) >> 1; pair<DB, int> ans;
        if(p <= m) ans = qu(l, m, lc, p);
        else ans = qu(m + 1, r, rc, p);
        if(d[k].val(p) > ans.first || (equ(d[k].val(p), ans.first) && d[k].id < ans.second))
            ans.first = d[k].val(p), ans.second = d[k].id;
        return ans;
    }
} D;
int enc(int x, int p) {return (x + lastans - 1) % p + 1;}
int main()
{
    freopen("_in.in", "r", stdin);
    n = read(); int cnt = 0;
    for(int i = 1; i <= n; i++){
        int tp = read(), a = read(), b, c, d;
        if(tp){
            b = read(), c = read(), d = read();
            a = enc(a, 39989), b = enc(b, 1e9), c = enc(c, 39989), d = enc(d, 1e9);
            if(a > c) swap(a, c), swap(b, d);
            D.md(1, 1e5, 1, mk(a, b, c, d, ++cnt));
        }
        else a = enc(a, 39989),
             printf("%d\n", lastans = D.qu(1, 1e5, 1, a).second);
    }
    return 0;
}

在斜率优化中的应用

看这样一个斜率优化的经典模型：

有 $n$ 个点依次排列，第 $i$ 个点有正数权值 $h_i$。你可以划一条线段连接两个点 $i,j$，费用是 $(h_i-h_j)^2$；要求你画的所有线段只能在端点处相交，且对于每个未被连接的点 $i$，需要支付 $w_i$ 的费用。
现在需要把 $1$ 号点和 $n$ 号点连接，求连接的最小费用。
$n\le 2\times 10^5, 0\le |w_i|, h_i\le 10^6$

设 $f[i]$ 为连接到 $i$ 的最小费用，设 $s_i$ 是 $w_i$ 的前缀和，有 $f[i] = \min\limits_{j=1}^{i-1}f[j]+(h_i-h_j)^2+s_{i-1}-s_j$。

我们可以考虑将其化为斜率优化的一般形式，设 $y_j=f[j]+h^2_j-s_j,b_j=-2h_ih_j+y_j$，则可以看成有一堆点 $(h_j,y_j)$，每次给出一个斜率 $-2h_i$，求纵轴截距 $b_j$ 的最小值。由于 $h_j$ 和 $-2h_i$ 均不单调，朴素斜率优化思路需要用 Splay 维护下凸包二分，或者 CDQ 分治，但是我都不会。

换一个思路：设 $f_i(x)=k_ix+y_i$，其中 $k_i=-2h_i,y_i=f[i]+h^2_i-s_i$，则我们在求 $h^2_i+s_{i-1}+\min\limits_{j=1}^{i-1} f_j(h_i)$。后面那个式子直接用李超树维护即可，由于这里的线段是直线，因此复杂度 $O(n\log n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int CN = 1e5 + 10;
const int CV = 1e6 + 10;
LL read(){
    LL s = 0, ne = 1; char c = getchar();
    for(;c < '0' || c > '9';c = getchar()) if(c == '-') ne = -1;
    for(;c >= '0' && c <= '9';c = getchar()) s = (s << 1) + (s << 3) + c - '0';
    return s * ne;
}
int n; LL h[CN], s[CN];
LL squ(LL x) {return x * x;}
class SEG {public: LL k, b; SEG() {b = 1e18;} LL val(LL p) {return k * p + b;}} ;
SEG mk(LL a, LL b) {SEG o; o.k = a, o.b = b; return o;}
class SGT {
  public: SEG d[CV << 2];
    #define lc k << 1
    #define rc k << 1 | 1
    void upd(int l, int r, int k, SEG x){
        int m = (l + r) >> 1;
        if(x.val(m) < d[k].val(m)) swap(d[k], x);
        if(l == r) return;
        if(x.k > d[k].k) upd(l, m, lc, x); else upd(m + 1, r, rc, x);
    }
    LL qu(int l, int r, int k, int p){
        if(l == r) return d[k].val(p);
        int m = (l + r) >> 1; LL ans = 1e18;
        if(p <= m) ans = qu(l, m, lc, p); else ans = qu(m + 1, r, rc, p);
        return min(ans, d[k].val(p));
    }
} D;
int main()
{
    n = read();
    for(int i = 1; i <= n; i++) h[i] = read();
    for(int i = 1; i <= n; i++) s[i] = s[i - 1] + read();
    LL yi = squ(h[1]) - s[1], ki = -2 * h[1], fi;
    D.upd(1, 1e6, 1, mk(ki, yi));
    for(int i = 2; i <= n; i++){
        fi = squ(h[i]) + s[i - 1] + D.qu(1, 1e6, 1, h[i]), 
        yi = squ(h[i]) - s[i] + fi, ki = -2 * h[i],
        D.upd(1, 1e6, 1, mk(ki, yi));
    }
    printf("%lld", fi);
    return 0;
}

相关题目

1. 「HEOI2013」Segment
2. 「CEOI2017」Building Bridges