POJ 4020 NEERC John's inversion 贪心+归并求逆序对

题意：给你n张卡，每张卡上有蓝色和红色的两种数字，求一种排列使得对应颜色数字之间形成的逆序对总数最小

题解：贪心，先按蓝色排序，数字相同再按红色排，那么蓝色数字的逆序总数为0，考虑交换红色的数字消除逆序，

那么这个操作的代价是蓝色的数字逆序对增加2*len-3，而红色的数字交换最多也只能消除那么多对逆序对。不会比当前更优。

因为数据范围比较大，用树状数组，线段树，可能要离散，所以学习了归并排序的方法来求逆序对总数。

思路大概是，归并之前的左右两个序列是已经排好序的，分别叫做L和R，如果L(i)>R(j)，那么R(j)也一定比L(i+1)以后的小，就算一下逆序对。归并排序又是先把小的给并入，所以不会少计算逆序对。

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 100005;

struct Unit
{
  int r,b;
  bool operator < (const Unit& rhs) const {
    return r < rhs.r || ( r == rhs.r && b < rhs.b );
  }
}a[maxn];

int t[maxn];
long long cnt;
void merge_sort(int l,int r)
{
    if(l==r) return;
    int mid = l+r>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int i = l, j = mid+1, k =l,p;
    while(i <= mid && j <= r){
        if(a[i].b>a[j].b){
            cnt += mid-i+1;
            t[k] = a[j].b;
            j++;
        } else {
            t[k] = a[i].b;
            i++;
        }
        k++;
    }
    if(i == mid + 1) for(p = j; p <= r; p++) t[k++] = a[p].b;
    else for(p = i; p <= mid; p++) t[k++] = a[p].b;
    for(k = l;k <= r; k++) a[k].b = t[k];
}


int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        scanf("%d%d",&a[i].r,&a[i].b);
    }
    sort(a,a+n);
    cnt = 0;
    merge_sort(0,n-1);
    printf("%I64d",cnt);

    return 0;
}

 在贴一份的各种情况的merge_sort

//[l,r] and need an array (t[])
void merge_sort(int l,int r)
{
    if(l == r) return;
    int mid = (l+r) >> 1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int p = l, q = r, k = l;
    while(p <= mid && q <= r){
        if(a[p]>a[q]) {
            // inv += mid - p + 1
            t[k++] = a[q++];
        } else {
            t[k++] = a[p++];
        }
    }
    if(p>mid) for(int i = q; i <= r; i++) t[k++] = a[i];
    else for(int i = q; i <= mid; i++) t[k++] = a[i];
    for(k = l; k <= r; i++) a[k] = t[k];
}

// [l r)
void merge_sort(int l,int r)
{
    if(r-l<=1) return;
    int m = (l+r)>>1;
    merge_sort(l,m);
    merge_sort(m,r);
    int p = l, q = m, i = l;
    while(p < m || q < r){
        if(q >= r || (p<m && a[p] <= a[q]) ) t[i++] = a[p++];
        else {
            // inv += m-p;
            t[i++] = a[p++];
        }
    }
    for(i = l; i < r; i++) a[i] = t[i];
}