PKU3067 Japan - 树状数组

本文主要是介绍PKU3067 Japan - 树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

城市被分为东西两个部分，两岸城市之间有高速公路连接。给出高速公路连接情况，判断有公路一共有多少个交点。

分析：

类似二部图匹配的模型。

设公路左边城市为x，右边城市为y。首先按照x城市的编号从大到小将公路a[]排序。

对于公路a[i]交点个数为，0到i-1之间的公路y<a[i].y的个数。（描述不清￥%#&……不说了，代码很明白）

这里是典型的树状数组的应用。

要注意两个地方：第一，公路可能有很多条，数组要开到10^6；第二，求和可能超int，要用int64。

 /*
PKU3067 Japan
*/
#include <stdio.h> 
#include <stdlib.h> 
#include <memory.h> 
#define clr(a) memset(a,0,sizeof(a)) 
#define int64 __int64 
#define I64d "%I64d" 
#define M 1000000 
#define N 3000 
typedef struct{
    int x,y;
}Node;
int n,m;
Node a[M];
int c[N];
int cmp(const void *A,const void *B){
    Node a = *(Node*)A;
    Node b = *(Node*)B;
    if(b.x==a.x) return b.y-a.y;
    return b.x-a.x;
}
int lowbit(int x){
    return x&(-x);
}
void Add(int i){
    while(i<=n){
        c[i]++;
        i+=lowbit(i);
    }
}
int64 Sum(int i){
    int64 s=0;
    while(i>0){
        s+=c[i];
        i-=lowbit(i);
    }
    return s;
}
int main()
{
    int T,Tn;
    
    scanf("%d",&Tn);
    
    for(T=1;T<=Tn;T++){
        int i,j,k;
        //input 
        scanf("%*d%d%d",&n,&m);
        for(i=0;i<m;i++){
            scanf("%d%d",&a[i].x,&a[i].y);
        }
        //sort 
        qsort(a,m,sizeof(a[0]),cmp);
        
        //work 
        int64 sum=0;
        clr(c);
        
        for(k=0;k<m;k++){
            i=a[k].y;
            Add(i);
            sum+=Sum(i-1);
        }
        //output 
        printf("Test case %d: "I64d"/n",T,sum);
    }
    
    return 0;
}
 