POJ 3067 Japan 树状数组

题意：两边都有一些城市，从上到下排列，有些城市之间有路，路与路之间会形成交点，问最后会形成多少个交点。
思路：首先可以把有联系的城市转化成平面上的点，比如说1 和2 之间有一条路，则代表有一个点，坐标为（1，2）。转化之后可以用树状数组做，可以发现最后的结果其实和所给的顺序无关，因此我们可以按y轴从小到大排序，若y轴相等，则按x轴从大到小排。
代码：
[cpp]  
#include <iostream> 
#include <cstdio> 
#include <algorithm> 
#include <string.h> 
using namespace std; 
 
#define CLR(arr,val) memset(arr,val,sizeof(arr)) 
typedef long long LL; 
const int N = 1010; 
LL num[N]; 
int flag[N][N]; 
struct road{ 
    int x,y; 
}rr[N*N]; 
bool cmp(road a,road b){ 
    if(a.y == b.y) 
        return a.x > b.x; 
    return a.y > b.y; 
} 
int lowbit(int x){ 
    return x & (-x); 
} 
void update(int x){ 
    while(x < N){ 
      num[x] += 1; 
      x += lowbit(x); 
    } 
} 
LL add(int x){ 
    LL s = 0; 
    while(x > 0){ 
       s += num[x]; 
       x -= lowbit(x); 
    } 
    return s; 
} 
int main(){ 
    //freopen("1.txt","r",stdin); 
    int numcase; 
    scanf("%d",&numcase); 
    int ca = 1; 
    while(numcase--){ 
       int n,m,k; 
       CLR(num,0); 
       CLR(flag,0); 
       scanf("%d%d%d",&n,&m,&k); 
       int x,y; 
       LL sum = 0; 
       for(int i = 0; i < k; ++i){ 
          scanf("%d%d",&rr[i].x,&rr[i].y); 
       } 
       sort(rr,rr+k,cmp); 
       for(int i = 0; i < k; ++i){ 
           if(flag[rr[i].x][rr[i].y]) 
               continue; 
          sum += add(rr[i].x - 1); 
          update(rr[i].x); 
          flag[rr[i].x][rr[i].y] = 1; 
       } 
       printf("Test case %d: %lld\n",ca++,sum); 
    } 
    return 0; 
} 
 

补充：软件开发 , C++ ,