2011–2012, Northern Subregional J. John’s Inversions

考虑某一种状态，无论如何调整卡片位置，都不会减少逆序对数量，这就是我们要找的最优解。

显然在对于一个颜色的数字有序时，达到了上述状态。

于是，我们根据一个颜色的值排序后再计算逆序对就得到了答案。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<vector>

#include<cstring>

#include<algorithm>

using namespace std;

typedef pair<int,int> card;

const int maxn=100000+1;

card c1[maxn],c2[maxn];

bool cmp(const card &a,const card &b)

{

 return a.first<b.first|| (a.first==b.first&&a.second<b.second);

}

bool cmp1(card a,card b)

{

 return a.second<b.second;

}

void merges(vector<card> & cc,int l,int r,long long int &ans)

{

 if(l==r)return;

 if(l==r-1)

 	 if(cmp1(cc[r],cc[l])){swap(cc[r],cc[l]);ans++;return ;}

 	 	else return ;

 int mid=(l+r)/2;

 vector<card>left,right;

 for(int i=l;i<=mid;i++)left.push_back(cc[i]);

 for(int i=mid+1;i<=r;i++)right.push_back(cc[i]);

 merges(left,0,mid,ans);merges(right,0,r-mid-1,ans);

 int l1=0,l2=0,len=0;

 while(l1<left.size()&&l2<right.size())

 	{

 	 if(cmp1(right[l2],left[l1])){cc[len++]=right[l2++];ans+=left.size()-l1;}

 	  	else{cc[len++]=left[l1++];}

	}

 while(l1<left.size())

 	{

 	 cc[len++]=left[l1++];

	}

 while(l2<right.size())

 	{

 	 cc[len++]=right[l2++];

	}

}

int main()

{freopen("john.in","r",stdin);

 //freopen("john.out","w",stdout);

 long long int ans1=0,ans2=0;

 int n;

 scanf("%d",&n);

 for(int i=0;i<n;i++)

 	{

 	 scanf("%d%d",&c1[i].first,&c1[i].second);

 	 c2[i].first=c1[i].second;

 	 c2[i].second=c1[i].first;

	}

 sort(c1,c1+n,cmp);

 sort(c2,c2+n,cmp);

 vector<card> s1,s2;

 for(int i=0;i<n;i++)

 	{

	 s1.push_back(c1[i]);

	 s2.push_back(c2[i]);

	}

 merges(s1,0,n-1,ans1);

 merges(s2,0,n-1,ans2);

 printf("%lld\n",min(ans1,ans2));

 return 0;

}