题解 P2154 【[SDOI2009]虔诚的墓主人】
xyz32768
2017-08-09 17:19:46
很容易看出，对于一个空地$(x,y)$，如果上下左右分别有$u$，$d$，$l$，$r$棵常青树，且$u,d,l,r>=k$，那么这块墓地的虔诚度为$C(u,k)*C(d,k)*C(l,k)*C(r,k)$。
但是现在的问题在于坐标系巨大，不能枚举所有的点。考虑离散化坐标后只枚举有效点（可以产生贡献的点），那么有效点也有$O(W^2)$个，无法承受$W<=10^5$的数据范围。首先，预处理出$C[k~W][k]$的值并离散化坐标，然后把常青树以$x$坐标为第一关键字，$y$坐标为第二关键字从小到大排序，这样$x$坐标相同的常青树就在一个连续区间里，并且这个连续区间内的$y$坐标是递增的。
对于一个$x$坐标相同的连续区间，常青树之间的空地只要满足上面和下面的常青树数量都必须$>=k$，就有可能产生贡献。而对于每相邻的两棵常青树之间的所有空地，上面的常青树的数量是一样的，下面的常青树的数量也是一样的。所以可以快速得到$C(u,k)*C(d,k)$的值，但是由于$y$坐标不相同，$C(l,k)*C(r,k)$需要进行求和。而每遇到一棵常青树，对应的$y$坐标的信息就需要改变。所以，这里考虑使用树状数组维护这个值。代码实现如下：
```cpp
for (i = 1; i <= w; i++) {
if (i == 1 || a[i].x != a[i - 1].x) tt = 0;
int le = a[i].y, v = (++h[le]) >= K && cnt[le] - h[le] >= K ?
1ll * C[h[le]][K] * C[cnt[le] - h[le]][K] % 2147483648ll : 0; tt++;
change(le, v - r[le]); r[le] = v;
if (i == w || a[i].x != a[i + 1].x || a[i + 1].y - a[i].y <= 1
|| tt < K || tot[a[i].x] - tt < K) continue;
Ans += 1ll * C[tt][K] * C[tot[a[i].x] - tt][K] % 2147483648ll
* (ask(a[i + 1].y - 1) - ask(a[i].y)) % 2147483648ll;
}
```
其中$C[][]$是预处理的组合数，$change$和$ask$为树状数组的操作，$cnt[]$记录每个$y$坐标值的出现次数，$tot[]$记录每个$x$坐标值的出现次数，$Ans$为答案。
最后输出答案$Ans$即可。（如果对模数$2147483648$采取自然溢出，那么要注意负数）。
代码：
```cpp
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
int res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
return bo ? ~res + 1 : res;
}
const int N = 1e5 + 5;
int w, K, C[N][12], Ans, tmp[N], T[N], col, tot[N], cnt[N], r[N], h[N];
struct cyx {int x, y;} a[N];
bool comp(cyx a, cyx b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
bool cmp2(cyx a, cyx b) {
if (a.y != b.y) return a.y < b.y;
return a.x < b.x;
}
void change(int x, int v) {
for (; x <= col; x += x & -x)
T[x] += v;
}
int ask(int x) {
int res = 0;
for (; x; x -= x & -x)
res += T[x];
return res;
}
int main() {
int i, j, tt = 0; read(); read(); w = read();
for (i = 1; i <= w; i++) a[i].x = read(), a[i].y = read();
K = read(); sort(a + 1, a + w + 1, comp);
for (i = 0; i <= w; i++) C[i][0] = 1;
for (i = 1; i <= w; i++) for (j = 1; j <= min(i, K); j++)
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
for (i = 1; i <= w; i++) {
if (i == 1 || a[i].x != a[i - 1].x) tt++;
tmp[i] = tt;
}
for (i = 1; i <= w; i++) tot[a[i].x = tmp[i]]++;
sort(a + 1, a + w + 1, cmp2); tt = 0;
for (i = 1; i <= w; i++) {
if (i == 1 || a[i].y != a[i - 1].y) tt++;
tmp[i] = tt;
}
for (i = 1; i <= w; i++) cnt[a[i].y = tmp[i]]++; col = a[w].y;
sort(a + 1, a + w + 1, comp);
for (i = 1; i <= w; i++) {
if (i == 1 || a[i].x != a[i - 1].x) tt = 0;
int le = a[i].y, v = (++h[le]) >= K && cnt[le] - h[le] >= K ?
1ll * C[h[le]][K] * C[cnt[le] - h[le]][K] % 2147483648ll
: 0; tt++;
change(le, v - r[le]); r[le] = v;
if (i == w || a[i].x != a[i + 1].x || a[i + 1].y - a[i].y <= 1
|| tt < K || tot[a[i].x] - tt < K) continue;
Ans += 1ll * C[tt][K] * C[tot[a[i].x] - tt][K] % 2147483648ll
* (ask(a[i + 1].y - 1) - ask(a[i].y)) % 2147483648ll;
}
printf("%d\n", Ans >= 0 ? Ans : (1ll * Ans + 2147483648ll)
% 2147483648ll);
return 0;
}
```