题解 P2154 【[SDOI2009]虔诚的墓主人】

### 虔诚的墓主人 --------------- ###### 观察数据范围得思路 $N,M$（地图大小）如此之大，而$W$（树的个数）只有$100,000$ 这种情况下，算法时间复杂度多半是关于$W$的。这个题中，能容忍的最大时间复杂度也就是$O(WlogW)$ $But$,但知道算法时间复杂度的最高上限是不能过直接相处如何去做的（当然离散化是能够被想出的） $So$，应该考虑从暴力算法优化 ----------- ##### 暴力 暴力无非就是每个点扫一下。看看上下左右树的个数多少，然后进行组合数的计算 假设上下左右分别有$t_{op},b_{ottom},l_{eft},r_{right}$个 那么答案就是$C_t^k\cdot C_b^k\cdot C_l^k\cdot C_r^k$ 时间复杂度$O(N\cdot M) $ ##### 优化  如图中两个蓝点的位置，我们可以很轻而易举的发现。这两个蓝点上面和下面的$t,b$大小不变 也就是$C_t^k\cdot C_{b}^{k}$大小不变，所以说在统计这两个蓝点方案数的时候，只需要计算每个蓝点（也就是同一个X的两棵树之间的空隙）的时候，只需要关注每个蓝点左右的$l,r$值。从下往上扫描，遇到一个数，就更新一次$t$,$b$.就可以了 可是这样的话，时间复杂度并未改变。 ~~如何对敌？~~ ~~呵呵呵呵，明日只需老夫一席话语........~~ 我们发现，在处理蓝点的时候，并不会对这个个数进行更改。只有在我们从左往右扫的时候，扫到了一棵树，那么这个树与下一个**同纵坐标之间的蓝点**的$l,r$才会更改（深绿框中蓝点与紫点的$l,r$,~~当然这个紫点的位置并不会计算贡献~~） 让我们回顾一下，现在的瓶颈是在于统计每个蓝点（空隙，下称蓝点）的左右的树的个数。 所以说我们要使用数据结构优化求和（什么和？就是当前蓝点的$C_l^k\cdot C_r^k$。为什么可以？利用乘法分配律，分解同一X的两棵树之间的贡献，对答案不影响） 这个数据结构支持什么？ 要支持区间求和和单点修改。所以说选用树状数组。 利用树状数组，快速算出两棵树（同一X）之间空隙的$C_l^k\cdot C^k_r$。然后乘以$C_t^k\cdot C_b^k$ 就可以保证在$O(WlogW)$的时间复杂度内算出答案 别忘了离散化 ```cpp #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using std::sort; const int maxn=101000; const long long mode=2147483648LL; struct node { int x,y;//原始位置 int X,Y;//离散化后位置 bool operator < (const node &a)const { if(x!=a.x) return x<a.x; return y<a.y; //其实这里用离散后的坐标效果是一样的 } }; node T[maxn]; long long last[maxn],Layt[maxn]; long long C[maxn][11]; long long ans; int totX[maxn],totY[maxn]; int baseX[maxn],lenX; int baseY[maxn],lenY; int base[maxn]; int N,M,w,k; int length; void insert(long long val,int pos)//Begin：树状数组 { while(pos<=length) { base[pos]=(base[pos]+val)%mode; pos+=(pos&(-pos)); } return ; } long long sum(int pos) { if(pos==0) return 0; long long res=0; while(pos) { res=(res+base[pos])%mode; pos-=(pos&(-pos)); } return res; } long long query(int l,int r) { return sum(r)-sum(l-1); }//End：树状数组 //以上是最普通不过的树状数组 //----------------------------------- void unique(int *A,int &Len)//去重 { sort(A+1,A+Len+1); int len=0,now=0x7fffffff; for(int i=1;i<=Len;i++) if(now!=A[i]) { now=A[i]; A[++len]=A[i]; } Len=len;//上面的引用，间接更改 return; } int check(int *A,int len,long long val)//离散化查询 { int l=1,r=len; while(l<r) { int mid=(l+r)>>1; if(A[mid]>=val) r=mid; else l=mid+1; } return l; } //以上是离散化和二分 //----------------------------------- void init(int x)//组合数 { C[0][0]=1; for(int i=1;i<=x;i++) for(int j=0;j<=10;j++) C[i][j]=(C[i-1][j]+(j?C[i-1][j-1]:0))%mode; return ; } //----------------------------------- void account(int n)//统计离散化后每一列，每一行共有多少个树 { int nowX,nowY; for(int i=1;i<=n;i++) { nowX=check(baseX,lenX,T[i].x); nowY=check(baseY,lenY,T[i].y); totY[nowY]++; totX[nowX]++; T[i].X=nowX;T[i].Y=nowY;//记录离散化后每棵树的位置 } length=lenY; } void add(int Y,int K)//将一颗树填进树状数组 { if(last[Y])//如果这棵树的Y之前有过值，应该先将这个值在树状数组中减去 { //last为上一次的值 insert(-last[Y],Y); last[Y]=0;//归零 } Layt[Y]++;//这个Y中已经被遍历过的树的数量+1 if(Layt[Y]>=K&&totY[Y]-Layt[Y]>=K)//新加的这一棵树在左右满足条件 { long long pas=(C[Layt[Y]][K]*C[totY[Y]-Layt[Y]][K])%mode; insert(pas,Y);//插入 last[Y]=pas;//记录 } } long long clac(int l,int r) { if(l>r) return 0;//防止错误，错误的原因是两棵树之间有可能没有空隙 return query(l,r);//树状数组查询 } void work(int n,int K)//解决问题 { int nowX=-1,now;//nowX为上一次处理的X位置，now为计数器 for(int i=1;i<=n;i++) { if(nowX!=T[i].X)//和上一次不在同一个X中 { now=0;//计数器归零 nowX=T[i].X;//赋值 } now++;//计数器++ if(totX[nowX]-now>=k&&now>=K&&T[i+1].X==nowX) ans=(ans+(C[now][k]*(clac(T[i].Y+1,T[i+1].Y-1)*C[totX[nowX]-now][k])%mode)%mode)%mode; /* * totX[nowX]-now>=k是判断是否上面树的数量可以进行计算 * now>=K是判断下面的树的数量是否可以进行计算 * T[i+1].X==nowX 特判第i棵树和第i+1棵树在同一X * ------------------------ * clac(T[i].Y+1,T[i+1].Y-1)是计算第i棵和第i+1棵之间空隙中的方案总数 * ------------------------ */ add(T[i].Y,K); //将这棵树的贡献加入树状数组 } } //解决问题 //-------------------------------------- int main() { scanf("%d%d%d",&N,&M,&w); for(int i=1;i<=w;i++) { scanf("%d%d",&T[i].x,&T[i].y); baseX[i]=T[i].x; baseY[i]=T[i].y; } scanf("%d",&k); unique(baseX,lenX=w);//手写的去重函数 unique(baseY,lenY=w); sort(T+1,T+1+w);//按照规则排序 init(w);//初始化组合数 account(w);//统计离散化后每一列，每一行共有多少个树 work(w,k);//解决问题 printf("%lld",(ans+mode)%mode);//输出答案 } //主函数 ``` ##### Ps：本人蒟蒻，如有纰漏。请在评论区指出。不胜感激