The secret of being a bore is to tell everything

0%

[SDOI2009] 虔诚的墓主人

题意

一个$N \times M (N, M \leq 10^9)$的地图上有$W (W \leq 10^5)$棵树。对于图上没有树的点,如果在这个点上下左右都至少有$k (1 \leq k \leq 10)$个点,那么它会贡献${L\choose{k}} * {R\choose{k}} * {U\choose{k}}* {D\choose{k}}$点虔诚度,问这个地图上所有虔诚度之和模$2147483648$(有毒)的值。

解题思路

题意很清晰,但是$N,M$的规模过于庞大,普通的模拟肯定不行了。但是我们注意到$W$的值并没有很大,所以实际上能贡献虔诚度的点只有$O(W^2)$个。但是这么多点一个个统计仍然太多了,所以很自然的我们想到了用扫描线法。

扫描线的统计仍然不是很直观,所以我们需要画一个图,假设我们现在的地图是这样的:
初始地图
那么显然中间那个点是一个可以统计的点,如果我们记某个点$p$上方的树的数量为$U(p)$,下方为$D(p)$,左右分别为$L(p), R(p)$。那么这个点的虔诚度为${L(p)\choose{k}} * {R(p)\choose{k}} * {U(p)\choose{k}}* {D(p)\choose{k}} = 1$。如果我们再加两个点,然后把目光集中在那根竖线上:
初始地图
我们可以发现可以贡献虔诚度的点会在竖线的线段与其左右两边的横线的交点上。除此之外,我们知道在这条竖线(不包括两端)上的点$U(p)$和$D(p)$的值是完全相等的。如果我们回到那个公式,统计所有点的贡献:
$$
\begin{align}
S & = \sum_{p} {L(p)\choose{k}} * {R(p)\choose{k}} * {U(p)\choose{k}}* {D(p)\choose{k}}\\
& = {U(p)\choose{k}} * {D(p)\choose{k}} * \bigg(\sum_{p} {L(p)\choose{k}} * {R(p)\choose{k}}\bigg)
\end{align}
$$
根据求和公式的分配率可以推出来。这个公式意味着我们可以先得出一段竖线的${U(p)\choose{k}} * {D(p)\choose{k}}$值,然后乘以这个竖线区域所包含的所有横线的${L(p)\choose{k}} * {R(p)\choose{k}}$就是这个区域所有的虔诚度贡献。竖线上的$U(p)$和$D(p)$可以通过从上到下以及预处理的方式求出来,现在问题在于怎么求出竖线上的横线贡献的$L(p), R(p)$:
$$
\sum_{i = l}^{r} {L(p[i])\choose{k}} * {R(p[i])\choose{k}}
$$
可以看出这其实是一个区间查询问题,对于横线来说$L(p), R(p)$也可以通过从左到右的方式算出来,但是问题是每个横线区域与竖线的位置是密切相关的,随着向右边移动而变化:
扫描线
这个时候扫描线的优势就出来了,我们可以把所有树的位置按照$x$坐标排序,如果$x$坐标相同则按照$y$坐标排序。然后我们从左到右,从上到下扫描,先统计个数,再更新横线的$L(p), R(p)$,最后把${L(p[i])\choose{k}} * {R(p[i])\choose{k}}$放进区间查询的数据结构里面。因为这个虔诚度是可以加起来的所以区间查询用树状数组就足够了。
动态演示

时间复杂度

$O(W\log{W})$,分别在排序和树状数组查询上。

参考代码

1
int cntX[MAXN * 2];
2
int cntY[MAXN * 2];
3
int curY[MAXN * 2];
4
FenwickTree tree;
5
int main() {
6
#ifdef LOCALLL
7
    freopen("in", "r", stdin);
8
    freopen("out", "w", stdout);
9
#endif
10
    int tot;
11
    scanf("%d%d", &n, &m);
12
    scanf("%d", &tot);
13
    // 组合数打表
14
    C[0][0] = 1;
15
    for (int i = 1; i <= tot; i++) {
16
        C[i][0] = 1;
17
        for (int j = 1; j <= min(i, 10); j++) {
18
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
19
        }
20
    }
21
    for (int i = 0; i < tot; i++) {
22
        int x, y;
23
        scanf("%d%d", &x, &y);
24
        points[i].x = x;
25
        points[i].y = y;
26
        discrete.add(x);
27
        discrete.add(y);
28
    }
29
    discrete.discretize();
30
    scanf("%d", &k);
31
    sort(points, points + tot);
32
    int cnt = 0;
33
    for (int i = 0; i < tot; i++) {
34
        cnt++;
35
        if (i == tot || points[i].x != points[i + 1].x) {
36
            int xx = discrete.get(points[i].x);
37
            // 横坐标为xx的点共有多少个
38
            cntX[xx] = cnt;
39
            cnt = 0;
40
        }
41
        points[i].x = discrete.get(points[i].x);
42
        points[i].y = discrete.get(points[i].y);
43
        // 纵坐标为y的点共有多少个
44
        cntY[points[i].y]++;
45
    }
46
    ll ans = 0;
47
    int curX = 0;
48
    for (int i = 0; i < tot; i++) {
49
        // 当前y坐标左边有多少个点
50
        curX++;
51
        if (i && points[i].x != points[i - 1].x) curX = 1;
52
        if (i != tot && points[i].x == points[i + 1].x) {
53
            int l = points[i].y, r = points[i + 1].y - 1;
54
            if (l < r) {
55
                ll U = choose(curX, k);
56
                ll D = choose(cntX[points[i].x] - curX, k);
57
                ll sum = ((tree.getSum(r) - tree.getSum(l)) % MOD + MOD) % MOD;
58
                ans = (ans + (sum * U % MOD) * D % MOD) % MOD;
59
            }
60
        }
61
        curY[points[i].y]++;
62
        ll now = choose(curY[points[i].y], k) *
63
                 choose(cntY[points[i].y] - curY[points[i].y], k) % MOD;
64
        ll pre =
65
            ((tree.getSum(points[i].y) - tree.getSum(points[i].y - 1)) % MOD +
66
             MOD) %
67
            MOD;
68
        // 注意只计算当前的总和,而不是之前的所有和
69
        tree.increase(points[i].y, (now - pre + MOD) % MOD);
70
    }
71
    printf("%lld\n", ans);
72
    return 0;
73
}