简述

李超树得名于其发明者——杭州学军中学的李超大神。这个数据结构主要用于解决动态维护（上\下）凸包，是一个非常神仙的东西，主要难点在于处理线段树上的懒惰标记。

算法代码与解释

这个算法有下面几个函数：

• INTERSECT(k1, k2, b1, b2)：求两直线交点的横坐标。
• UPDATE(k, b, l, r, p)：向李超树中加入直线。
• QUERY(qx, l, r, p)：询问当横坐标为\(qx\)时纵坐标的高度。

我们先来思考 UPDATE 操作。考虑以下几种情形：

• 如果我们发现该区间未储存直线，那么我们直接赋值即可。
• 如果我们发现原先有了直线，那么求出两端点上两直线的函数值，待加入直线在\(l\)上的函数值为\(ff\)，在\(r\)上的函数值为\(fb\)，待比较直线在\(l\)上的函数值为\(gf\)，在\(r\)上的函数值为\(gb\)。我们考虑下面几种情况：
  • 如果两直线平行（也就是\(ff,fb\)与\(gf,gb\)有相同的大小关系时），那么我们直接比较高度取最高\最低的直线。
  • 如果两直线有交点，我们求出交点的横坐标\(intx\)，分别进行考虑进行左右儿子更新即可。

例题

// BZ1568.cpp
#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lson (p << 1)
#define rson ((p << 1) | 1)
using namespace std;
const int MAX_Q = 100020, MAX_N = 50010, ENDPOINT = 50000;
int n, tmpx;
char opt[10];
double lnk[MAX_N << 2], lnb[MAX_N << 2], tmpw, tmpz;
bool tag[MAX_N << 2];
double intersect(double k1, double b1, double k2, double b2) { return 1.0 * (b2 - b1) / (k1 - k2); }
void update(double k, double b, int l, int r, int p)
{
    if (tag[p])
    {
        double ff = k * l + b, gf = lnk[p] * l + lnb[p], fb = k * r + b, gb = lnk[p] * r + lnb[p];
        if (ff <= gf && fb <= gb)
            return;
        else if (ff >= gf && fb >= gb)
        {
            lnk[p] = k, lnb[p] = b;
            return;
        }
        double intx = intersect(k, b, lnk[p], lnb[p]);
        if (ff >= gf)
            if (intx <= mid)
                update(k, b, l, mid, lson);
            else
                update(lnk[p], lnb[p], mid + 1, r, rson), lnk[p] = k, lnb[p] = b;
        else if (intx > mid)
            update(k, b, mid + 1, r, rson);
        else
            update(lnk[p], lnb[p], l, mid, lson), lnk[p] = k, lnb[p] = b;
    }
    else
        lnk[p] = k, lnb[p] = b, tag[p] = true;
}
double query(int qx, int l, int r, int p)
{
    double ans = 0;
    if (tag[p])
        ans = max(ans, 1.0 * qx * lnk[p] + lnb[p]);
    if (l == r)
        return ans;
    if (qx <= mid)
        ans = max(ans, query(qx, l, mid, lson));
    else
        ans = max(ans, query(qx, mid + 1, r, rson));
    return ans;
}
int main()
{
    scanf("%d", &n);
    while (n--)
    {
        scanf("%s", opt + 1);
        if (opt[1] == 'Q')
            scanf("%d", &tmpx), printf("%d\n", (int)(query(tmpx, 1, ENDPOINT, 1) / 100.0));
        else
            scanf("%lf%lf", &tmpw, &tmpz), update(tmpz, tmpw - tmpz, 1, ENDPOINT, 1);
    }
    return 0;
}