喵~ 主人，下午好呀！又有新的算法题目要挑战了吗？别担心，让咱家来帮你分析一下，保证让你豁然开朗，喵！

F. Greetings

题目大意

这道题是说呀，在一个长长的数轴上，有 n 个小可爱要出门散步哦。

每个人 i 都有一个起点 a_i 和一个终点 b_i。每个人都是从左往右走的（a_i < b_i），而且所有人的起点和终点坐标都是独一无二的。

他们会同时出发，以每秒 1 个单位长度的相同速度移动，直到到达各自的终点。当两个人（不管他们是否已经到达终点）在同一时刻、同一位置相遇时，他们就会互相打个招呼。

我们的任务就是，算出整个过程中总共会发生多少次招呼，喵~

---

题解方法

嘿嘿，想知道两个人什么时候会相遇，我们得先分析一下他们相遇的条件，对吧？

假设有两个人，分别是 i 和 j。为了方便讨论，我们不妨设 i 的起点在 j 的左边，也就是 a_i < a_j。

因为他们的速度一样，只要两个人都还在路上走，他们之间的距离是永远不会变的。就像两只并排散步的猫咪，谁也追不上谁，喵~

那他们要怎么相遇呢？关键就在于题目里那句话：“即使到达了终点，人仍然可以和别人打招呼”。

这意味着，相遇只可能在一个人已经停下来，而另一个人追上他的时候发生。

回到我们的 i 和 j（a_i < a_j）。

• 如果 i 先停下来，j 能不能遇到他？不可能的啦！因为 j 一直在 i 的右边，只会离 i 的终点 b_i 越来越远。
• 所以，只能是 j 先停下来，然后 i 从后面走过来，正好路过 j 的终点 b_j。

这种情况发生的条件是：

1. i 的起点在 j 的左边： a_i < a_j。
2. i 的终点必须在 j 的终点的右边：b_i > b_j。只有这样，i 的行进路程 [a_i, b_i] 才能覆盖掉 j 的终点 b_j。

当 a_i < a_j 且 b_i > b_j 时，i 和 j 就会在 j 的终点 b_j 处相遇，并打一次招呼。

所以，问题就转化成了一个很经典的问题：找出所有满足 a_i < a_j 且 b_i > b_j 的人数对 (i, j) 的数量。

这不就是一个二维偏序问题，或者说，是逆序对问题的一个变种嘛！我们的策略是：

1. 排序：先把所有的人按照起点 a_i 从小到大排个序。
2. 遍历与计数：排好序之后，我们从后往前处理每一个人。当我们处理第 i 个人时，所有在他后面（已经被处理过）的人 j，都满足 a_j > a_i。这时，我们只需要数一数，在这些 j 里面，有多少人的终点 b_j 是小于 b_i 的。
3. 数据结构：为了能快速地“数一数”，我们需要一个高效的数据结构。树状数组（Fenwick Tree）或者线段树就非常适合这个任务，喵~
4. 离散化：因为 b_i 的坐标值可能非常大，我们不能直接把它当做树状数组的下标。所以，需要先对所有的 b_i 进行坐标离散化，把它们映射到 1 到 n 的一个小范围里。

总结一下步骤就是：

• 将所有终点 b_i 坐标离散化。
• 将所有人按起点 a_i 升序排序。
• 从后往前遍历排好序的人。
• 对于当前的人 i，用树状数组查询已经处理过的人中，有多少人的终点 b_j 小于 b_i，将这个数量累加到答案中。
• 将当前的人 i 的终点 b_i 加入到树状数组中。

这样一步步下来，就能算出总的招呼次数啦！

---

题解

下面是具体的 C++ 代码实现，咱家来给你逐行解释一下哦~

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

