李超线段树李超线段树

李超线段树

也可以叫李超树，用于维护线段、直线，并求出最值，基于标记永久化

通常李超树的题 (x) 的范围可以接受

• 标记永久化：省去 pushdown ，修改时一路更改被影响到的点，

  询问时一路累加路上的标记，在一些地方也能省去 pushup

维护直线

[JSOI2008]Blue Mary开公司

将这题转换为两个操作：

• 加入一条直线
• 查询所有直线在 (x=T) 时取到的最大值。

用 (tg) 维护区间内在 (x=mid) 时 (y) 值最大的函数编号，每次插入只需分类讨论。这里有两种方法

假设插入函数为 (x) ，当前区间 (tg) 对应函数为 (y) ，当前区间是 ([l,r]) ，中点是 (mid)

sol 1

1. (x) 的斜率大于 (y) 的

   • (x) 在 (mid) 处的取值大于 (y) 的。 (y) 在右半区间一定不会优于 (x) 。

     用 (y) 去更新左区间(注意是用 (y) 更新)。 (tg) 更新为 (x) 的编号

   • 否则。 (x) 在左半区间一定不会优于 (y) ，用 (x) 去更新右半区间。

2. 否则

   • (x) 在 (mid) 处的取值大于 (y) 的。(y) 在左半区间一定不会优于 (x)

     用 (y) 去更新右半区间。(tg) 更新为 (x) 的编号

   • 否则。(x) 在右半区间一定不会优于 (y) ，用 (x) 去更新左半区间

这种分类可得：每一次只会选择一种情况。最终保证单次修改复杂度为 (O(log n))

sol 2

1. (x) 在 (l,r) 两处的取值都大于 (y) 的，直接更新 (tg) ，返回

2. 比较 (x,y) 在 (mid) 的取值，更新 (tg) ，以及用于更新的线段。

   • 实现比较巧妙：将 (y) 定义为引用变量，如果 (x) 在 (mid) 处取值大于 (y) 的就 swap(x, y)

     得到 (y) 是较优的那个， (x) 用于更新。

3. (x) 在 (l) 处取值大于 (y) 的， (x) 可能在左区间更优，更新左区间

4. (x) 在 (r) 处取值大于 (y) 的， (x) 可能在右区间更优，更新右区间。

同 sol1 的分析，复杂度为 (O(log n))

code

最终 sol2 更加简洁，常数更小，此处用 sol2 实现

查询类似单点查询，将路上所有直线在 (x=T) 取到的值都取最值

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long uLL;
typedef long double LD;
typedef long long LL;
typedef double db;
const int N = 2e5 + 5;
int n, cnt, tg[N << 2];
db ans;
char op[15];
struct L {
    db k, b;
} a[N];
inline db F(int i, int x) { return a[i].k * (x - 1) + a[i].b; }
#define ls (rt << 1)
#define rs (rt << 1 | 1)
void mdy(int x, int l, int r, int rt) {
    register int mid = l + r >> 1, &y = tg[rt];
    if (F(x, l) >= F(y, l) && F(x, r) >= F(y, r)) { tg[rt] = x; return; }
    if (l == r) return;
    if (F(x, mid) > F(y, mid)) swap(x, y);
    if (F(x, l) > F(y, l)) mdy(x, l, mid, ls);
    if (F(x, r) > F(y, r)) mdy(x, mid + 1, r, rs);
}
void ask(int p, int l, int r, int rt) {
    ans = max(ans, F(tg[rt], p));
    if (l == r) return;
    register int mid = l + r >> 1;
    if (p <= mid) ask(p, l, mid, ls);
    else ask(p, mid + 1, r, rs);
}
#undef ls
#undef rs
int main() {
    scanf("%d", &n);
    for (int Ti = n; Ti--; ) {
        scanf("%s", op);
        if (op[0] == 'Q') {
            register int t;
            scanf("%d", &t);
            ans = 0;
            ask(t, 1, 200000, 1);
            printf("%dn", (int)ans / 100);
        } else {
            ++cnt;
            scanf("%lf%lf", &a[cnt].b, &a[cnt].k);
            mdy(cnt, 1, 200000, 1);
        }
    }
}

维护线段

[HEOI2013]Segment

相当于多了一个定义域 (xin[x_0,x_1]) ，类似区间修改

先找到线段树中被修改区间包含的区间，再用维护直线的方法下传、更新 (tg) 。

