首页 > 代码库 > BZOJ 1227 【SDOI2009】 虔诚的墓主人

BZOJ 1227 【SDOI2009】 虔诚的墓主人

Description

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

Input

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

Output

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

HINT

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

所有数据满足$1 \leqslant N, M \leqslant 1,000,000,000$,$0 \leqslant xi \leqslant N$,$0 \leqslant yi \leqslant M$,$1 \leqslant W \leqslant 100,000$,$ 1 \leqslant k \leqslant 10$。

存在$50\%$的数据,满足$1 \leqslant k \leqslant 2$。存在$25\%$的数据,满足$1 \leqslant W \leqslant 10000$。

注意:”恰好有$k$颗树“,这里的恰好不是有且只有,而是从不少于$k$棵的树中恰好选$k$棵

 

  这道题出看毫无想法……再看仍没有想法……回忆了一下以前看过的题解,终于知道怎么做了……

  首先,我们可以将坐标离散化(其实只要离散化$x$坐标就够了)。因为所有会产生贡献的墓地上、下、左、右一定都有常青树,因此这些墓地肯定可以由离散化之后的坐标表示。

  然后,我们对每棵常青树$i$求出它的上、下、左、右分别有多少棵常青树,分别记为$u_i$,$d_i$,$l_i$,$r_i$。这个东西可以将常青树排序后扫一遍求出来。

  接着,我们考虑使用一个扫描线从下往上扫。每到一行,我们可以求一下这一行的墓地会产生多少贡献。即,对于相邻的两棵常青树$i$和$j$($i$在$j$左边),我们设墓地$(i,j)$上方的常青树有$u_{i,j}$棵,下方的常青树有$d_{i,j}$棵,第$i$棵常青树坐标为$x_i,y_j$,那么对答案产生的贡献为:

$$C_{r_j+1}^k C_{l_i+1}^{k}\sum_{k=x_i+1}^{x_j-1}(u_{k,y_i}d_{k,y_i})$$

  于是我们现在要考虑的就是如何维护 $\sum_{k=x_i+1}^{x_j-1}(u_{k,y_i}d_{k,y_i})$ 这个东西。

  一般这种区间和的东西都可以用一个树状数组来维护。像这道题,我们可以将横坐标离散化,然后对横坐标建一个树状数组来维护这个东西。当我们每扫到一棵常青树的时候,就可以把这个横坐标维护的值在树状数组中修改一下即可。区间求和树状数组不在话下。

  还有一个细节。这道题的模数是$2147483648$,那么我们完全可以使用$unsigned int$来自然溢出,最后再把结果与上$2147483647$即可。

  所以这道题就这么解决了。我的代码还写了一点注释,不懂实现细节的话可以看一下。

  下面贴代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 100010

using namespace std;
typedef unsigned int llg;

struct data{
	int x,y,b;
}s[maxn];
int n,m,W,wx[maxn],dx[maxn],lx,N,k;
int l[maxn],r[maxn],u[maxn],d[maxn];
llg c[maxn],Cc[maxn][11],ans;

int getint(){
	int w=0;bool q=0;
	char c=getchar();
	while((c>‘9‘||c<‘0‘)&&c!=‘-‘) c=getchar();
	if(c==‘-‘) c=getchar(),q=1;
	while(c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar();
	return q?-w:w;
}

inline llg C(int x){return Cc[x][k];}//这个函数表示从x个数中去出k个的方案数
bool cmpx(data a,data b){if(a.x==b.x) return a.y<b.y;return a.x<b.x;}
bool cmpy(data a,data b){if(a.y==b.y) return a.x<b.x;return a.y<b.y;}
void add(int x,llg y){while(x<=lx) c[x]+=y,x+=x&(-x);}
llg sum(int x){
	llg t=0;
	while(x) t+=c[x],x-=x&(-x);
	return t;
}

void init(){
	sort(s+1,s+W+1,cmpx);
	for(int i=1;i<=W;i++){
		int j=i,now=0;
		while(s[j+1].x==s[j].x) j++,d[s[j].b]=++now;
		while(i<=j) u[s[i].b]=now--,i++; i--;
		N=max(N,d[s[j].b]);
	}//求u,d两个数组
	sort(s+1,s+W+1,cmpy);
	for(int i=1;i<=W;i++){
		int j=i,now=0;
		while(s[j+1].y==s[j].y) j++,l[s[j].b]=++now;
		while(i<=j) r[s[i].b]=now--,i++; i--;
		N=max(N,l[s[j].b]);
	}//求l,r两个数组
	for(int i=0;i<=N;i++) Cc[i][0]=Cc[i][i]=1;
	for(int i=2;i<=N;i++)
		for(int j=1;j<=k;j++)
			Cc[i][j]=Cc[i-1][j-1]+Cc[i-1][j];
}

int main(){
	File("a");
	n=getint()+1; m=getint()+1; W=getint();
	for(int i=1;i<=W;i++) dx[++lx]=s[i].x=getint()+1,s[i].y=getint()+1,s[i].b=i;
	k=getint(); sort(dx+1,dx+lx+1); lx=unique(dx+1,dx+lx+1)-dx-1; init();
	for(int i=1;i<=W;i++) wx[i]=lower_bound(dx+1,dx+lx+1,s[i].x)-dx;//离散化坐标
	for(int i=1,j;i<=W;i=j+1){
		j=i; add(wx[i],C(d[s[i].b]+1)*C(u[s[i].b])-C(d[s[i].b])*C(u[s[i].b]+1));//修改第i棵常青树对应的树状数组
		while(s[j+1].y==s[j].y){
			j++; ans+=C(l[s[j-1].b]+1)*C(r[s[j].b]+1)*(sum(wx[j]-1)-sum(wx[j-1]));//统计答案
			add(wx[j],C(d[s[j].b]+1)*C(u[s[j].b])-C(d[s[j].b])*C(u[s[j].b]+1));//修改第j棵常青树对应的树状数组
		}
	}
	printf("%d",ans&2147483647);
	return 0;
}

BZOJ 1227 【SDOI2009】 虔诚的墓主人