数据结构 - 李超线段树

[HEOI2013] Segment

要求在平面直角坐标系下维护两个操作：

1. 在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$。
2. 给定一个数 $k$，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大的线段的编号。

本题输入强制在线。

输入的第一行是一个整数 $n$，代表操作的个数。

接下来 $n$ 行，每行若干个用空格隔开的整数，第 $i + 1$ 行的第一个整数为 $op$，代表第 $i$ 次操作的类型。

若 $op = 0$，则后跟一个整数 $k$，代表本次操作为查询所所有与直线 $x = (k + lastans - 1) \bmod 39989 + 1$ 相交的线段中，交点纵坐标最大的线段编号。

若 $op = 1$，则后跟四个整数 $x_0, y_0, x_1, y_1$，记 $x_i' = (x_i + lastans - 1) \bmod 39989 + 1$，$y_i' = (y_i + lastans - 1) \bmod 10^9 + 1$。本次操作为插入一条两端点分别为 $(x_0', y_0')$，$(x_1',y_1')$ 的线段。

其中 $lastans$ 为上次询问的答案，初始时，$lastans = 0$。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq k, x_0, x_1 \leq 39989$，$1 \leq y_0, y_1 \leq 10^9$。

题目链接：P4097。

李超线段树是没有 pushdown 的，每次查询时考虑上每一个点的标记，这也叫做标记永久化。

#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 100010, M = 40010;
const double eps = 1e-6;

struct Seg {
    double k, b;
    
    void init(int& x1, int& y1, int& x2, int& y2) {
        if (x1 > x2) swap(x1, x2), swap(y1, y2);
        if (x1 == x2) b = max(y1, y2), k = 0;
        else {
            k = (double)(y1 - y2) / (x1 - x2);
            b = y1 - k*x1;
        }
    }
} seg[N];
int n, idx;

struct Node {
    int l, r;
    int segid;
} tr[M<<2];

int compf(double x) {
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}

double apply(int id, int x) {
    return seg[id].k * x + seg[id].b;
}

struct Comp {
    int x;
    Comp(int x): x(x) {}

    bool operator()(int id1, int id2) const {
        double f1 = apply(id1, x), f2 = apply(id2, x);
        int res = compf(f1 - f2);
        if (res == -1) return true;
        else if (res == 1) return false;
        // 如果编号大就不选
        return id1 > id2;
    }
};

void modify(int u, int l, int r, int id) {
    // debug("Modifing %d which is [%d %d]\n", u, tr[u].l, tr[u].r);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= tr[u].l && tr[u].r <= r) {
        if (!tr[u].segid) return tr[u].segid = id, void();
        if (Comp(mid)(tr[u].segid, id)) swap(tr[u].segid, id);

        if (tr[u].l == tr[u].r) return;

        if (Comp(l)(tr[u].segid, id)) modify(u<<1, l, r, id);
        if (Comp(r)(tr[u].segid, id)) modify(u<<1|1, l, r, id);
        return;
    }

    if (l <= mid) modify(u<<1, l, r, id);
    if (mid+1 <= r) modify(u<<1|1, l, r, id);
}

int query(int u, int l, int r, int x) {
    int res = tr[u].segid;
    if (tr[u].l == x && tr[u].r == x) return res;

    int mid = (tr[u].l + tr[u].r) >> 1;
    if (x <= mid) return max(res, query(u<<1, l, r, x), Comp(x));
    else return max(res, query(u<<1|1, l, r, x), Comp(x));
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) return;
    int mid = (l+r) >> 1;
    build(u<<1, l, mid), build(u<<1|1, mid+1, r);
}

int main() {
    int lastans = 0, op, x, x1, x2, y1, y2;
    build(1, 1, 40000);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &op);
        
        if (op == 0) {
            scanf("%d", &x);
            x = (x + lastans - 1) % 39989 + 1;
            printf("%d\n", lastans = query(1, 1, 40000, x));
        }
        else {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            x1 = (x1 + lastans - 1) % 39989 + 1, x2 = (x2 + lastans - 1) % 39989 + 1;
            y1 = (y1 + lastans - 1) % 1000000000 + 1, y2 = (y2 + lastans - 1) % 1000000000 + 1;
            seg[++idx].init(x1, y1, x2, y2);
            modify(1, x1, x2, idx);
        }
    }
    return 0;
}

[JSOI2008] Blue Mary 开公司

对于一个金融顾问 $i$，他设计的经营方案中，每天的收益都比前一天高，并且均增长一个相同的量 $P_i$。

由于金融顾问的工作效率不高，所以在特定的时间，Blue Mary 只能根据他已经得到的经营方案来估算某一时间的最大收益。由于 Blue Mary 是很没有经济头脑的，所以他在估算每天的最佳获益时完全不会考虑之前的情况，而是直接从所有金融顾问的方案中选择一个在当天获益最大的方案的当天的获益值，例如：

