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

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

  • 插入一个线段（斜率存在），$(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;
}