题目地址：洛谷：【P2154】[SDOI2009]虔诚的墓主人 – 洛谷、BZOJ：Problem 1227. — [SDOI2009]虔诚的墓主人

题目描述

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

输入输出格式

输入格式：
输入文件religious.in的第一行包含两个用空格分隔的正整数N和M，表示公墓的宽和长，因此这个矩形公墓共有(N+1) ×(M+1)个格点，左下角的坐标为(0, 0)，右上角的坐标为(N, M)。
第二行包含一个正整数W，表示公墓中常青树的个数。
第三行起共W行，每行包含两个用空格分隔的非负整数xi和yi，表示一棵常青树的坐标。输入保证没有两棵常青树拥有相同的坐标。
最后一行包含一个正整数k，意义如题目所示。

输出格式：
输出文件religious.out仅包含一个非负整数，表示这片公墓中所有墓地的虔诚度总和。为了方便起见，答案对2,147,483,648取模。

输入输出样例

输入样例#1：

5 6
13
0 2
0 3
1 2
1 3
2 0
2 1
2 4
2 5
2 6
3 2
3 3
4 3
5 2
2

输出样例#1：

6

说明

图中，以墓地(2, 2)和(2, 3)为中心的十字架各有3个，即它们的虔诚度均为3。其他墓地的虔诚度为0。
对于30%的数据，满足1 ≤ N, M ≤ 1,000。
对于60%的数据，满足1 ≤ N, M ≤ 1,000,000。
对于100%的数据，满足1 ≤ N, M ≤ 1,000,000,000，0 ≤ xi ≤ N，0 ≤ yi ≤ M，1 ≤ W ≤ 100,000，1 ≤ k ≤ 10。
存在50%的数据，满足1 ≤ k ≤ 2。
存在25%的数据，满足1 ≤ W ≤ 10000。

题解

有一些分可以用[eq]O(n^2)[/eq]乱搞过。具体来说就是预处理每个格子上下左右的常青树数量扫一遍格子。N和M太大的时候可以离散化搞一下，容易发现我们的算法其实是[eq]O(w^2)[/eq]的复杂度。
想把[eq]O(n^2)[/eq]搞成[eq]O(n \log n)[/eq]的算法，需要用到数据结构的辅助。假设每个格子上面、下面、左边、右边的常青树数量分别是u、d、l、r，我们发现每个格子对答案的贡献实际上是\mathrm{C}_u^k \times \mathrm{C}_d^k \times \mathrm{C}_l^k \times \mathrm{C}_r^k。如果我们一个格子一个格子地计算，肯定是不行的，考虑用数据结构维护一个维度的信息，这里我们维护的是区间\mathrm{C}_u^k \times \mathrm{C}_d^k的和。可以先把常青树按照坐标双关键字排序。由于每棵常青树只会对它所在行下面的该列格子产生影响，我们可以边处理边更新这个常青树所在列的值。处理同行的每两棵常青树之间的墓区间的上述和，再乘以左右两边常青树的数量即可。这个求前缀和可以使用常数小的树状数组来做。
模数非常特殊，是[eq]2^{31}[/eq]，我们可以用unsigned int自然溢出。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cctype>

#include <vector>
#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 200005;

int n, m, w, k;

unsigned int C[MAXN][15];

inline void calc(int x) {
    C[0][0] = 1;
    for(int i = 1; i <= x; i++) {
        for(int j = 0; j <= std::min(i, k); j++) {
            C[i][j] += C[i - 1][j];
            if(j > 0) C[i][j] += C[i - 1][j - 1];
        }
    }
}

unsigned int tree[MAXN];

inline int lowbit(int x) {
    return x & -x;
}

inline void add(int x, int v) {
    for(int i = x; i <= w; i += lowbit(i)) {
        tree[i] += v;
    }
}

inline unsigned int query(int x) {
    unsigned int res = 0;
    for(int i = x; i; i -= lowbit(i)) {
        res += tree[i];
    }
    return res;
}

struct Tree {
    int x, y;
} trees[MAXN];

inline bool cmp(Tree a, Tree b) {
    return a.x != b.x ? a.x < b.x : a.y < b.y;
}

std::vector<int> tmpx, tmpy;
int rcnt[MAXN], ccnt[MAXN], nrcnt, nccnt[MAXN];

int main() {
    n = readint(); m = readint(); w = readint();
    for(int i = 1; i <= w; i++) {
        trees[i].x = readint(); trees[i].y = readint();
        tmpx.push_back(trees[i].x); tmpy.push_back(trees[i].y);
    }
    k = readint();
    calc(w);
    tmpx.push_back(-1); tmpy.push_back(-1);
    // 离散化
    std::sort(tmpx.begin(), tmpx.end());
    tmpx.erase(std::unique(tmpx.begin(), tmpx.end()), tmpx.end());
    std::sort(tmpy.begin(), tmpy.end());
    tmpy.erase(std::unique(tmpy.begin(), tmpy.end()), tmpy.end());
    for(int i = 1; i <= w; i++) {
        trees[i].x = std::lower_bound(tmpx.begin(), tmpx.end(), trees[i].x) - tmpx.begin();
        trees[i].y = std::lower_bound(tmpy.begin(), tmpy.end(), trees[i].y) - tmpy.begin();
        rcnt[trees[i].x]++; ccnt[trees[i].y]++;
    }
    std::sort(trees + 1, trees + w + 1, cmp);
    unsigned int ans = 0;
    for(int i = 1; i < w; i++) {
        if(trees[i].x != trees[i - 1].x) nrcnt = 0;
        nccnt[trees[i].y]++; nrcnt++;
        // 更新所在列的值
        unsigned int up = nccnt[trees[i].y], down = ccnt[trees[i].y] - nccnt[trees[i].y],
            now = C[up][k] * C[down][k], old = query(trees[i].y) - query(trees[i].y - 1);
        if(now != old) add(trees[i].y, now - old);
        unsigned int left = nrcnt, right = rcnt[trees[i].x] - nrcnt;
        if(trees[i].x != trees[i + 1].x || trees[i + 1].y - trees[i].y <= 1
            || left < k || right < k) continue;
        // 计算两棵常青树之间区间对答案的贡献
        ans += C[left][k] * C[right][k] * (query(trees[i + 1].y - 1) - query(trees[i].y));
    }
    printf("%u", ans % 2147483648u); // 自然溢出是对2^32取模，这里再取一次模
    return 0;
}