cf 918 div4

F. Greetings
1.思路：按照左端点排序然后求逆序对数量(使用的模板：归并排序)
$O(nlogn)$

#include<iostream>
#include<algorithm>
using namespace  std;
const int N  = 200010;
typedef long long LL;
typedef pair<int,int> PII;
PII d[N];
int a[N],tmp[N];
//归并排序求逆序对
LL merge_sort(int l ,int r)
{
    if(l>=r) return 0;
    int mid = (l+r)>>1;
    LL res = merge_sort(l,mid)+merge_sort(mid+1,r);
    int k = 0,i = l,j = mid+1;
    while(i<=mid&&j<=r)
        if(a[i]<=a[j]) tmp[k++] = a[i++];
        else
        {
            tmp[k++] = a[j++];
            res += mid-i+1;
        }
    while(i<=mid) tmp[k++] = a[i++];
    while(j<=r) tmp[k++] = a[j++];
    for(int i= l,j = 0;i<=r;i++,j++) a[i] = tmp[j];
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    while(n--)
    {
        int m;
        cin >> m;
        for(int i = 0;i<m;i++) cin>>d[i].first>>d[i].second;
        sort(d,d+m);
        for(int i = 0;i<m;i++) a[i] = d[i].second;
        cout << merge_sort(0,m-1)<<endl;
    }
    return 0;
}

2.ordered_set(ps:之前都没用过红黑树，一看题解要打这么长的拓展定义人都傻了)
$O(nlogn)$

include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set;

typedef pair<int,int> PII;
const int N = 200010;
typedef long long LL;

int n;
vector<PII> p;
ordered_set st;
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n;
    while(n--)
    {
        int m;
        cin >> m;
        p.assign(m,{});
        for(int i = 0;i<m;i++) cin >> p[i].second>>p[i].first;
        sort(p.begin(),p.end());
        LL res = 0;
        st.clear();
        for(int i = 0;i<m;i++)
        {
            res += st.size()-st.order_of_key(p[i].second);//去掉所以小于的情况
            st.insert(p[i].second);
        }
        cout<<res<<endl;
    }
    return 0;
}

3.二重循环(TLE)简单但是TLE -_-

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N = 200010;
int n;
PII p[N];
bool compare(const PII &a,const PII &b)
{
    return a.second>b.second;
}
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        int m;
        scanf("%d",&m);
        for(int i = 0;i<m;i++) scanf("%d%d",&p[i].first,&p[i].second);
        sort(p,p+m,compare);
        int res = 0;
        for(int i = 0;i<m;i++)
            for(int j = i+1;j<m;j++)
                if(p[i].first<p[j].first) 
                    res++;
        printf("%d\n",res);
    }
    return 0;
}