学步园

Description

Input

Output

Sample Input

1
3 4 4
1 4
2 3
3 2
3 1

Sample Output

Test case 1: 5

Source

/*将两个岛上的城市分别用一张图的行和列来表示
于是就出现了当两个城市之间修建桥的话，那么hash
标记该点为1，（来看测试数据）改图的hash值便变为
0 0 0 1
0 0 1 0
1 1 0 0

易得，当某个点为1的时候那么其右上方1的个数和就是该点
所表示的线段上的交点数，如此一来
for循环枚举点并且树状数组求"右上方"hash值为 1 点的个数*/

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;//二维树状数组的行和列
int c[1010][1010];//树状数组
int flag[1010][1010];
inline int lowbit(int x){return x&(-x);}
void update(int x,int y,int val)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        for(int j=y;j<=m;j+=lowbit(j))
        {
            c[i][j]+=val;
        }
    }
}
int getsum(int x,int y)
{
    int temp=0;
    for(int i=x;i>=1;i-=lowbit(i))
    {
        for(int j=y;j>=1;j-=lowbit(j))
        {
            temp+=c[i][j];
        }
    }
    return temp;
}
int main()
{
    int ci;scanf("%d",&ci);
    for(int pl=1;pl<=ci;pl++)
    {
        int k;
        memset(c,0,sizeof(c));
        memset(flag,0,sizeof(flag));
        scanf("%d%d%d",&n,&m,&k);
        while(k--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            flag[x][y]=1;
            update(x,y,1);
        }
        long long cnt=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(flag[i][j])
                {
                    cnt+=getsum(i-1,m)-getsum(i-1,j);//求右上角区域的和

                   //可优化成求一次和，即将数组左右倒置，这样就转换成求左上区域的和，只需求一次getsum()即可，需要将y换成m+1-y;

                  //见下面注释
                }
            }
        }
        cout<<"Test case "<<pl<<": "<<cnt<<endl;
        /*while(k--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            flag[x][m+1-y]=1;
            update(x,m+1-y,1);
        }
        __int64 cnt=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(flag[i][j])
                {
                    cnt+=(__int64)getsum(i-1,j-1);
                }
            }
        }
        printf("Test case %d: %I64d/n",pl,cnt);*/
    }
    return 0;
}