链接：http://poj.org/problem?id=3067
题意：左边有n个城市，右边有m个城市，建k条道路，问有这k条道路中有多少个交点。
分析：将城市按x和y从小到大排序，对于每条道路，求前面有多少个y比当前的y大的，累加起来即可。即求逆序数，可以用树状数组实现。
求逆序数的思路：
可以把数一个个插入到树状数组中， 每插入一个数， 统计小于等于他的数的个数，对应的逆序为 i- sum( data[i] )，其中 i 为当前已经插入的数的个数， sum( data[i] ）为比 小于等于data[i] 的数的个数，i- sum( data[i] ) 即比 data[i] 大的个数， 即逆序的个数。最后需要把所有逆序数求和，就是在插入的过程中边插入边求和。
另外这题要注意会超int，要用64位才能过。
AC代码如下：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
#define LL __int64
int c[N];
struct node{
int x,y;
bool operator <(const node &a)const{
if(x==a.x)
return y<a.y;
return x<a.x;
}
}p[N*N];
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int num)
{
while(x<=N)
{
c[x]+=num;
x+=lowbit(x);
}
}
LL sum(LL x)
{
LL s=;
while(x>)
{
s+=c[x];
x-=lowbit(x);
}
return s;
}
int main()
{
int t,i,k,j,n,m;
scanf("%d",&t);
for(j=;j<=t;j++)
{
memset(c,,sizeof(c));
scanf("%d%d%d",&n,&m,&k);
for(i=;i<=k;i++)
scanf("%d%d",&p[i].x,&p[i].y);
sort(p+,p+k+);
LL ans=;
for(i=;i<=k;i++)
{
update(p[i].y,);
ans+=i-sum(p[i].y);
}
printf("Test case %d: %I64d\n",j,ans);
}
return ;
}