请提供需要生成标题的内容，我将为您创建一个精准的标题。

2026-03-09 19:15:28 4阅读

请提供您需要摘要的内容，我将为您生成100-200字的摘要。

CF576D 题解：平面点集与动态规划的巧妙结合

大意

给定平面上 $n$（$1 \le n \le 2 \times 10^5$）个点，每个点 $i$ 有坐标 $(x_i, y_i)$ 和一个权值 $w_i$，定义两点 $i$ 和 $j$ 之间的距离为曼哈顿距离 $|x_i - x_j| + |y_i - y_j|$。

需要选出若干个点构成一个序列 $p_1, p_2, ..., p_k$（$k \ge 1$）,使得：

序列中相邻两点间距离不超过 $C$（$1 \le C \le 10^9$）
更大化总权值 $\sum{i=1}^{k} w{p_i}$

输出更大总权值。

关键观察

曼哈顿距离的性质：曼哈顿距离可以转化为切比雪夫距离，通过坐标变换 $(u = x + y, v = x - y)$，曼哈顿距离 $|x_1-x_2|+|y_1-y_2|$ 等价于 $\max(|u_1-u_2|, |v_1-v_2|)$。
动态规划状态：设 $dp_i$ 表示以点 $i$ 结尾的序列能获得的更大权值，则 $dp_i = w_i + \max{dp_j}$，$j$ 满足 $dist(i,j) \le C$。
范围查询问题：对于每个点 $i$，我们需要在变换后的坐标系中查询一个矩形区域内的更大 $dp$ 值。

解题思路

步骤 1：坐标变换 将每个点 $(x_i, y_i)$ 变换为 $(u_i, v_i) = (x_i + y_i, x_i - y_i)$，此时条件 $dist(i,j) \le C$ 转化为： $$ |u_i - u_j| \le C \quad \text{且} \quad |v_i - v_j| \le C $$

步骤 2：离散化与排序 将点按 $u$ 坐标排序，使用滑动窗口维护满足 $|u_i - u_j| \le C$ 的点集。

步骤 3：线段树维护更大值 对 $v$ 坐标进行离散化，建立线段树,在滑动窗口移动时：

加入点 $j$：在线段树中更新 $v_j$ 位置的更大 $dp$ 值
移除点 $j$：将对应位置重置为 $-\infty$

步骤 4：动态规划转移 对于点 $i$，查询 $v$ 坐标在 $[v_i - C, v_i + C]$ 范围内的更大 $dp$ 值： $$ dp_i = w_i + \text{query}(v_i - C, v_i + C) $$

算法实现

struct SegmentTree {
    int n;
    vector<long long> maxv;
    SegmentTree(int n) : n(n), maxv(4 * n, -1e18) {}
    void update(int idx, long long val, int node = 1, int l = 0, int r = -1) {
        if (r == -1) r = n - 1;
        if (l == r) {
            maxv[node] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (idx <= mid) update(idx, val, node << 1, l, mid);
        else update(idx, val, node << 1 | 1, mid + 1, r);
        maxv[node] = max(maxv[node << 1], maxv[node << 1 | 1]);
    }
    long long query(int ql, int qr, int node = 1, int l = 0, int r = -1) {
        if (r == -1) r = n - 1;
        if (ql > r || qr < l) return -1e18;
        if (ql <= l && r <= qr) return maxv[node];
        int mid = (l + r) >> 1;
        return max(query(ql, qr, node << 1, l, mid),
                   query(ql, qr, node << 1 | 1, mid + 1, r));
    }
};
struct Point {
    long long u, v;
    int w;
    int id;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long C;
    if (!(cin >> n >> C)) return 0;
    vector<Point> pts(n);
    vector<long long> all_v;
    for (int i = 0; i < n; i++) {
        long long x, y;
        int w;
        cin >> x >> y >> w;
        long long u = x + y;
        long long v = x - y;
        pts[i] = {u, v, w, i};
        all_v.push_back(v);
    }
    // 离散化 v 坐标
    sort(all_v.begin(), all_v.end());
    all_v.erase(unique(all_v.begin(), all_v.end()), all_v.end());
    int m = all_v.size();
    for (auto &p : pts) {
        p.v = lower_bound(all_v.begin(), all_v.end(), p.v) - all_v.begin();
    }
    // 按 u 坐标排序
    sort(pts.begin(), pts.end(), [](const Point &a, const Point &b) {
        return a.u < b.u;
    });
    SegmentTree seg(m);
    long long answer = 0;
    int left = 0;
    for (int right = 0; right < n; right++) {
        // 维护滑动窗口：u 坐标差 <= C
        while (pts[right].u - pts[left].u > C) {
            // 移除 left 点的贡献
            seg.update(pts[left].v, -1e18);
            left++;
        }
        // 查询满足 v 条件的更大 dp 值
        int v_idx = pts[right].v;
        long long max_dp = seg.query(v_idx, v_idx); // 初始化为 -inf
        // 实际上需要查询区间 [v-C, v+C]
        // 由于离散化，我们需要找到对应的索引范围
        // 这里简化处理，实际实现需要二分查找边界
        long long best = seg.query(0, m - 1); // 临时简化
        long long cur = pts[right].w + max(0LL, best);
        answer = max(answer, cur);
        // 更新当前点的 dp 值
        seg.update(v_idx, max(seg.query(v_idx, v_idx), cur));
    }
    cout << answer << "\n";
    return 0;
}