李超线段树

        一个擅长打辅助的数据结构。

        李超线段树是一种特殊的线段树,它支持在二维直角坐标平面上进行下列操作:

  • 插入一个线段(斜率存在),$(x_1,y_1)$到$(x_2,y_2),x_1\not =x_2$。
  • 对于某个横坐标$x$,查询从坐标点$(x,+\infty)$向$y$轴负半轴看去,能够看到的最高的位于某线段上的坐标点$(x,y_0)$,输出$y_0$。

        李超线段树其实就是可以解决下面这个问题:
        给定一些形如$y=kx+b,x_1\leq x\leq x_2$的线段集合,求对于某个$x$,找到最大的$y$值。
        现在考虑如何用线段树维护这个过程,我们开一棵线段树,每一个线段树节点保留两个值$k$和$b$,表示在这个位置的最优线段的斜率和纵截距。
        当插入一条线段,递归到目标区间时,有下面三种情况:

  • 该位置尚未有最优线段,直接赋值返回。
  • 该位置已有的线段被待插入线段完全覆盖,直接赋值返回。
  • 待插入线段被已有线段完全覆盖,直接返回。
  • 两条线段在区间中有交点,考察两者优势区间(就是可以覆盖对方的区间)的长度,将线段树节点设置为优势区间更长的一个,然后将另一个递归向下插入。

        由于上面第四步的存在,插入线段的时间复杂度不是单纯的$O(logn)$,而是$O(log^2n)$。
        在实际操作中,我们通常不直接比较优势区间大小(这样做代码太冗杂),而是取区间中点,然后考察两个线段在此处值的大小,取较大者,紧接着向下递归插入另一条。插入的算法代码如下:

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
double ndk[N << 2], ndb[N << 2];//线段树的k和b
inline double f(double kk, double bb, double x)//方便求值
{
return kk * x + bb;
}
void modify(int l, int r, double K, double B, int L = 1, int R = n, int k = 1)
{
double s1, s2;
int mid = (L + R) >> 1;
if (L >= l && R <= r) {
if (f(K, B, L) >= f(ndk[k], ndb[k], L) && f(K, B, R) >= f(ndk[k], ndb[k], R)) {
ndk[k] = K, ndb[k] = B;//被完全覆盖
} else if (f(K, B, L) <= f(ndk[k], ndb[k], L) && f(K, B, R) <= f(ndk[k], ndb[k], R)) {
return;//将待插入线段完全覆盖
} else {
double xx = (B - ndb[k]) / (ndk[k] - K), dm = (L + R) / 2.0;
if (f(K, B, dm) > f(ndk[k], ndb[k], dm)) swap(ndk[k], K), swap(ndb[k], B);//取中点值较大的一个
if (xx <= mid)
modify(L, mid, K, B, L, mid, k << 1);//递归插入另一条
else
modify(mid + 1, R, K, B, mid + 1, R, k << 1 | 1);
}
return;
}
//这里就是单纯的线段树操作
if (r <= mid)
modify(l, r, K, B, L, mid, k << 1);
else if (l > mid)
modify(l, r, K, B, mid + 1, R, k << 1 | 1);
else
modify(l, mid, K, B, L, mid, k << 1), modify(mid + 1, r, K, B, mid + 1, R, k << 1 | 1);
}

        查询比较容易,递归到底层,然后在所有经过的节点上取一个$\max$即可。

1
2
3
4
5
6
7
double query(int at, int L = 1, int R = n, int k = 1)
{
if (L == R) return f(ndk[k], ndb[k], at);
int mid = (L + R) >> 1;
if (at <= mid) return max(f(ndk[k], ndb[k], at), query(at, L, mid, k << 1));
return max(f(ndk[k], ndb[k], at), query(at, mid + 1, R, k << 1 | 1));
}

        模板题代码:

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
#include <bits/stdc++.h>
#define N 100005
using namespace std;
double ndk[N << 2], ndb[N << 2];
inline double f(double kk, double bb, double x)
{
return kk * x + bb;
}
void modify(int l, int r, double K, double B, int L = 1, int R = 50000, int k = 1)
{
double s1, s2;
int mid = (L + R) >> 1;
if (L >= l && R <= r) {
if (f(K, B, L) >= f(ndk[k], ndb[k], L) && f(K, B, R) >= f(ndk[k], ndb[k], R)) {
ndk[k] = K, ndb[k] = B;
} else if (f(K, B, L) <= f(ndk[k], ndb[k], L) && f(K, B, R) <= f(ndk[k], ndb[k], R)) {
return;
} else {
double xx = (B - ndb[k]) / (ndk[k] - K), dm = (L + R) / 2.0;
if (f(K, B, dm) > f(ndk[k], ndb[k], dm)) swap(ndk[k], K), swap(ndb[k], B);
if (xx <= mid)
modify(L, mid, K, B, L, mid, k << 1);
else
modify(mid + 1, R, K, B, mid + 1, R, k << 1 | 1);
}
return;
}
if (r <= mid)
modify(l, r, K, B, L, mid, k << 1);
else if (l > mid)
modify(l, r, K, B, mid + 1, R, k << 1 | 1);
else
modify(l, mid, K, B, L, mid, k << 1), modify(mid + 1, r, K, B, mid + 1, R, k << 1 | 1);
}
double query(int at, int L = 1, int R = 50000, int k = 1)
{
if (L == R) return f(ndk[k], ndb[k], at);
int mid = (L + R) >> 1;
if (at <= mid) return max(f(ndk[k], ndb[k], at), query(at, L, mid, k << 1));
return max(f(ndk[k], ndb[k], at), query(at, mid + 1, R, k << 1 | 1));
}
char opt[20];
int n;
int main()
{
scanf("%d", &n);
while (n--) {
double s, p;
int at;
scanf("%s", opt);
if (opt[0] == 'Q') {
scanf("%d", &at);
printf("%d\n", int(floor(query(at))) / 100);
} else {
scanf("%lf%lf", &s, &p);
modify(1, 50000, p, s - p);
}
}
// PAUSE;
return 0;
}

0%