POJ 3067 Japan(树状数组)

题意是：日本有N个城市在东边，从北至南编号为1 2 3，，，N，M个城市在西边，从北至南编号为1 2 ，，，，M，K条高速公路将被建造，高速公路的一端在西边，一端在东边；问高速公路的交点有多少个，不包括城市的端点。

先把x按从小到大排序，若x相同然后再按y从小到大排序。模拟一下可以发现，交点的个数就是每个y的逆序对个数，问题就变成求逆序对有多少个，树状数组求解就可以了。

注意一点答案用longlong。

 1 //#pragma comment(linker, "/STACK:102400000,102400000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 const int MAXN = 1e3 + 5;
 8 typedef __int64 LL;
 9 int bit[MAXN] , m;
10 struct data {
11     int x , y;
12     bool operator < (const data &cmp) const{
13         if(x == cmp.x)
14             return y < cmp.y;
15         return x < cmp.x;
16     }
17 }a[MAXN * MAXN];
18 
19 inline void add(int i) {
20     for( ; i <= m ; i += (i & -i))
21         bit[i]++;
22 }
23 
24 int sum(int i) {
25     int res = 0;
26     for( ; i >= 1 ; i -= (i & -i))
27         res += bit[i];
28     return res;
29 }
30 
31 int main()
32 {
33     int t , n , k;
34     scanf("%d" , &t);
35     for(int ca = 1 ; ca <= t ; ca++) {
36         scanf("%d %d %d" , &n , &m , &k);
37         memset(bit , 0 , sizeof(bit));
38         for(int i = 0 ; i < k ; i++) {
39             scanf("%d %d" , &a[i].x , &a[i].y);
40         }
41         sort(a , a + k);
42         LL res = 0;
43         for(int i = 0 ; i < k ; i++) {
44             res += (LL)(i - sum(a[i].y));
45             add(a[i].y);
46         }
47         printf("Test case %d: " , ca);
48         printf("%I64d
" , res);
49     }
50 }