复杂度分析：首先将查询分到 (log n) 个线段树上区间，对于这些区间又要 (O(log n)) 的时间下传

单次修改 (O(nlog^2 n))

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long uLL;
typedef long double LD;
typedef long long LL;
typedef double db;
const int N = 1e5 + 5, M = 39989, P = 1e9;
int n, cnt, tg[N << 2], ans;
db mxx;
struct L { db k, b; } p[N];
inline db F(int i, int x) { return p[i].k * x + p[i].b; }
#define ls (rt << 1)
#define rs (rt << 1 | 1)
void mdy(int ql, int qr, int x, int l, int r, int rt) {
    if (ql > r || l > qr) return;
    register int mid = l + r >> 1;
    if (ql <= l && r <= qr) {
        register int &y = tg[rt];
        if (F(x, l) > F(y, l) && F(x, r) > F(y, r)) {
            tg[rt] = x;
            return;
        }
        if (l == r) return;
        if (F(x, mid) > F(y, mid)) swap(x, y);
        if (F(x, l) > F(y, l)) mdy(ql, qr, x, l, mid, ls);
        if (F(x, r) > F(y, r)) mdy(ql, qr, x, mid + 1, r, rs);
        return;
    }
    mdy(ql, qr, x, l, mid, ls);
    mdy(ql, qr, x, mid + 1, r, rs);
}
inline void cmx(int i, int x) {
    register db v = F(i, x);
    if (v > mxx || (v == mxx && i < ans)) ans = i, mxx = v;
}
void ask(int x, int l, int r, int rt) {
    cmx(tg[rt], x);
    if (l == r) return;
    register int mid = l + r >> 1;
    if (x <= mid) ask(x, l, mid, ls);
    else ask(x, mid + 1, r, rs);
}
#undef ls
#undef rs
int main() {
    scanf("%d", &n);
    for (int Ti = n, ls = 0, op; Ti; Ti--) {
        scanf("%d", &op);
        if (!op) {
            register int t;
            scanf("%d", &t);
            t = (t + ls - 1) % M + 1;
            mxx = 0;
            ans = 0;
            ask(t, 1, M, 1);
            printf("%dn", ls = ans);
        } else {
            register int xx, yy, x2, y2;
            scanf("%d%d%d%d", &xx, &yy, &x2, &y2);
            xx = (xx + ls - 1) % M + 1;
            x2 = (x2 + ls - 1) % M + 1;
            yy = (yy + ls - 1) % P + 1;
            y2 = (y2 + ls - 1) % P + 1;
            if (xx > x2) swap(xx, x2), swap(yy, y2);
            ++cnt;
            if (xx == x2) p[cnt].k = 0, p[cnt].b = max(yy, y2);
            else p[cnt].k = 1.0 * (yy - y2) / (1.0 * xx - x2), p[cnt].b = 1.0 * yy - p[cnt].k * xx;
            mdy(xx, x2, cnt, 1, M, 1);
        }
    }
}

强行结合

[SDOI2016]游戏

查询上链？直接树剖。

