LGOJ4254 [JSOI2008]Blue Mary开公司

题意

Link_Luogu

题解

本题是李超线段树模板

李超线段树解决的问题

考虑下面一个问题：

定义一个坐标系，有 m 次操作

操作 1：添加一条直线；

操作 2：求 x=x0 这条直线和其他直线的交点的最高纵坐标。

要求时间复杂度 log 级别，可以用线段树维护。

李超线段树的原理

对于一个区间，我们维护该区间的所有直线中，没有被其他直线覆盖的从上往下去看在x轴上的投影最大的直线（称为标记直线）。

其实这条直线的意义就是对这个区间内大多数点而言最优的直线，但也不一定是最优的直线，更优解可能在更小的区间内。

现在插入一条直线（称为新直线）到了一个区间，尝试更改该区间的标记直线。

分为几种情况：

1.新直线完全覆盖标记直线，直接更新并return，不用继续向下更新。

2.新直线完全被覆盖，那么新直线无用，直接return。

3.不是上面两种情况，判断两条直线哪一个投影大一些，作为新的标记直线，再递归下去处理。

注意，"3." 里面递归下去处理的是投影小的那一个哦（变向 Pushdown emmm...）

询问时直接整个线段树包含 x0 的区间所存的线段取 max 即可（相当于标记永久化中的单点查询）。

其实相当于一个标记永久化的思想（使用永久化实现对“子树的类覆盖”）。

本质上我们可以考虑一个暴力，就是每一次把这条直线所包含的所有线段树的区间暴力更新“标记直线”，这样的话在最下层答案肯定是正确的。

然后我们易发现上面的标记永久化和这个暴力是等价的（影响的都是一个子树）；依次类推，如果插入的不是直线而是线段，可以把线段拆到 log 个被这个线段完全覆盖的区间上，在这些区间上这些线段都可以看成是直线，复杂度多一个 log。

最后如果是要询问一个区间的最大值也很好处理，如果是插入的是直线，只需询问区间的两个端点就可以了；线段的话只要插入的时候算出区间两个端点的值然后 Pushup，同时还要进行查询 max 的标记永久化。

要注意斜率是在 x = 0 处的取值

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, MAXVAL = 50008;

struct Line {
    double k, b;
    template <class TT>
    inline double val(TT x) { return k * x + b; }
} zcx, Tree[N * 4 + 10];

#define lson (x << 1)
#define rson (x << 1 | 1)

void Update(int x, int nl, int nr) {
    if (zcx.val(nl) <= Tree[x].val(nl) && zcx.val(nr) <= Tree[x].val(nr)) return;
    if (zcx.val(nl) >= Tree[x].val(nl) && zcx.val(nr) >= Tree[x].val(nr)) {
        Tree[x] = zcx;
        return;
    }
    int nm = (nl + nr) >> 1;
    if (zcx.val(nl) >= Tree[x].val(nl) && zcx.val(nm) >= Tree[x].val(nm)) {
        swap(Tree[x], zcx);
        Update(rson, nm + 1, nr);
    } else if (zcx.val(nl) <= Tree[x].val(nl) && zcx.val(nm) <= Tree[x].val(nm)) {
        Update(rson, nm + 1, nr);
    } else if (zcx.val(nm + 1) >= Tree[x].val(nm + 1) && zcx.val(nr) >= Tree[x].val(nr)) {
        swap(Tree[x], zcx);
        Update(lson, nl, nm);
    } else {
        Update(lson, nl, nm);
    }
    /* 下面是写假了的
    if ((zcx.val(nl) >= Tree[x].val(nl)) != (zcx.val(nm) >= Tree[x].val(nm))) {
        if (zcx.val(nm + 1) >= Tree[rson].val(nm + 1) && zcx.val(nr) >= Tree[rson].val(nr))
            Tree[rson] = zcx;
        Update(lson, nl, nm);
    } else {
        if (zcx.val(nl) >= Tree[lson].val(nl) && zcx.val(nm) >= Tree[lson].val(nm))
            Tree[lson] = zcx;
        Update(rson, nm + 1, nr);
    } */
}

double Query(int x, int nl, int nr, int ed) {
    if (nl == nr) return Tree[x].val(ed);
    int nm = (nl + nr) >> 1;
    double qsum = Tree[x].val(ed);
    if (ed <= nm) return max(qsum, Query(lson, nl, nm, ed));
    else return max(qsum, Query(rson, nm + 1, nr, ed));
}

#undef lson
#undef rson

char qrystr[20];
int Qrytimes;
/* 注意题面中 n 不一定是值域大小，这是个坑 */

int main()
{
    freopen("LGOJ4254.in", "r", stdin);
    freopen("LGOJ4254.out", "w", stdout);

    scanf("%d", &Qrytimes);
    while (Qrytimes--) {
        scanf("%s", qrystr);
        if (!strcmp(qrystr, "Query")) {
            int qrypos;
            scanf("%d", &qrypos);
            long long fans = (long long)(Query(1, 1, MAXVAL /* there is no n */, qrypos) / 100.0);
            printf("%lld\n", fans);
        } else {
            scanf("%lf%lf", &zcx.b, &zcx.k);
            zcx.b -= zcx.k; /* 斜率是在 x = 0 处的取值要注意!!! */
            Update(1, 1, MAXVAL);
        }
    }

    return 0;
}