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; 
}