【题解】Greetings

前置知识：排序 + 逆序对

题目大意

数线上有 $n$ 个人，第 $i$ 个人在点 $a \times i$ ，想去点 $b \times i$ 。对于每个人来说， $a \times i \lt b \times i$ 以及所有人的起点和终点都是不同的（也就是说，所有的 $2n$ 数 $a \times 1, a \times 2, \dots, a \times n, b \times 1, b \times 2, \dots, b \times n$ 都是不同的）。

所有的人将以每秒 $1$ 个单位的速度同时开始移动，直到到达终点 $b_i$ 。当两个人在同一点相遇时，他们会互相问候一次。会有多少次打招呼？

请注意，即使一个人到达了最终点，他仍然可以向其他人打招呼。

解题思路

画图后可以看出，由于 $a \times i \lt b \times i$ ，所有人都在去往右边走，并且速度相同，此时相遇有两种可能：

$l_i < l_j$ 并且 $r_i > r_j$
$l_i > l_j$ 并且 $r_i < r_j$

我们只需要稍加排序，就可以转化为一种思路：

将所有人的初始点从小到大进行排序，求出他们的终点的逆序对之和。

这不就是逆序对么？把样例丢尽逆序对模板，十分正确的。

接下来就可以愉快的写代码了。

AC Code

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
#define int long long

int a[N], c[N], ans;
struct Node
{
    int l, r;
    bool operator<(const Node &u) const
    {
        return l < u.l;
    }
}tmp[N];

void mergesort(int bg, int ed)
{
    if (bg == ed)
        return;
    int mid = (bg + ed) / 2, i = bg, j = mid + 1, k = bg;
    mergesort(bg, mid), mergesort(mid + 1, ed);
    while (i <= mid && j <= ed)
    {
        if (a[i] <= a[j])
            c[k++] = a[i++];
        else
            c[k++] = a[j++], ans += mid - i + 1;
    }
    while (i <= mid)
        c[k++] = a[i++];
    while (j <= ed)
        c[k++] = a[j++];
    for (int l = bg; l <= ed; l++)
        a[l] = c[l];
}

void solve()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i ++) cin >> tmp[i].l >> tmp[i].r;
    sort(tmp + 1, tmp + 1 + n);
    
    for (int i = 1; i <= n; i ++) 
        a[i] = tmp[i].r;
    ans = 0;
    mergesort(1, n);
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}