有如下两个金融顾问分别对前四天的收益方案做了设计：

	第一天	第二天	第三天	第四天	$P_i$
顾问 1	$1$	$5 $	$9$	$13$	$4$
顾问 2	$2$	$5$	$8$	$11$	$3$

在第一天，Blue Mary 认为最大收益是 $2$（使用顾问 2 的方案），而在第三天和第四天，他认为最大收益分别是 $9$ 和 $13$（使用顾问 1 的方案）。而他认为前四天的最大收益是：$2 + 5 + 9 + 13 = 29$。

现在你作为 Blue Mary 公司的副总经理，会不时收到金融顾问的设计方案，也需要随时回答 Blue Mary 对某天的“最大收益”的询问（这里的“最大收益”是按照 Blue Mary 的计算方法）。一开始没有收到任何方案时，你可以认为每天的最大收益值是 0。

输入格式

第一行 ：一个整数 $N$，表示方案和询问的总数。

接下来 $N$ 行，每行开头一个单词 Query 或 Project。

若单词为 Query，则后接一个整数 $T$，表示 Blue Mary 询问第 $T$ 天的最大收益。

若单词为 Project，则后接两个实数 $S, P$，表示该种设计方案第一天的收益 $S$，以及以后每天比上一天多出的收益 $P$。

输出格式

对于每一个 Query，输出一个整数，表示询问的答案，并精确到整百元（以百元为单位，例如：该天最大收益为 $210$ 或 $290$ 时，均应该输出 $2$）。没有方案时回答询问要输出 $0$。

数据范围：$1 \leq N \leq 10 ^ 5$，$1 \leq T \leq 5\times 10 ^ 4$，$0 < P < 100$，$|S| \leq 10 ^ 5$。

题目链接：P4254。

本题和上题不同点在于输出的是最大值而不是线段编号，插入的是直线而不是线段。所以一个好消息就是我们不用判断区间了，而且也不用给 max 重新写 Comp 了。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010, M = 50010;
const double eps = 1e-6;

int n;
char op[10];

struct Seg {
    double k, b;

    void init(double k1, double b1) {
        k = k1, b = b1;
    }
} seg[N];
int idx;

int compf(double x) {
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}

double apply(int id, int x) {
    return seg[id].k * x + seg[id].b;
}

struct Node {
    int l, r, segid;
} tr[M<<2];

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) return;
    int mid = (l+r) >> 1;
    build(u<<1, l, mid), build(u<<1|1, mid+1, r);
}

void modify(int u, int id) {
    if (!tr[u].segid) return tr[u].segid = id, void();
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (compf(apply(tr[u].segid, mid) - apply(id, mid)) < 0) swap(id, tr[u].segid);

    if (tr[u].l == tr[u].r) return;

    if (compf(apply(tr[u].segid, tr[u].l) - apply(id, tr[u].l)) < 0) modify(u<<1, id);
    if (compf(apply(tr[u].segid, tr[u].r) - apply(id, tr[u].r)) < 0) modify(u<<1|1, id);
}

double query(int u, int x) {
    double res = apply(tr[u].segid, x);
    if (tr[u].l == x && tr[u].r == x) return res;

    int mid = (tr[u].l + tr[u].r) >> 1;
    if (x <= mid) return max(res, query(u<<1, x));
    else return max(res, query(u<<1|1, x));
}

int main() {
    int x;
    double k, b, y1;
    scanf("%d", &n);
    build(1, 1, 50000);
    for (int i = 1; i <= n; i++) {
        scanf("%s", op);
        if (*op == 'Q') {
            scanf("%d", &x);
            double res = query(1, x);
            printf("%.0lf\n", floor(res / 100));
        }
        else {
            scanf("%lf%lf", &y1, &k);
            b = y1 - k;
            seg[++idx].init(k, b);
            modify(1, idx);
        }
    }
    return 0;
}

[CEOI2017] Building Bridges

有 $n$ 根柱子依次排列，每根柱子都有一个高度。第 $i$ 根柱子的高度为 $h_i$。

现在想要建造若干座桥，如果一座桥架在第 $i$ 根柱子和第 $j$ 根柱子之间，那么需要 $(h_i-h_j)^2$ 的代价。

在造桥前，所有用不到的柱子都会被拆除，因为他们会干扰造桥进程。第 $i$ 根柱子被拆除的代价为 $w_i$，注意 $w_i$ 不一定非负，因为可能政府希望拆除某些柱子。

现在政府想要知道，通过桥梁把第 $1$ 根柱子和第 $n$ 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

对于 $100\%$ 的数据，有 $2\le n\le 10^5;0\le h_i,\vert w_i\vert\le 10^6$。

