51nod1107(逆序对数&归并排序)

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1107

题意：中文题诶～

思路：通过题意可以发现对于两点p1(x1, y1)，p2(x2, y2), 若x1<x2&&y1>y2则线段p1p2满足要求，那么显然可以先按x值排下序，对应y序列的逆序对数目即为答案；

注意：对于x1==x2&&y1>y2的情况是不满足题意的，可以通过重载排序去除x值相等的情况下的y逆序对；

代码：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#define ll long long
using namespace std;

const int MAXN=5e4+10;
struct node{
    int first;
    int second;
}p[MAXN];
ll ans=0;

bool cmp(node a, node b){
    if(a.first==b.first) return a.second<b.second;
    return a.first<b.first;
}

void teger_sort(int* a, int* t, int x, int y){
    if(y-x>1){  //**递归至单个元素为一组
        int m=(y+x)>>1;
        int p=x, q=m, i=x;
        teger_sort(a, t, x, m);  //***左递归
        teger_sort(a, t, m, y);  //***右递归
        while(p<m||q<y){   //**合并
            if(q>=y||(p<m&&a[p]<=a[q])){
                t[i++]=a[p++];  //**将左边元素复制到临时数组
            }else{
                t[i++]=a[q++]; //**将右边元素复制到临时数组
                ans+=m-p; //**累计逆序对的数目
            }
        }
        for(int i=x; i<y; i++){ //**将临时数组里已排序的元素还原到原数组
            a[i]=t[i];
        }
    }
}

int main(void){
    int n, a[MAXN], t[MAXN];
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d%d", &p[i].first, &p[i].second);
    }
    sort(p, p+n, cmp);
    for(int i=0; i<n; i++){
        a[i]=p[i].second;
    }
    teger_sort(a, t, 0, n);
    printf("%lld
", ans);
    return 0;
}