bzoj 1227: [SDOI2009]虔诚的墓主人

.

题意：在一个n*m的矩形上，有一些格点是树，有一些是墓地。一块墓地的虔诚值定义为以它为中心的十字架的个数。十字架指的是在中心上下左右各选k棵树。问最后虔诚值的总和。
题解：离散化+排序+树状数组+组合数学
好题。先离散化，然后排序。求出每棵树上下左右各有多少棵树。树状数组记录的是当前行每个位置上下的方案数，算答案就可以用树状数组求出这一棵树和下一棵树（两棵树在同一行）之间的墓地的上下的方案和，再乘上左右的方案数，就是对答案的贡献。

#include<bits/stdc++.h>
using namespace std;

int n,m,w,k,c[100010][11],s[200010],mx,sum[200010],ans=0;
map<int,int>mpx,mpy;
struct pnt
{
    int x,y,u,d,l,r;
}a[100010];

inline int lb(int x)
{
    return x&-x;
}
void add(int x,int y)
{
    for(int i=x;i<=mx;i+=lb(i))
    s[i]+=y;
}
int get(int x)
{
    int ans=0;
    for(int i=x;i>0;i-=lb(i))
    ans+=s[i];
    return ans;
}
int cmp(pnt x,pnt y)
{
    return x.y==y.y?x.x<y.x:x.y<y.y;
}
int main()
{
    scanf("%d%d%d",&n,&m,&w);
    for(int i=0;i<w;i++)
    {
        scanf("%d%d",&a[i].x,&a[i].y);
        mpx[a[i].x]=1;
        mpy[a[i].y]=1;
    }
    int nn=0;
    int last=0;
    for(map<int,int>::iterator it=mpx.begin();it!=mpx.end();it++)
    {
        if(it->first-last>1)
        nn++;
        it->second=++nn;
        last=it->first;
    }
    nn=last=0;
    for(map<int,int>::iterator it=mpy.begin();it!=mpy.end();it++)
    {
        if(it->first-last>1)
        nn++;
        it->second=++nn;
        last=it->first;
    }
    for(int i=0;i<w;i++)
    {
        a[i].x=mpx[a[i].x];
        a[i].y=mpy[a[i].y];
    }
    mx=mpx.rbegin()->second;
    scanf("%d",&k);
    c[0][0]=1;
    for(int i=1;i<=w;i++)
    {
        c[i][0]=1;
        for(int j=1;j<=i&&j<=k;j++)
        c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    sort(a,a+w,cmp);
    int hh;
    for(int i=0;i<w;i++)
    {
        if(i==0||a[i].y!=a[i-1].y)
        hh=1;
        else
        hh++;
        a[i].l=hh;
        a[i].d=++sum[a[i].x];
    }
    for(int i=w-1;i>=0;i--)
    {
        if(a[i].y!=a[i+1].y)
        hh=1;
        else
        hh++;
        a[i].r=hh;
        a[i].u=sum[a[i].x]-a[i].d+1;
    }
//    for(int i=0;i<w;i++)
//    printf("x:%d y:%d u:%d d:%d l:%d r:%d\n",a[i].x,a[i].y,a[i].u,a[i].d,a[i].l,a[i].r);
    for(int i=0;i<w;i++)
    {
        add(a[i].x,c[a[i].d][k]*c[a[i].u-1][k]-get(a[i].x)+get(a[i].x-1));
        if(i!=0&&a[i].y==a[i-1].y)
        ans+=(get(a[i].x-1)-get(a[i-1].x))*c[a[i-1].l][k]*c[a[i].r][k];
    }
    printf("%d",ans&2147483647);
}