[SDOI2009]虔诚的墓主人

讲解

转化一下题目的要求，假设我们知道点$(i,j)$的上下左右的常青树的个数分别为$U[i][j]$，$D[i][j]$，$L[i][j]$和$R[i][j]$，那么依据一个很简单的组合数学我们知道：

$Ans = C_{K}^{U[i][j]} \times C_{K}^{D[i][j]} \times C_{K}^{L[i][j]} \times C_{K}^{R[i][j]}$

其中$C$为组合。基本的思路就是这样，但是我们要考虑优化。
从空间上来说，$1 \leq N, M \leq 1000000000$，肯定会直接爆炸（并且空间限制还是$128MB$）。题目并不要求十分确切的常青树位置，因此可以直接离散化。于是我们可以将坐标离散到一个$W \times W$的图中，因为$1 \leq W \leq 10000$，因此空间的问题就直接解决了。
然后是时间，对于每一个墓地，原始做法是$O(N^2)$的求出上下左右的四个数组，但是最终的时间复杂度是$O(N^4)$。于是对于优化来说这里用到一个扫描线的思想。
对于扫描线的具体讲解可以直接$Google$，这里只是针对题目讲方法罢了。
将所有的常青树按照$X$为第一关键字，$Y$为第二关键字的方法升序排序。
对于同一行的两个常青树，如果中间没有任何常青树，那么发现中间的所有的墓地的$L[i][j]$和$R[i][j]$都相等，因此只需要前缀和预处理出来

$\sum_{i}^{N} \sum_{j}^M C_{K}^{L[i][j]} \times C_{K}^{R[i][j]}$

即可，下面要求的就只剩下了$U[i][j]$和$D[i][j]$。

维护上下所有常青树的乘积，而左右乘积的改变次数就等于常青树的个数，而考虑其他行的时候上下乘积的改变次数也就是常青树的个数。

于是我们要维护上下组合数的乘积的区间和，这种维护显然就可以线段树或者树状数组。

步骤

对于同一行的两个数$A$和$B$，$Ans += C_{k}^{L[A]} \times C_{k}^{R[B]}$，然后用树状数组维护$A$和$B$点的$C_{k}^{U[i]} \times C_{k}^{D[i]}$的和。（省略掉了列，因为是同一行嘛）

答案实际上就是

$\sum C_{k}^{L[A]} \times C_{k}^{R[B]} \times \sum [C_{k}^{U[i]} \times C_{k}^{D[i]}]$

从左向右处理的时候，修改树状数组该点横坐标位置上的数值为

$C_{k}^{U[i]} \times C_{k}^{D[i]} - C_{k}^{U[i] + 1} \times C_{k}^{D[i] +1}$

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

typedef long long LL ;
const int MAXN = 100010 ;
const int Inf = 0x7ffffff ;
const int Mod = 2147483647 ;
int N, M, W, K, S[MAXN], C[MAXN][11] ;
int X[MAXN], Y[MAXN], Ans ;
struct Node {
    int X, Y, L, R, U, D ;
}   E[MAXN] ;

inline int Read() {
    int X = 0, F = 1 ; char ch = getchar() ;
    while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
    while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
    return X * F ;
}

struct BIT {
    int Sum[MAXN] ;

    inline int Lowbit(int Now) {
        return Now & ( - Now) ;
    }

    inline void Add(int Now, int K) {
        while (Now <= W) {
            Sum[Now] += K ;
            Now += Lowbit(Now) ;
        }
    }

    inline int Query(int Now) {
        int Ans = 0 ;
        while (Now > 0) {
            Ans += Sum[Now] ;
            Now -= Lowbit(Now) ;
        }   return Ans ;
    }
}   Bit ;

inline bool CMP(Node A, Node B) {
    if (A.Y != B.Y) return A.Y < B.Y ;
    else return A.X < B.X ;
}

inline void Init() {
    for (int i = 0 ; i <= W ; i ++) {
        C[i][0] = 1 ;
        for (int j = 1 ; j <= min(K, i); j ++)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1] ;
    }
    sort(E + 1, E + W + 1, CMP) ;
    int Ken = 0 ;
    for (int i = 1 ; i <= W ; i ++) {
        if (E[i].Y == E[i - 1].Y) Ken ++ ;
        else Ken = 1 ;  E[i].L = Ken ;
        S[E[i].X] ++ ; E[i].U = S[E[i].X] ;
    }   Ken = 0 ;
    for (int i = W ; i >= 1 ; i --) {
        if (E[i].Y == E[i + 1].Y) Ken ++ ;
        else Ken = 1 ; E[i].R = Ken ;
        E[i].D = S[E[i].X] - E[i].U ;
    }
}

int main() {
    N = Read(), M = Read(), W = Read() ;
    for (int i = 1 ; i <= W ; i ++) {
        E[i].X = Read(), E[i].Y = Read() ;
        X[i] = E[i].X ; Y[i] = E[i].Y ;
    }   K = Read() ;
    sort(X + 1, X + W + 1) ;
    sort(Y + 1, Y + W + 1) ;
    for (int i = 1; i <= W ; i ++) {
        E[i].X = lower_bound(X + 1, X + W + 1, E[i].X) - X ;
        E[i].Y = lower_bound(Y + 1, Y + W + 1, E[i].Y) - Y ;
    }   Init() ;
    for (int i = 1 ; i <= W ; i ++) {
        int V = Bit.Query(E[i].X) - Bit.Query(E[i].X - 1) ;
        Bit.Add(E[i].X, - V) ;
        Bit.Add(E[i].X, C[E[i].U][K] * C[E[i].D][K]) ;
        if (E[i].Y == E[i - 1].Y)
            Ans = Ans + C[E[i - 1].L][K] * C[E[i].R][K] * 
            (Bit.Query(E[i].X - 1) - Bit.Query(E[i - 1].X));
    }   printf("%d", Ans & Mod) ; 
    return 0 ;
}

后记

有人说可不可以搞一个二维线段树，思路上来说是可行的，但是空间上大概会爆炸吧~。
最后在冲浪的时候发现由于模数为$2147483647$所以可以自然溢出然后最后$ \& 2147483646$就可以了。