pku 3067 Japan
树状数组经典的应用。把每个公路看作(a,b)一条边，首先按a为第一关键字，b为第二关键字从大到小排序。然后维护一个序列A[i]，表示某时刻当前已经连到b的边数，用树状数组维护其前缀和Sum[i]=A[1]+A[2]+…+A[i]。当插入一条边(a,b)时，与这条边相交的边数就是Sum[b-1]，令Ans加上Sum[b-1]，然后修改A[b]加1。
由于边已经排过序，与每次添加的边相交的边数恰好可以从前b-1个A中统计出。时间复杂度为O((N+M)log(N+M))。
/*
* Problem: pku3067 japan
* Author: Guo Jiabao
* Time: 2009.3.19 13:38
* State: Solved
* Memo: 树状数组统计
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXM=1001;
using namespace std;
typedef __int64 big;
struct BIT
{
big C[MAXM];
int N;
void init(int tN)
{
N=tN;
memset(C,0,sizeof(C));
}
inline int lowbit(int x)
{
return x&(-x);
}
big sum(int p)
{
big rs=0;
while (p)
{
rs+=C[p];
p-=lowbit(p);
}
return rs;
}
void modify(int p,int delta)
{
while (p<N)
{
C[p]+=delta;
p+=lowbit(p);
}
}
}B;
struct highway
{
int x,y;
}H[MAXM*MAXM];
int N,M,K;
big Ans;
inline int cmp(const void *a,const void *b)
{
if (((highway *)a)->x > ((highway *)b)->x) return -1;
if (((highway *)a)->x < ((highway *)b)->x) return 1;
if (((highway *)a)->y > ((highway *)b)->y) return -1;
return 1;
}
void init()
{
scanf("%d%d%d",&N,&M,&K);
B.init(M);
for (int i=1;i<=K;i++)
scanf("%d%d",&H[i].x,&H[i].y);
qsort(H+1,K,sizeof(H[0]),cmp);
Ans=0;
}
void deal()
{
for (int i=1;i<=K;i++)
{
Ans+=B.sum(H[i].y-1);
B.modify(H[i].y,1);
}
}
int main()
{
int i,T;
freopen("japan.in","r",stdin);
freopen("japan.out","w",stdout);
scanf("%d",&T);
for (i=1;i<=T;i++)
{
init();
deal();
printf("Test case %d: %I64dn",i,Ans);
}
return 0;
}
上次修改时间 2017-02-03