李超线段树

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

看一个栗子:

要求在平面直角坐标系中维护若干线段,支持加入一条线段和查询所有线段与直线 $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)$,不过它的常数很小。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#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)$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#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

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×