「BZOJ1227」[SDOI2009] 虔诚的墓主人
题目描述 Description
小W是一片新造公墓的管理人。公墓可以看成一块N×M的矩形，矩形的每个格点，要么种着一棵常青树，要么是一块还没有归属的墓地。
当地的居民都是非常虔诚的基督徒，他们愿意提前为自己找一块合适墓地。为了体现自己对主的真诚，他们希望自己的墓地拥有着较高的虔诚度。
一块墓地的虔诚度是指以这块墓地为中心的十字架的数目。一个十字架可以看成中间是墓地，墓地的正上、正下、正左、正右都有恰好k棵常青树。
小W希望知道他所管理的这片公墓中所有墓地的虔诚度总和是多少。
输入描述 Input Description
输入文件的第一行包含两个用空格分隔的正整数N和M，表示公墓的宽和长，因此这个矩形公墓共有(N+1) ×(M+1)个格点，左下角的坐标为(0, 0)，右上角的坐标为(N, M)。
第二行包含一个正整数W，表示公墓中常青树的个数。
第三行起共W行，每行包含两个用空格分隔的非负整数xi和yi，表示一棵常青树的坐标。输入保证没有两棵常青树拥有相同的坐标。
最后一行包含一个正整数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, M ≤ 1,000。
对于60%的数据，满足1 ≤ N, M ≤ 1,000,000。
对于100%的数据，满足1 ≤ N, M ≤ 1,000,000,000，0 ≤ xi ≤ N，0 ≤ yi ≤ M，1 ≤ W ≤ 100,000，1 ≤ k ≤ 10。
存在50%的数据，满足1 ≤ k ≤ 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。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include<iostream> #include<cstdio> #include<algorithm> #define ll long long #define P 2147483648LL using namespace std; int n,m,w,K,H[200001]; ll c[100001][11],tr[200001],ans; struct data{int x,y;}a[100005]; int h[200001],l[200001]; int now[200001]; int find(int x) { int l=1,r=2*w,mid; while(l<=r) { int mid=(l+r)>>1; if(H[mid]<x)l=mid+1; else if(H[mid]>x)r=mid-1; else return mid; } } void getc() { c[0][0]=1; for(int i=1;i<=w;i++) {c[i][0]=1; for(int j=1;j<=min(K,i);j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%P; } } int lowbit(int x){return x&(-x);} void update(int x,int y) { while(x<=2*w) { tr[x]+=y;tr[x]%=P; x+=lowbit(x); } } ll ask(int x) { ll s=0; while(x) { s+=tr[x];s%=P; x-=lowbit(x); } return s; } inline bool cmp(data a,data b) { if(a.y==b.y)return a.x<b.x; return a.y<b.y; } int main() { scanf("%d%d%d",&m,&n,&w); for(int i=1;i<=w;i++) { scanf("%d%d",&a[i].x,&a[i].y); H[2*i-1]=a[i].x; H[2*i]=a[i].y; } scanf("%d",&K);getc(); sort(H+1,H+2*w+1); for(int i=1;i<=w;i++) { h[find(a[i].y)]++; l[find(a[i].x)]++; } sort(a+1,a+w+1,cmp); int lf; for(int i=1;i<=w;i++) { if(i>1&&a[i].y==a[i-1].y) { lf++; ll t1=ask(find(a[i].x)-1)-ask(find(a[i-1].x)); ll t2=c[lf][K]*c[h[find(a[i].y)]-lf][K]; ans+=t1*t2; ans%=P; } else lf=0; int d=find(a[i].x);now[d]++; int change=(c[now[d]][K]*c[l[d]-now[d]][K]-c[now[d]-1][K]*c[l[d]-now[d]+1][K])%P; update(d,change); } if(ans<0)ans+=P; printf("%d",ans); return 0; } |
OI 课件=>
[…] 具体怎么做下面也有:-D大力安利HZWER […]
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
输入保证没有两棵常青树拥有相同的坐标。
可以常数优化
%2147483648改成&2147483647