SDOI2009 虔诚的墓主人-白红宇

SDOI2009 虔诚的墓主人

阅读量：6220 次

发布时间：2019-06-21

本文共 3156 字，大约阅读时间需要 10 分钟。

1227: [SDOI2009]虔诚的墓主人

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

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

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
      
       #include
       
        #define N 100002using 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
        
         '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
         
          =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);}