This post is written in Chinese. Please consider using Google Translate

树状数组经典的应用。把每个公路看作(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;
}