这个题目是逆序数的变形，主要我存在的问题是思维的问题，先按x从小到大排序，如果x相等，再按y从小到大排序，我觉得我应该能想到怎么做，但是主要原因是我没有积极去思考，我发现每次我都是这样，有很强的依赖感和懒惰感，其实好多题目按照常规思路去想，加一点优化，或者利用现有的知识其实我是能够解决的，比如说比赛的时候我就过分依赖队友，我觉得这样不仅会让自己的水平得不到提高，更重要的是自己会丧失队友对我的信任，其实我是能够做出来的，比如说上次的动归，那还算有点难度，但是我还是想出来，现场也不是很多人想出来了，我下次会选择一个题目，然后仔细的思考，争取做出来，先想暴力的思路是什么，再优化，如果我连暴力都不敢暴力的话，我想我们怎么能够想出更复杂的算法去解决这个问题，所以我想对自己说的是，一要相信自己，不要去依赖别人，而是要积极思考，哪怕是最难的题目，也可以先用最暴力的方法解，但是如果不尝试的话，我想这是根本就不可能解出来的，所以一定要开动脑筋想，先想暴力，再想优化。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct node{
int x;
int y;
}node;
__int64 ans;
int const max_n = 1000010;
node a[max_n];
int b[max_n];
int c[max_n];
int n,m,k;
bool cmp(node na,node nb){
if( na.x < nb.x)
return true;
if( na.x > nb.x )
return false;
if( na.y < nb.y)
return true;
return false;
}
void merge_sort(int *A,int x,int y,int *T){//A数组x——y的左闭又开区间的归并算法
if( y-x >1 ){
//printf("%I64d\n",ans);
int m = x +(y-x)/2;//此处不用（x+y）/2避免越界
int p = x,q=m,i=x;
merge_sort(A,x,m,T);
merge_sort(A,m,y,T);
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( i=x; i<y; i++ )
A[i] = T[i];
//printf("x = %d y = %d ans = %I64d\n",x,y,ans);
}
}
int main(){
int t;
while( 1 == scanf("%d",&t) ){
int id = 0;
while( t-- ){
scanf("%d%d%d",&n,&m,&k);
for( int i=0; i<k; i++ )
scanf("%d%d",&a[i].x,&a[i].y);
sort(a,a+k,cmp);
ans = 0;
for( int i=0; i<k; i++ )
b[i+1] = a[i].y;
b[k+1] = 10000;
merge_sort(b,1,k+1,c);
printf("Test case %d: %I64d\n",++id,ans);
}
}
return 0;
}