bzoj 1227: [SDOI2009]虔诚的墓主人

不念不忘少年蓝@ 2021-10-01 02:04 257阅读 0赞

## Description ##

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

## Solution ##

对于一个墓地,以它为中心的十字架的个数为 \\(C(l,K)\*C(r,K)\*C(u,K)\*C(d,K)\\) , \\(l,r,u,d\\)分别表示四个方向的树的数量  
把树按照 \\(x\\) 为第一关键字, \\(y\\)为第二关键字排序以之后,\\(x\\)相同的在一块,并且 \\(y\\) 递增,我们只需要单独拿出这些考虑即可  
首先上下的贡献可以通过下标算出,每一次查询就是查询上下相邻的两颗树中间的墓地的贡献,即需要维护一个左右贡献的和  
离散化坐标之后树状数组维护左右的贡献即可,随着 \\(x\\) 的移动,贡献也要相应的改变

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,R,C,K,Fac[N],inv[N],b[N],num=0,c[N][15],by[N],ny=0; int tx,ty,tr[N],l[N],r[N]; struct node{ int x,y; bool operator <(const node &p)const{ if(x!=p.x)return x<p.x; return y<p.y; } }a[N],e[N]; inline void add(int sta,int t){ for(int i=sta;i<=ty;i+=(i&(-i)))tr[i]+=t; } inline int qry(int sta){ int ret=0; for(int i=sta;i>=1;i-=(i&(-i)))ret+=tr[i]; return ret; } int main(){ freopen("pp.in","r",stdin); freopen("pp.out","w",stdout); cin>>R>>C>>n; for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y),b[++num]=a[i].x,by[++ny]=a[i].y; sort(b+1,b+num+1);sort(by+1,by+ny+1); tx=unique(b+1,b+num+1)-b-1;ty=unique(by+1,by+ny+1)-by-1; for(int i=1;i<=n;i++){ a[i].x=lower_bound(b+1,b+tx+1,a[i].x)-b; a[i].y=lower_bound(by+1,by+ty+1,a[i].y)-by; } cin>>K; for(int i=0;i<=n;i++){ c[i][0]=1; for(int j=1;j<=min(K,i);j++) c[i][j]=(c[i-1][j-1]+c[i-1][j]); } sort(a+1,a+n+1); for(int i=1;i<=n;i++)r[a[i].y]++; int ans=0; for(int i=1,j;i<n;i=j){ int cnt=0; for(j=i;j<n && a[j].x==a[i].x;j++)e[++cnt]=a[j]; for(int k=1;k<=cnt;k++){ int y=e[k].y; add(y,c[l[y]+1][K]*c[r[y]-1][K]-c[l[y]][K]*c[r[y]][K]); l[y]++;r[y]--; if(k>K && cnt-k+1>=K)ans+=c[k-1][K]*c[cnt-k+1][K]*(qry(y-1)-qry(e[k-1].y)); } } cout<<(ans&2147483647)<<endl; return 0; }

转载于:https://www.cnblogs.com/Yuzao/p/8454457.html