poj 3067 Japan（树状数组求逆序数）

题意：左边有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代码如下：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=1010;
 6 #define LL __int64
 7 int c[N];
 8 struct node{
 9     int x,y;
10     bool operator <(const node &a)const{
11         if(x==a.x)
12             return y<a.y;
13         return x<a.x;
14     }
15 }p[N*N];
16 int lowbit(int x)
17 {
18     return x&(-x);
19 }
20 void update(int x,int num)
21 {
22     while(x<=N)
23     {
24         c[x]+=num;
25         x+=lowbit(x);
26     }
27 }
28 LL sum(LL x)
29 {
30     LL s=0;
31     while(x>0)
32     {
33         s+=c[x];
34         x-=lowbit(x);
35     }
36     return s;
37 }
38 int main()
39 {
40     int t,i,k,j,n,m;
41     scanf("%d",&t);
42     for(j=1;j<=t;j++)
43     {
44         memset(c,0,sizeof(c));
45         scanf("%d%d%d",&n,&m,&k);
46         for(i=1;i<=k;i++)
47             scanf("%d%d",&p[i].x,&p[i].y);
48         sort(p+1,p+k+1);
49         LL ans=0;
50         for(i=1;i<=k;i++)
51         {
52             update(p[i].y,1);
53             ans+=i-sum(p[i].y);
54         }
55         printf("Test case %d: %I64d
",j,ans);
56     }
57     return 0;
58 }

View Code