SDOI2009 虔诚的墓主人

1227: [SDOI2009]虔诚的墓主人

http://www.lydsy.com/JudgeOnline/problem.php?id=1227

Time Limit: 5 Sec Memory Limit: 259 MB

Description

小W 是一片新造公墓的管理人。公墓可以看成一块N×M 的矩形，矩形的每个格点，要么种着一棵常青树，要么是一块还没有归属的墓地。当地的居民都是非常虔诚的基督徒，他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚，他们希望自己的墓地拥有着较高的虔诚度。一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地，墓地的正上、正下、正左、正右都有恰好k 棵常青树。小W 希望知道他所管理的这片公墓中所有墓地的虔诚度总和是多少

Input

第一行包含两个用空格分隔的正整数N 和M，表示公墓的宽和长，因此这个矩形公墓共有(N+1) ×(M+1)个格点，左下角的坐标为(0, 0)，右上角的坐标为(N, M)。第二行包含一个正整数W，表示公墓中常青树的个数。第三行起共W 行，每行包含两个用空格分隔的非负整数xi和yi，表示一棵常青树的坐标。输入保证没有两棵常青树拥有相同的坐标。最后一行包含一个正整数k，意义如题目所示。

Output

包含一个非负整数，表示这片公墓中所有墓地的虔诚度总和。为了方便起见，答案对2,147,483,648 取模。

Sample Input

5 6
13
0 2
0 3
1 2
1 3
2 0
2 1
2 4
2 5
2 6
3 2
3 3
4 3
5 2
2

Sample Output

HINT

图中，以墓地(2, 2)和(2, 3)为中心的十字架各有3个，即它们的虔诚度均为3。其他墓地的虔诚度为0。

所有数据满足1 ≤ N, M ≤ 1,000,000,000，0 ≤ xi ≤ N，0 ≤ yi ≤ M，1 ≤ W ≤ 100,000， 1 ≤ k ≤ 10。存在50%的数据，满足1 ≤ k ≤ 2。存在25%的数据，满足1 ≤ W ≤ 10000。

注意：”恰好有k颗树“，这里的恰好不是有且只有，而是从>=k的树中恰好选k棵

树状数组

暴力：up，down，left，right分别代表墓地上下左右的

枚举每个墓地，ans=Σ C（up，k）*C（down，k）*C（left，k）*C（right，k）

时间复杂度：O（nw）

观察数据范围，发现n，m非常大，w相比却较小

所以思考答案是否与w有关

而且，离散化坐标

两块常青树之间的墓地，他们left相等，right相等

那么ans=Σ C（up，k）*C（down，k）*C（left，k）*C（right，k）

=Σ C（left，k）*C（right，k）* Σ C（up，k）*C（down，k）

所以可以讲常青树按行为第一关键字，列为第二关键字排序

枚举相邻（这类的相邻指排序中的顺序相邻）2棵常青树，这两颗常青树对答案的贡献是

C（left，k）*C（right，k）*两颗常青树之间的Σ C（up，k）*C（down，k）

因为按行为第一关键字，所以left和right可以在枚举的过程中得到

区间的Σ C（up，k）*C（down，k），用树状数组维护即可

还要注意一点，2棵常青树对答案有贡献的前提是:

2常青树行相等，列不相邻

一点儿小优化：% 2^31 可以用unsigned int 自然溢出

答案最后 & 2^31-1

注意要unsigned，否则出现负数就WA了

实测：bzoj 上快了300ms，codevs 上快了100ms （25个测试点总共）

感觉也没快多少

#include<cstdio>
#include<algorithm>
#define N 100002
using namespace std;
const long long mod=2147483648ll; 
int n,m,w,k,sx,sy;
int hashx[N],hashy[N],sumx[N],sumy[N],nowy[N];
long long ans,d[N];
long long c[N][11];
struct node
{
    int x,y,nx,ny;
}e[N];
bool cmp(node p,node q)
{
    if(p.x==q.x) return p.y<q.y;
    return p.x<q.x;
}
int read()
{
    int x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar();}
    return x;
}
int lowbit(int x) { return x&(-x); }
void add(int x,long long val)
{
    while(x<=sy)  { d[x]=(d[x]+val)%mod; x+=lowbit(x); }
}
long long query(int x)
{
    long long sum=0;
    while(x) { sum=(sum+d[x])%mod; x-=lowbit(x); }
    return sum;
}
long long C(int i,int j) { return c[i][j]; }
int main()
{
    scanf("%d%d%d",&n,&m,&w);
    for(int i=1;i<=w;i++) 
    {
        e[i].x=read(); e[i].y=read();
        e[i].x++; e[i].y++;
        hashx[i]=e[i].x; hashy[i]=e[i].y;
    }
    scanf("%d",&k);
    sort(e+1,e+w+1,cmp);
    sort(hashx,hashx+w+1);
    sort(hashy,hashy+w+1);
    sx=unique(hashx,hashx+w+1)-hashx-1;
    sy=unique(hashy,hashy+w+1)-hashy-1;
    for(int i=1;i<=w;i++)
    {
        e[i].nx=lower_bound(hashx,hashx+sx+1,e[i].x)-hashx; sumx[e[i].nx]++;
        e[i].ny=lower_bound(hashy,hashy+sy+1,e[i].y)-hashy; sumy[e[i].ny]++;
    }
    c[1][1]=1;
    for(int i=2;i<N;i++) c[i][1]=i;
    for(int i=2;i<N;i++)
     for(int j=2;j<=min(i,k);j++)
      c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    int tmp=0,down,up;
    for(int i=1;i<w;i++)
    {
        tmp++;  
        down=++nowy[e[i].ny];  up=sumy[e[i].ny]-down;
        add(e[i].ny,C(up,k)*C(down,k)-C(up+1,k)*C(down-1,k));
        if(e[i].x==e[i+1].x&&e[i].y+1!=e[i+1].y)
        {
            if(tmp>=k&&sumx[e[i].nx]-tmp>=k)  
             ans=(ans+C(tmp,k)*C(sumx[e[i].nx]-tmp,k)%mod*(query(e[i+1].ny-1)-query(e[i].ny)+mod)%mod)%mod;
        }
        else if(e[i].x!=e[i+1].x) tmp=0;
    }
    printf("%lld",ans);
}

WA 1: sy 是离散化之后的列，不是原题中的列

WA 2 ：换行的时候left清0

WA 3 ：前缀和相减哪里减1哪里不减，这里因为只要两常青树之间的区间和，所以端点都不包括