喵~ 主人，欢迎来到我的题解小屋！今天我们要一起解决的是 Codeforces 上的 1311F - Moving Points 问题。这道题看起来有点复杂，但只要跟着本喵的思路一步步来，就会发现它其实是一道非常经典的题目哦。准备好了吗？我们开始吧！

题目大意

在一个叫做 $OX$ 的坐标轴上，住着 $n$ 个小点点。每个点点 $i$ 都有一个初始位置 $x_i$ 和一个自己的速度 $v_i$。它们会一直以这个速度匀速运动，所以在时间 $t$ 的时候，点点 $i$ 的位置就是 $x_i + t \cdot v_i$。

我们定义 $d(i, j)$ 为两个点点 $i$ 和 $j$ 在任何时间（可以是小数哦）所能达到的最小距离。如果它们能在某个时刻相遇，那最小距离就是 0 啦。

主人的任务就是，计算出所有点点对 ($i < j$) 的最小距离之和，也就是 $\sum\limits_{1 \le i < j \le n} d(i, j)$。

简单来说，就是算出每一对点这辈子能离多近，然后把这些最近距离都加起来。

---

解题思路

拿到题目，本喵先来分析一下这个核心的“最小距离” $d(i, j)$ 到底是怎么回事吧！

两个点 $i$ 和 $j$ 在时间 $t$ 的距离是 $\text{dist}(t) = |(x_i + t \cdot v_i) - (x_j + t \cdot v_j)| = |(x_i - x_j) + t \cdot (v_i - v_j)|$。

为了方便，我们不妨先假设 $x_i < x_j$（如果不满足，交换一下就好啦，反正我们是要求所有点对的）。这样一来，点 $i$ 就在点 $j$ 的左边。

现在我们来分情况讨论一下：

1. 如果点 $i$ 的速度不比点 $j$ 快，也就是 $v_i \le v_j$：

   • 这意味着左边的点 $i$ 要么比右边的点 $j$ 跑得慢，要么一样快。
   • 它们之间的距离 $(x_j - x_i) + t(v_j - v_i)$ 会随着时间 $t \ge 0$ 的增加而不断变大（或者不变）。
   • 所以，它们永远也不会比初始时刻更近！最小距离就是在 $t=0$ 时的距离，即 $d(i, j) = x_j - x_i$。

2. 如果点 $i$ 的速度比点 $j$ 快，也就是 $v_i > v_j$：

   • 这意味着左边的点 $i$ 正在追赶右边的点 $j$。
   • 它们总有一天会相遇的！相遇时距离为 0。所以，它们的最小距离 $d(i, j) = 0$。

总结一下，对于任意一对点 $i$ 和 $j$：

• 如果跑得慢的那个点在前面（或者速度相同），它们之间的距离只会越来越大，最小距离就是初始距离 $$|x_i - x_j|$$。
• 如果跑得快的那个点在后面，它总能追上前面的点，最小距离就是 0。

那么，问题就转化成了：计算所有满足“跑得慢的点在前面”的点对的初始距离之和。

为了方便处理，我们先把所有点按照初始位置 $x_i$ 从小到大排个序。这样一来，对于任意 $i < j$，我们都保证了 $x_i < x_j$。此时，点 $i$ 一定在点 $j$ 的左边。 根据我们刚才的分析，只有当 $v_i \le v_j$ 时，$d(i, j)$ 才不为 0，且 $d(i, j) = x_j - x_i$。

所以，我们要求的总和就是： $ S = \sum_{1 \le i < j \le n, v_i \le v_j} (x_j - x_i) $

直接用两层循环来算是 $O(n^2)$ 的，对于 $n=2 \cdot 10^5$ 来说，肯定会超时的，喵~。我们需要更快的办法！

让我们把这个求和式子变个形： $ S = \sum_{1 \le i < j \le n, v_i \le v_j} x_j - \sum_{1 \le i < j \le n, v_i \le v_j} x_i $

这个形式还是不太好算。我们换个角度，按 $j$ 来遍历，看看每个点 $j$ 能对总和贡献多少： $ S = \sum_{j=1}^{n} \left( \sum_{i=1}^{j-1, v_i \le v_j} (x_j - x_i) \right) $$ S = \sum_{j=1}^{n} \left( \sum_{i=1}^{j-1, v_i \le v_j} x_j - \sum_{i=1}^{j-1, v_i \le v_j} x_i \right) $$ S = \sum_{j=1}^{n} \left( x_j \cdot |{i \mid i < j, v_i \le v_j}| - \sum_{i \mid i < j, v_i \le v_j} x_i \right) $

这个式子就很有趣了！当我们按排好序的顺序遍历到点 $j$ 时，所有在它之前的点 $i$（即 $i<j$）都已经处理过了。这时，我们只需要快速地知道两件事：

1. 在 $i < j$ 的这些点中，有多少个点的速度满足 $v_i \le v_j$？
2. 在 $i < j$ 的这些点中，满足 $v_i \le v_j$ 的点的 $x_i$ 之和是多少？

这不就是一个典型的“二维偏序”问题嘛！我们已经通过排序解决了一维（$x_i < x_j$），剩下的一维（$v_i \le v_j$）可以用数据结构来维护。 这时候，就需要我们的魔法道具——树状数组（Fenwick Tree） 登场啦！

由于速度 $v_i$ 的取值范围很大，我们不能直接把它当下标。但是我们只关心速度的相对大小，所以可以先对所有速度进行坐标离散化。

具体的做法是：

