poj 3067

学长讲完线段树，树状数组后让我们做的题，但是看完题目，感觉用线段树没什么想法，然后n,m都只有1000这样的话，o(n*m)是可以过的，然后就直接开始做了：

大体思路：第一行1-n开始算，表示这个节点与之前的所有线最多形成了多少个crossing，然后开始加一个节点，一直加到第m个节点。每一个节点crossing的计算方法是，从第二行的最右边开始更新，更新到第一个点。

下面是ac代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>

using namespace std;
const int maxn = 1005;
long long a[1005],b[1005];//a[i]表示更新到第一行第i个节点，第i个节点连的所有线形成的crossing，
                          //b[j]表示更新到第二行第j个节点，连载j节点上面所有线的个数
long long mat[maxn][maxn];
long long n,m,k,ans;

void init()
{
    ans=0;
    for(int i=0;i<=n+1;i++)
    {
        a[i]=0;
        for(int j=0;j<=m+1;j++)
        {
            b[j]=0;
            mat[i][j]=0;
        }
    }
}
void solve()
{
    int c,d;
    while(k--)
    {
        scanf("%d%d",&c,&d);
        mat[c][d]++;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>0;j--)
        {
            if(!mat[i][j])
                continue;
            a[i]+=(b[j+1])*mat[i][j];
        }
        int inc=0;
        //一轮i更新完了以后才能更新b[j]的所有值
        for(int j=m;j>0;j--)
        {
            b[j]+=inc;
            if(!mat[i][j])
                continue;
            inc+=mat[i][j];
            b[j]+=mat[i][j];
        }
        ans+=a[i];
    }
}

int main()
{
    freopen("test.in","r",stdin);
    int T;
    while(scanf("%d",&T)!=EOF)
    {
        for(int nCase=1;nCase<=T;nCase++)
        {
            scanf("%I64d%I64d%I64d",&n,&m,&k);
            init();
            solve();
            printf("Test case %d: %I64d
",nCase,ans);
        }
    }
    return 0;
}