题解：基站网络最小费用问题

算法思路

本题需要从移动公司（第一个基站）通过一系列基站传递网络到UP主家，最小化总费用。采用李超线段树优化动态规划。

1. 问题分析

• 基站按坐标 $x_i$ 递增排列

• 从基站 $j$ 连接到基站 $i$（$x_j < x_i$）的条件：

  • 两个圆相切：$x_i - x_j = \sqrt{r_{2_i}} + r_{1_j}$
  • 费用为：$f_i = f_j + \sqrt{r_{2_i}} + v_i$

• 最终基站 $i$ 能到达UP主家的条件：$x_i + r_{1_i} \geq m$

2. 关键转换

由相切条件：

$$x_i - x_j = \sqrt{r_{2_i}} + r_{1_j}$$

可得：

$$\sqrt{r_{2_i}} = x_i - x_j - r_{1_j}$$

代入费用公式：

$$f_i = f_j + (x_i - x_j - r_{1_j}) + v_i$$

整理得：

$$f_i = \min_{j < i} \{ f_j - x_j - r_{1_j} \} + x_i + v_i $$

3. 动态规划优化

设 $k = \frac{1}{2\sqrt{r_{1_j}}}$，$b = f_j - k \cdot x_j$

使用李超线段树维护直线 $y = kx + b$，在 $x_i$ 处查询最小值。

代码实现

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

const int N = 5e5 + 10;
int n, R[N], V[N];
long long m, X[N], bx[N];
double f[N], ans = 1e18;
long long mp[N];

struct line {
    double k, b = 1e18;
    int id;
    double operator()(const long long &x) {
        return k * mp[x] + b;
    }
} lp[N], t[N * 4];

// 李超线段树：插入直线
void add(int p, int l, int r, int a) {
    int mid = (l + r) >> 1;
    
    if (t[p](mid) > lp[a](mid))
        swap(t[p], lp[a]);
    
    if (l == r) return;
    
    if (lp[a].k > t[p].k) 
        add(p << 1, l, mid, a);
    else 
        add(p << 1 | 1, mid + 1, r, a);
}

// 李超线段树：查询最小值
double ask(int p, int l, int r, int x) {
    if (l == r) 
        return t[p](x);
    
    int mid = (l + r) >> 1;
    double res = (x <= mid) ? ask(p << 1, l, mid, x) 
                           : ask(p << 1 | 1, mid + 1, r, x);
    return min(res, t[p](x));
}

int main() {
    scanf("%d%lld", &n, &m);
    
    // 读入数据
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &X[i]);
        R[i] = read();
        V[i] = read();
        bx[i] = X[i];
    }
    
    // 坐标离散化
    int tot = unique(bx + 1, bx + n + 1) - bx - 1;
    for (int i = 1; i <= n; i++) {
        int orig = X[i];
        X[i] = lower_bound(bx + 1, bx + n + 1, X[i]) - bx;
        mp[X[i]] = orig;
    }
    
    // 初始化DP
    f[1] = V[1];
    lp[1] = line{1.0 / (2.0 * sqrt(R[1])), 
                 f[1] - mp[X[1]] / (2.0 * sqrt(R[1])), 1};
    add(1, 1, n, 1);
    
    // DP转移
    for (int i = 2; i <= n; i++) {
        f[i] = ask(1, 1, n, X[i]) + V[i];
        lp[i] = line{1.0 / (2.0 * sqrt(R[i])), 
                     f[i] - mp[X[i]] / (2.0 * sqrt(R[i]))};
        add(1, 1, n, i);
    }
    
    // 检查能到达UP主家的基站
    for (int i = 1; i <= n; i++) {
        if (mp[X[i]] + R[i] >= m) {
            ans = min(ans, f[i]);
        }
    }
    
    printf("%.3lf\n", ans);
    return 0;
}

关键优化

1. 李超线段树

• 维护直线集合 $y = kx + b$
• 支持在 $x$ 处查询最小值
• 时间复杂度：$O(\log n)$ 每次操作

2. 坐标离散化

• 将 $x_i$ 映射到 $[1, n]$ 区间
• 减少李超线段树的空间开销

3. 数学推导

通过几何关系将原问题转化为线性函数优化问题：

$$f_i = \min_{j < i} \left\{ \frac{x_i}{2\sqrt{r_{1_j}}} + \left(f_j - \frac{x_j}{2\sqrt{r_{1_j}}}\right) \right\} + v_i $$

复杂度分析

• 时间复杂度：$O(n \log n)$
  • 离散化：$O(n \log n)$
  • $n$ 次插入和查询：$O(n \log n)$
• 空间复杂度：$O(n)$

该算法能够高效处理 $5 \times 10^5$ 规模的数据，满足题目要求。