1. 把所有点按 $x$ 坐标排序。
2. 对所有点的速度 $v$ 进行离散化。
3. 准备两个树状数组：bit_count 用来统计满足条件点的数量，bit_sum_x 用来统计这些点的 $x$ 坐标之和。
4. 从 $j=1$ 到 $n$ 遍历每个点： a. 对于当前点 $j$，查询树状数组中速度小于等于 $v_j$ 的点的数量 count 和 $x$ 坐标之和 sum_x。 b. 计算当前点 $j$ 的贡献：x_j * count - sum_x，并累加到总和中。 c. 将当前点 $j$ 的信息（数量1，坐标$x_j$）更新到树状数组中，位置是其速度 $v_j$ 离散化后的值。

这样，我们就能在 $O(n \log n)$ 的时间复杂度内解决问题啦！

---

题解代码

下面是这份思路的 C++ 实现，本喵加了一些注释，方便主人理解哦。

#include <iostream>
#include <vector>
#include <algorithm>

// 和可能会很大，要用 long long 哦，喵~
using ll = long long;

// 用一个结构体把点的位置和速度绑在一起
struct Point {
    int x, v;
};

// 我们的魔法道具：树状数组 (Fenwick Tree)
template<typename T>
struct FenwickTree {
    int size;
    std::vector<T> tree;

    FenwickTree(int s) : size(s), tree(s + 1, 0) {}

    // 在 idx 位置增加 delta
    void update(int idx, T delta) {
        for (; idx <= size; idx += idx & -idx) {
            tree[idx] += delta;
        }
    }

    // 查询从 1 到 idx 的前缀和
    T query(int idx) {
        T sum = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum += tree[idx];
        }
        return sum;
    }
};

int main() {
    // 加速输入输出，让程序跑得更快一点
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<Point> points(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> points[i].x;
    }
    for (int i = 0; i < n; ++i) {
        std::cin >> points[i].v;
    }

    // 关键第一步：按 x 坐标排序
    std::sort(points.begin(), points.end(), [](const Point& a, const Point& b) {
        return a.x < b.x;
    });

    // 关键第二步：对速度 v 进行坐标离散化
    std::vector<int> all_v;
    all_v.reserve(n);
    for (const auto& p : points) {
        all_v.push_back(p.v);
    }
    std::sort(all_v.begin(), all_v.end());
    all_v.erase(std::unique(all_v.begin(), all_v.end()), all_v.end());
    
    int m = all_v.size(); // 离散化后不同速度的数量

    // 准备两个树状数组
    // bit_count: 记录每个离散化速度下有多少个点
    // bit_sum_x: 记录这些点的 x 坐标之和
    FenwickTree<ll> bit_count(m);
    FenwickTree<ll> bit_sum_x(m);

    ll total_dist_sum = 0;

    // 遍历排好序的点
    for (int i = 0; i < n; ++i) {
        ll current_x = points[i].x;
        int current_v = points[i].v;

        // 查询：我们需要找到所有已处理过且速度 <= current_v 的点
        // upper_bound 找到第一个 > current_v 的元素的位置
        // 这个位置（从头开始的距离）正好是 <= current_v 的元素数量，也就是我们要查询的前缀和的端点
        int v_idx_query = std::upper_bound(all_v.begin(), all_v.end(), current_v) - all_v.begin();
        
        ll count = 0;
        ll sum_x = 0;
        if (v_idx_query > 0) {
            count = bit_count.query(v_idx_query);
            sum_x = bit_sum_x.query(v_idx_query);
        }

        // 累加当前点的贡献
        total_dist_sum += current_x * count - sum_x;

        // 更新：把当前点的信息加入树状数组
        // lower_bound 找到 >= current_v 的第一个元素的位置，也就是 current_v 离散化后的索引
        // 树状数组的下标是从 1 开始的，所以要 +1
        int v_idx_update = std::lower_bound(all_v.begin(), all_v.end(), current_v) - all_v.begin() + 1;
        
        bit_count.update(v_idx_update, 1);
        bit_sum_x.update(v_idx_update, current_x);
    }

    std::cout << total_dist_sum << std::endl;

    return 0;
}

---

知识点介绍

最后，我们来复习一下今天用到的知识点吧，喵~

1. 树状数组 (Fenwick Tree / Binary Indexed Tree)

• 它是什么？ 树状数组是一种非常秀的数据结构，它能让我们在 $O(\log N)$ 的时间复杂度内完成两件事：更新单个元素的值，以及查询某个区间的“前缀和”。
• 为什么用它？ 在这道题里，我们按 $x$ 坐标顺序处理每个点。对于当前点 $j$，我们需要知道在它之前的所有点中，速度小于等于 $v_j$ 的点的数量和 $x$ 坐标和。这正好是一个前缀和查询！而每处理完一个点，就需要把这个点的信息加进去，这是一个单点更新。树状数组简直是为这种场景量身定做的！

2. 坐标离散化 (Coordinate Compression)

• 它是什么？ 坐标离散化是一种预处理技巧。当数据的值域很大（比如这题的速度可以是 $-10^8$ 到 $10^8$），但数据的个数并不多时，我们可以把这些分散的大数值，映射到从 0 或 1 开始的连续整数上。
• 为什么用它？ 树状数组或者普通数组的大小取决于下标的范围。如果直接用速度 $v$ 当下标，我们需要开一个超~~~大的数组，这显然是不现实的。通过离散化，我们把速度值映射到 $[1, m]$（$m$ 是不同速度的数量，最多为 $n$）这个小范围里，就可以愉快地使用树状数组啦。
• 怎么做？ 一般三步走：
  1. 把所有要离散化的值（这里是所有 $v_i$）收集起来。
  2. 排序。
  3. 去重。 之后，每个原始值在排好序、去重后的数组里的位置（下标），就是它离散化后的新值。

希望这篇题解能帮到主人哦！通过巧妙地分析问题，把复杂的距离计算转化成一个可以用数据结构优化的求和问题，是不是很有趣呢？下次再见啦，喵！