同时根据 (lca) 将询问分成两段、两条直线。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long uLL;
typedef long double LD;
typedef long long LL;
typedef double db;
char buf[100000], *S = buf, *T = buf;
inline char G() { return S == T && (T = (S = buf) + fread(buf, 1, 100000, stdin), S == T) ? EOF : *S++; }
inline int Rd() {
    register int x = 0, C = G(), f = 1;
    for (; C < '0' || C > '9'; C = G()) f &= C ^ '-';
    for (; C > '/' && C < ':'; C = G()) x = (x << 1) + (x << 3) + (C ^ 48);
    return f ? x : -x;
}
const LL INF = 123456789123456789ll;
const int N = 1e5 + 5;
int n, Ti, lst[N], Ecnt, clk, tot;
int dfn[N], fa[N], dep[N], sz[N], son[N], top[N], rk[N];
int tg[N << 2];
LL dis[N], mn[N << 2], ans;
struct L { LL k, b; } p[N << 1];
struct Ed { int to, nxt; LL qz; } e[N << 1];
inline LL F(int i, int x) { return p[i].k * dis[rk[x]] + p[i].b; }
inline void Ae(int fr, int go, int vl) { e[++Ecnt] = (Ed){ go, lst[fr], 1ll * vl }, lst[fr] = Ecnt; }
void dfs1(int u, int ff) {
    fa[u] = ff, dep[u] = dep[ff] + (sz[u] = 1);
    for (int i = lst[u], v; i; i = e[i].nxt)
        if ((v = e[i].to) ^ ff) {
            dis[v] = dis[u] + e[i].qz;
            dfs1(v, u), sz[u] += sz[v];
            if (sz[v] > sz[son[u]]) son[u] = v;
        }
}
void dfs2(int u, int nw) {
    dfn[u] = ++clk, rk[clk] = u, top[u] = nw;
    if (son[u]) dfs2(son[u], nw);
    for (int i = lst[u], v; i; i = e[i].nxt)
    if ((v = e[i].to) ^ fa[u] && v ^ son[u]) dfs2(v, v);
}
#define ls (rt << 1)
#define rs (rt << 1 | 1)
void bui(int l, int r, int rt) {
    mn[rt] = INF, tg[rt] = 1;
    if (l == r) return;
    register int mid = l + r >> 1;
    bui(l, mid, ls), bui(mid + 1, r, rs);
}
inline void Up(int rt) { mn[rt] = min(mn[rt], min(mn[ls], mn[rs])); }
void mdy(int ql, int qr, int x, int l, int r, int rt) {
    if (ql > r || l > qr) return;
    register int mid = l + r >> 1;
    if (ql <= l && r <= qr) {
        mn[rt] = min(mn[rt], min(F(x, l), F(x, r)));
        register int &y = tg[rt];
        if (F(x, l) <= F(y, l) && F(x, r) <= F(y, r)) { tg[rt] = x; return; }
        if (l == r) return;
        if (F(x, mid) < F(y, mid)) swap(x, y);
        if (F(x, l) < F(y, l)) mdy(ql, qr, x, l, mid, ls);
        if (F(x, r) < F(y, r)) mdy(ql, qr, x, mid + 1, r, rs);
        return Up(rt);
    }
    mdy(ql, qr, x, l, mid, ls), mdy(ql, qr, x, mid + 1, r, rs), Up(rt);
}
void ask(int ql, int qr, int l, int r, int rt) {
    if (ql > r || l > qr) return;
    if (ql <= l && r <= qr) { ans = min(ans, mn[rt]); return; }
    register int mid = l + r >> 1;
    ans = min(ans, min(F(tg[rt], max(l, ql)), F(tg[rt], min(r, qr))));
    ask(ql, qr, l, mid, ls), ask(ql, qr, mid + 1, r, rs);
}
#undef ls
#undef rs
inline int LCA(int x, int y) {
    for (; top[x] ^ top[y]; x = fa[top[x]])
        if (dep[top[x]] < dep[top[y]]) x ^= y ^= x ^= y;
    return dep[x] < dep[y] ? x : y;
}
inline void change(int x, int y, int z) {
    for (; top[x] ^ top[y]; x = fa[top[x]])
        mdy(dfn[top[x]], dfn[x], z, 1, n, 1);
    mdy(dfn[y], dfn[x], z, 1, n, 1);
}
inline LL query(int x, int y) {
    for (ans = INF; top[x] ^ top[y]; x = fa[top[x]]) {
        if (dep[top[x]] < dep[top[y]]) x ^= y ^= x ^= y;
        ask(dfn[top[x]], dfn[x], 1, n, 1);
    }
    if (dep[x] < dep[y]) x ^= y ^= x ^= y;
    ask(dfn[y], dfn[x], 1, n, 1);
    return ans;
}
int main() {
    n = Rd(), Ti = Rd();
    for (int i = 1, u, v, w; i < n; i++) {
        u = Rd(), v = Rd(), w = Rd();
        Ae(u, v, w), Ae(v, u, w);
    }
    dfs1(1, 0), dfs2(1, 1), bui(1, n, 1);
    p[++tot] = (L){ 0, INF };
    for (int op, x, y, a, b, l; Ti--; ) {
        op = Rd(), x = Rd(), y = Rd();
        if (op == 1) {
            a = Rd(), b = Rd(), l = LCA(x, y);
            p[++tot] = (L){ -1ll * a, dis[x] * a + b };
            change(x, l, tot);
            p[++tot] = (L){ 1ll * a, (dis[x] - dis[l] * 2) * a + b };
            change(y, l, tot);
        } else printf("%lldn", query(x, y));
    }
}

维护凸包 & 优化 dp

咕了，不会，去学 dp 了。。。