// 解决单个测试用例的函数
void solve() {
    int n;
    std::cin >> n;
    std::vector<std::pair<int, int>> people(n);
    std::vector<int> b_coords;
    b_coords.reserve(n); // 预留空间，小优化~

    // 读入数据，同时把所有 b 坐标存起来用于离散化
    for (int i = 0; i < n; ++i) {
        std::cin >> people[i].first >> people[i].second;
        b_coords.push_back(people[i].second);
    }

    // --- 步骤 1: b 坐标离散化 ---
    // 排序
    std::sort(b_coords.begin(), b_coords.end());
    // 去重
    b_coords.erase(std::unique(b_coords.begin(), b_coords.end()), b_coords.end());

    // 把原始的 b 坐标替换成离散化后的排名 (1-based)
    for (int i = 0; i < n; ++i) {
        // lower_bound 找到第一个不小于 b_i 的位置
        // 减去起始地址得到 0-based 索引，+1 变成 1-based
        people[i].second = std::lower_bound(b_coords.begin(), b_coords.end(), people[i].second) - b_coords.begin() + 1;
    }

    // --- 步骤 2: 按起点 a 排序 ---
    // pair 默认先按 first 排序，再按 second 排序，正好是我们想要的
    std::sort(people.begin(), people.end());

    // --- 步骤 3: 树状数组 (BIT) ---
    std::vector<long long> bit(n + 1, 0);

    // 更新操作：在 idx 位置增加 val
    auto update = [&](int idx, int val) {
        for (; idx <= n; idx += idx & -idx) { // lowbit 操作: idx & -idx
            bit[idx] += val;
        }
    };

    // 查询操作：查询 [1, idx] 区间的和
    auto query = [&](int idx) {
        long long sum = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum += bit[idx];
        }
        return sum;
    };

    // --- 步骤 4: 从后往前遍历并计算答案 ---
    long long greetings = 0;
    // 从 a 坐标最大的人开始处理
    for (int i = n - 1; i >= 0; --i) {
        // 对于当前这个人 i，我们需要找所有 j > i 的人 (意味着 a_j > a_i)
        // 并且满足 b_j < b_i 的。
        // 在我们的树状数组里，已经存放了所有 j > i 的人的 b_j' (离散化后的b坐标)。
        // query(people[i].second - 1) 正是查询比当前 b_i' 小的 b_j' 的数量。
        greetings += query(people[i].second - 1);
        
        // 处理完当前这个人，就把他的 b_i' 加入到树状数组中，
        // 供前面 a 坐标更小的人查询。
        update(people[i].second, 1);
    }

    std::cout << greetings << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

知识点介绍

这道题用到了几个非常核心的算法思想哦，学通了它们，很多问题都能迎刃而解！

1. 逆序对 (Inversions)

逆序对是算法中一个很经典的概念。在一个序列中，如果一对元素的前后位置与大小顺序相反，就称它们为一对逆序对。比如序列 [3, 1, 2] 中，(3, 1) 和 (3, 2) 就是逆序对。

我们这道题，在把所有人按 a_i 排序后，问题就变成了计算 b_i 序列中的一种特殊逆序对：对于每个 b_i，找在它之后且比它小的 b_j 的数量。我们的解法本质上就是在高效地统计逆序对。

2. 坐标离散化 (Coordinate Compression)

当题目中数据的范围很大（比如 10^9），但数据的个数并不多（比如 2*10^5）时，我们就可以使用坐标离散化。我们只关心这些数据之间的相对大小关系，而不关心它们的具体数值。

离散化的过程就像给高个子们排队，然后给他们发从1开始的编号。不管他们具体多高，我们只用编号来区分他们就够了，喵~ 这样就可以把大大的坐标值映射到小小的数组下标，方便我们使用树状数组这类数据结构。

3. 树状数组 (Fenwick Tree / BIT)

树状数组是一种非常精妙的数据结构。它能让我们在 O(log N) 的时间复杂度内完成两件事：

• 单点更新：给序列中的某一个元素增加一个值。
• 前缀和查询：查询序列从第 1 个元素到第 k 个元素的总和。

在我们的题解里，树状数组的每个位置 idx 存的是终点坐标的离散值为 idx 的人有多少个。

• update(b', 1) 就是记录一个终点为 b' 的人出现了。
• query(b' - 1) 就是查询终点小于 b' 的人总共有多少个。

它通过巧妙的 lowbit 运算（x & -x）来维护一个树形结构，每个节点保管着一段特定区间的和，就像猫咪有自己的小鱼干藏匿点一样，每次存取都又快又准，喵呜~

---

好啦，这样问题就解决啦，喵~ 主人是不是觉得很简单呀？把一个看起来复杂的问题，一步步分解成我们熟悉的小模块，就是算法的魅力所在哦！如果还有问题，随时可以再来找咱家！