【bzoj1227】[SDOI2009]虔诚的墓主人

2014年3月11日3,8854

题目描述 Description

小W是一片新造公墓的管理人。公墓可以看成一块N×M的矩形,矩形的每个格点,要么种着一棵常青树,要么是一块还没有归属的墓地。

当地的居民都是非常虔诚的基督徒,他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚,他们希望自己的墓地拥有着较高的虔诚度。

一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地,墓地的正上、正下、正左、正右都有恰好k棵常青树。

小W希望知道他所管理的这片公墓中所有墓地的虔诚度总和是多少。

输入描述 Input Description

输入文件的第一行包含两个用空格分隔的正整数NM,表示公墓的宽和长,因此这个矩形公墓共有(N+1) ×(M+1)个格点,左下角的坐标为(0, 0),右上角的坐标为(NM)。

第二行包含一个正整数W,表示公墓中常青树的个数。

第三行起共W行,每行包含两个用空格分隔的非负整数xiyi,表示一棵常青树的坐标。输入保证没有两棵常青树拥有相同的坐标。

最后一行包含一个正整数k,意义如题目所示。

输出描述 Output Description

输出文件仅包含一个非负整数,表示这片公墓中所有墓地的虔诚度总和。为了方便起见,答案对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

6

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

数据范围及提示 Data Size & Hint

对于30%的数据,满足1 ≤ N≤ 1,000。

对于60%的数据,满足1 ≤ N≤ 1,000,000。

对于100%的数据,满足1 ≤ N≤ 1,000,000,000,0 ≤ xi ≤ N,0 ≤ yi ≤ M,1 ≤ ≤ 100,000,1 ≤ ≤ 10。

存在50%的数据,满足1 ≤ ≤ 2。

数据统计 Statistics

先离散横纵坐标

按照y进行排序,从下往上处理每一行

l[a],r[a],u[a],d[a]表示一个点上下左右的点数,可以预处理,也可以边做边记录

如果a,b在同一行,则ans+=c(l[a]+1(包括a),k)*c(r[b]+1,k)再分别乘上ab间的每一个点的c(u[i],k)*c(d[i],k)

但是这样复杂度为n^2

于是我们要用树状数组维护a到b所有点的c(u[i],k)*c(d[i],k)之和

可以这样考虑

比如某一列某一行有一个点

在扫描这行之下的时候,这个点是算在u[i]里的,但是扫描这行之上时算在了d[i]中

于是我们从左往右处理某行的某一个点时,要将树状数组中该点横坐标位置上的数进行修改

修改的值为就是现在的c(u[i],k)*c[d[i],k]减去原来的,也就是c(u[i],k)*c[d[i],k]-c(u[i]+1,k)*c[d[i]-1,k]

我的代码比较sb。。

 

  • ddd2016年2月25日 下午4:24 回复

    可以常数优化
    %2147483648改成&2147483647

    #1  
  • sentews2016年2月26日 上午9:57 回复

    Hack!
    10 10
    10
    8 8
    8 8
    5 4
    0 0
    0 9
    7 7
    5 5
    6 6
    4 8
    0 1
    1

    #2  
    • zxcvbnm_12016年3月11日 下午7:23 回复

      输入保证没有两棵常青树拥有相同的坐标。

      #21
  • BZOJ1227 – OceanEye's Blog2017年5月11日 下午4:46 回复

    […] 具体怎么做下面也有:-D大力安利HZWER […]

    #3