题目链接：P4655。

首先本题的 DP 方程巨简单。

$$f_i=\min_{j<i}\{ f_j+(h_i-h_j)^2+\sum_{k=j+1}^{i-1} w_k\}$$

设数列 $\{w_i\}$ 的前缀和数列是 $\{S_i\}$，然后对于每个 $i$ 来说，把只包含 $i$ 的式子提出来，变形为：

$$f_i=\min_{j<i}\{-2h_jh_i+f_j+h_j^2-S_j\}+h_i^2+S_{i-1}$$

所以我们的自变量是 $h_i$，把 $\min$ 里面的式子看成直线，用李超树求最小值。

我刚开始写的时候最大值写习惯了被坑了好几次。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define L(u) (tr[u].l)
#define R(u) (tr[u].r)

typedef long long LL;
const int N = 100010, M = 1000010, MaxH = 1000000;
const LL INF = 1e18;
int n;
LL s[N], f[N], h[N];

struct Seg {
    LL k, b = INF;

    void init(LL k1, LL b1) {
        k = k1, b = b1;
    }
} seg[N];

struct Node {
    int l, r;
    int segid;
} tr[M<<2];

LL apply(int id, LL x) {
    return seg[id].k * x + seg[id].b;
}

void build(int u, int l, int r) {
    tr[u].l = l, R(u) = r;
    if (l == r) return;
    int mid = (l+r) >> 1;
    build(u<<1, l, mid), build(u<<1|1, mid+1, r);
}

void modify(int u, int id) {
    int mid = (L(u) + R(u)) >> 1;
    if (!tr[u].segid) return tr[u].segid = id, void();

    // 注意这里的不等号方向, 一定要记住自己在写最大值还是最小值
    if (apply(tr[u].segid, mid) > apply(id, mid)) swap(id, tr[u].segid);
    if (L(u) == R(u)) return;

    if (apply(tr[u].segid, L(u)) > apply(id, L(u))) modify(u<<1, id);
    else if (apply(tr[u].segid, R(u)) > apply(id, R(u))) modify(u<<1|1, id);
}

LL query(int u, LL x) {
    LL res = apply(tr[u].segid, x);
    if (L(u) == R(u)) return res;

    int mid = (L(u) + R(u)) >> 1;
    if (x <= mid) return min(res, query(u<<1, x));
    else return min(res, query(u<<1|1, x));
}

int main() {
    scanf("%d", &n);
    build(1, 1, MaxH);
    for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);
    for (int i = 1; i <= n; i++) scanf("%lld", &s[i]), s[i] += s[i-1];

    f[1] = 0;
    seg[1].init(-2*h[1], f[1]+h[1]*h[1]-s[1]);
    modify(1, 1);

    for (int i = 2; i <= n; i++) {
        f[i] = query(1, h[i]) + (LL)h[i]*h[i] + s[i-1];
        seg[i].init(-2*h[i], f[i]+(LL)h[i]*h[i]-s[i]);
        modify(1, i);
    }

    printf("%lld\n", f[n]);
    return 0;
}

[NOI2007] 货币兑换

小 Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A 纪念券（以下简称 A 券）和 B 纪念券（以下简称 B 券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。

每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 $K$ 天中 A 券和 B 券的价值分别为 $A_K$ 和 $B_K$（元/单位金券）。

为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。

比例交易法分为两个方面：

a) 卖出金券：顾客提供一个 $[0, 100]$ 内的实数 $OP$ 作为卖出比例，其意义为：将 $OP\%$ 的 A 券和 $OP\%$ 的 B 券以当时的价值兑换为人民币；

b) 买入金券：顾客支付 $IP$ 元人民币，交易所将会兑换给用户总价值为 $IP$ 的金券，并且，满足提供给顾客的 A 券和 B 券的比例在第 $K$ 天恰好为 $\mathrm{Rate}_ K$；

例如，假定接下来 $3$ 天内的 $A_K,B_K,\mathrm{Rate}_ K$ 的变化分别为：

时间	$A_K$	$B_K$	$\mathrm{Rate}_ K$
第一天	$1$	$1$	$1$
第二天	$1$	$2$	$2$
第三天	$2$	$2$	$3$

假定在第一天时，用户手中有 $100$ 元人民币但是没有任何金券。

用户可以执行以下的操作：

时间	用户操作	人民币(元)	A 券的数量	B 券的数量
开户	无	$100$	$0$	$0$
第一天	买入 $100$ 元	$0$	$50$	$50$
第二天	卖出 $50\%$	$75$	$25$	$25$
第二天	买入 $60$ 元	$15$	$55$	$40$
第三天	卖出 $100\%$	$205$	$0$	$0$

注意到，同一天内可以进行多次操作。

