题目传送门

前置知识：排序 + 逆序对

题目大意

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

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

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

解题思路

piXS0MR.png

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

  • li<ljl_i < l_j 并且 ri>rjr_i > r_j
  • li>ljl_i > l_j 并且 ri<rjr_i < r_j

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

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

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

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

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#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;
}

赛事代码当时想复杂了，不过也可以过。大抵是目前题解里最简单的一篇罢。