F. Greetings

题目链接：Problem - F - Codeforces

题目大意：给你n个线段， 求有多少对（两个）线段满足完全覆盖， 例如： 设一个线段有a,b两点， 满足

ai <= aj <= bj <= bi (i,j为每个线段的下标)。   具体题目描述看原题链接。

输入：

输入的第一行包含一个整数 t ( 1≤t≤1e4 )--测试用例的数量。测试用例说明如下。

每个测试用例的第一行包含一个整数 n ( 1≤n≤2⋅1e5 ) - 人数。

然后是 n 行，其中 i 行包含两个整数 ai 和 bi( −1e9≤ai<bi≤1e9 )--每个人的起始位置和结束位置。

对于每个测试用例，所有的 2n 数字 a1,a2,…,an, b1,b2,…,bn 都是不同的。

所有测试用例中 n 的总和不超过 2⋅1e5 。

考察类容： 求逆序对， 归并排序，                                它解：树状数组， 离散化

1.通过题目的描述，看出只有当左端点足够小，才更有可能包含其他线段。

2.做法：先将线段以a端点排序， 然后通过b端点求逆序对。

例如样例：

-4 9

-2 5

3 4

6 7

8 10

排序过后：刚好保持不变， 接下来看b点， 对于第一个线段， b==9, 后面的 b==5, 4, 7, 满足 ans+=3,   对于b==5, 后面的 b==4, 满足 ans+=1. 后面的线段没有满足的了， 所以最后答案为ans = 4.  可以发现就是求b点的逆序对。

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
using i128 = __int128;
//求逆序对
i64 msort(vector<int> &a, vector<int> &b, int L, int R) {
    if(L==R)return 0;
    i64 res = 0;
    int mid = (L + R) >> 1;
    res += msort(a, b, L, mid);
    res += msort(a, b, mid+1, R);

    int i = L, j = mid+1, k = 0;
    while(i<=mid && j<=R) {
        if(a[i] <= a[j]) {
            b[k++] = a[i++];
        }else{
            b[k++] = a[j++];
            res += mid - i + 1;
        }
    }

    while(i<=mid) {
        b[k++] = a[i++];
    }
    while(j<=R) {
        b[k++] = a[j++];
    }
    for(int i=L, k=0; i<=R; i++, k++) {
        a[i] = b[k];
    }
    return res;
}

void solve(){
    int n;
    cin >> n;
    vector<pair<int,int>> p(n);
    for(int i=0; i<n; i++) {
        cin >> p[i].first >> p[i].second;
    }
    //排序
    sort(p.begin(), p.end());
    vector<int> a(n), b(n);
    for(int i=0; i<n; i++) {
        a[i] = p[i].second;
    }
    cout << msort(a, b, 0, n-1) << "\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

感谢收看与点赞， 欢迎大佬指正。