小 Y 是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来 $N$ 天内的 A 券和 B 券的价值以及 $\mathrm{Rate}$。他还希望能够计算出来，如果开始时拥有 $S$ 元钱，那么 $N$ 天后最多能够获得多少元钱。

输入格式

第一行两个正整数 $N,S$，分别表示小 Y 能预知的天数以及初始时拥有的钱数。

接下来 $N$ 行，第 $K$ 行三个实数 $A_K,B_K,\mathrm{Rate} _ K$ ，意义如题目中所述。

输出格式

只有一个实数 $\mathrm{MaxProfit}$，表示第 $N$ 天的操作结束时能够获得的最大的金钱数目。答案保留 $3$ 位小数。

对于 $100\%$ 的测试数据，满足：

$0 < A_K \leq 10$，$0 < B_K\le 10$，$0 < \mathrm{Rate}_K \le 100$，$\mathrm{MaxProfit} \leq 10^9$。

必然存在一种最优的买卖方案满足：

每次买进操作使用完所有的人民币，每次卖出操作卖出所有的金券。

题目链接：P4027。

最后一句话特别重要，要没有反正我做不出来，有了照样做不出来。

首先列方程，计算出如果有 $f_j$ 元在第 $j$ 天分别买进多少券，设 $A,B$ 买入 $a_j,b_j$ 单位，$R_j$ 表示 $\text{Rate}_j$，首先有 $a=bR_j$，其次有 $aA_j+bB_j=x$，所以我们可以解出来：

$$a_j=\frac{R_jf_j}{R_jA_j+B_j},b_j=\frac{f_j}{R_jA_j+B_j}$$

然后由每次操作要么全部满入，要么全部卖出，那么就可以列出：

$$f_i=\max_{j<i}\{a_jA_i+b_jB_i\}=B_i\cdot \max_{j<i}\{a_j\frac{A_i}{B_i} +b_j\}$$

将 $A_i/B_i$ 看作自变量，$a_j$ 看作斜率，所以又可以用李超树做了。这里我们可以把自变量离散化一下，一个是防止精度问题，另一个是既然是值域线段树如果是实数到底开多少点如果不离散化也无从得知。

当然，也可以选择什么都不买，即 $f_i=\max\{f_i,f_{i-1}\}$ 这里直接用滚动数组优化了，也就是压根不开 $f$ 这个数组，直接用单个变量。这里写一个动态开点的李超树练习一下。

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010;
const double eps = 1e-7;
int n, m;
double k[N], t[N], A[N], B[N], C[N], R[N];
vector<double> nums;

struct Node {
    int lson, rson;
    int id;
} tr[N];
int root = 1, idx = 1;

bool compf(double a, double b) {
    double x = a - b;
    if (fabs(x) < eps) return false;
    return x < 0;
}

double apply(int id, int x) {
    return nums[x-1] * k[id] + t[id];
}

int find(double x) {
    // 我这里一开始没加自定义比较 WA 了好多次
    return lower_bound(nums.begin(), nums.end(), x, compf) - nums.begin() + 1;
}

double query(int& u, int L, int R, int x) {
    int mid = (L + R) >> 1;
    double res = apply(tr[u].id, x);

    if (x <= mid && tr[u].lson) return max(res, query(tr[u].lson, L, mid, x));
    else if (mid+1 <= x && tr[u].rson) return max(res, query(tr[u].rson, mid+1, R, x));
    else return res;
}

void modify(int& u, int L, int R, int id) {
    if (!u) u = ++idx;
    if (!tr[u].id) return tr[u].id = id, void();

    int mid = (L + R) >> 1;
    if (compf(apply(tr[u].id, mid), apply(id, mid))) swap(id, tr[u].id);
    if (L == R) return;

    if (compf(apply(tr[u].id, L), apply(id, L))) modify(tr[u].lson, L, mid, id);
    if (compf(apply(tr[u].id, R), apply(id, R))) modify(tr[u].rson, mid+1, R, id);
}

int main() {
    double f;
    scanf("%d%lf", &n, &f);

    for (int i = 1; i <= n; i++) {
        scanf("%lf%lf%lf", &A[i], &B[i], &R[i]);
        C[i] = A[i] / B[i];
        nums.emplace_back(C[i]);
    }

    sort(nums.begin(), nums.end(), compf);
    nums.erase(unique(nums.begin(), nums.end(), [](double a, double b){ return fabs(a-b) < eps; }), nums.end());
    m = nums.size();

    for (int i = 1; i <= n; i++) {
        f = max(f, B[i] * query(root, 1, m, find(C[i])));
        double a = R[i]*f/(R[i]*A[i]+B[i]), b = f/(R[i]*A[i]+B[i]);
        k[i] = a, t[i] = b;
        modify(root, 1, m, i);
    }

    printf("%.3lf\n", f);
    return 0;
}