题目传送门
思路
看一眼数据，\(1\le N\)，\(M\le10^9\)，太难入手了。所以这道题肯定是从 \(\text{W}\) 和 \(\text{k}\) 入手的。
- 对于 \(\text{W}\)：离散化（此后最多会有 \(2\times W\) 个坐标）；
- 对于 \(\text{k}\)：预处理时间不足，考虑边计算边统计。
所以总的思路就是：
1. 按 \(\text{y}\) 坐标离散化，统计每一列共有多少常青树，并按列放进树状数组；
2. 按 \(\text{x}\) 坐标离散化，统计每一行共有多少常青树（扫描常青树的顺序按行应为从左到右）；
3. 对于相邻的两棵常青树，易得它们之间的墓地对应哪些列，以及这些列对于这一块墓地的 \(\operatorname{C} ^ k _ {up}+\operatorname{C} ^ k _ {down}\)。
思路很简单吧，但是还是需要优化。
每扫描到一棵树，就可以更新下一行下一列的树的个数了。\(\operatorname{lst} _ x++\) 后，把原数 \(\operatorname{a}\) 更新成 \(a (x+1) (y-x-k-1) \div (x+1-k) (y-x-1)\)，\(\operatorname{lst}\) 记录现在（包括现在）每一列有多少树。
好的，这样做之后还要优化，除非你可以开 \(10^9\) 的数组。
优化的思路就是把离散化后的坐标也用上。因此，直接乘是会出问题的。加上我们知道每个可能会成为十字架的列的前置常青树的情况，所以可以通过加减来改变。
在 \(\operatorname{lst} _ i++\) 之前，给这个坐标加上 \(\operatorname{c} [\operatorname{lst}[lh] + \operatorname{1}[k] \times \operatorname{c}[\operatorname{tot}[i]] - \operatorname{lst}[i] - 2] - \operatorname{c}[\operatorname{lst}[i][k] \times \operatorname{c}[\operatorname{tot}[i] - \operatorname{lst}[i] - 1]\)。
树状数组就很简单了，单点修改，区间查询。
最后，把相邻的常青树之间的墓地的 \(\operatorname{ans} += \operatorname{C} _ {left} ^ k \times \operatorname{C} _ {right} ^ k\times \sum _ {\text{这一棵树同一行的上一棵树}} ^ {\text{这一棵树之前}} \times \operatorname{C}[up][k] \times \operatorname{C}[down][k]\),其中 \(\operatorname{left}\) 可以现场扫描，每一行共有多少常青树已经记录过了。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
const ll M = 2147483648;
ll n, m, mtx = 1, mty = 1;//每一行常青树的总数/列,总行数，总列数
struct egt {
ll x, y;
#define x(i) et[i].x
#define y(i) et[i].y
} et[N];
int w, k;
ll lst[N], sx[N], sy[N];
ll c[N][15], tr[N], ans = 0;
inline int lowbit(int i) {
return i & (-i);
}
inline void ad(int p, ll chg) {
while (p < N) {
tr[p] = (tr[p] + chg) % M;
p += lowbit(p);
}
}
inline ll qs(int x) {
ll ret = 0;
while (x) {
ret = (ret + tr[x]) % M;
x -= lowbit(x);
}
return ret;
}
inline bool cmpx(egt x1, egt y1) {
if (x1.x == y1.x)
return x1.y < y1.y;
return x1.x < y1.x;
}
inline bool cmpy(egt x1, egt y1) {
if (x1.y == y1.y)
return x1.x < y1.x;
return x1.y < y1.y;
}
inline void ini() {
c[0][0] = 1;
for (int i = 1; i < N; i++) {
c[i][0] = 1;
for (int j = 1; j < 15; j++)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % M;
}
}
int main() {
ini();
scanf("%lld%lld%d", &n, &m, &w);
for (int i = 1; i <= w; i++)
scanf("%lld%lld", &et[i].x, &et[i].y);
scanf("%d", &k);
sort(et + 1, et + w + 1, cmpy);
for (int i = 2; i <= w; i++) {
if (y(i - 1) != y(i)) {
y(i - 1) = mty;
sy[mty]++, ++mty;
continue;
}
y(i - 1) = mty, sy[mty]++;
}
y(w) = mty, sy[mty]++;
sort(et + 1, et + w + 1, cmpx);
for (int i = 2; i <= w; i++) {
if (x(i - 1) != x(i)) {
x(i - 1) = mtx;
sx[mtx]++, ++mtx;
continue;
}
x(i - 1) = mtx;
sx[mtx]++;
}
x(w) = mtx, sx[mtx]++;
ll p = 0;
for (int i = 1; i <= w; i++) {
if (i > 1 && x(i - 1) == x(i)) {
p++;
ll m1 = c[p][k] % M * c[sx[x(i)] - p][k] % M;
ll m2 = (qs(y(i) - 1) - qs(y(i - 1)) + M) % M;
ans += m1 * m2;
ans %= M;
} else p = 0;
lst[y(i)]++;
ll chg = (c[lst[y(i)]][k] * c[sy[y(i)] - lst[y(i)]][k] - c[lst[y(i)] - 1][k] * c[sy[y(i)] - lst[y(i)] + 1][k]) % M;
ad(y(i), chg);
}
printf("%lld", (ans + M) % M);
return 0;
}