写完Kdtree感觉整个人都要离散了。
这题比较神，之前连题都没看懂。每个位置的方案数就是上下左右的数量的组合数的乘积。把x离散之后维护区间中左×右的和，上下y相同的扫一遍搞定。（感觉说了像没说）
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct point {
int x, y;
};
const int maxn = 100009;
const int maxk = 13;
inline bool cmpP(int* a, int* b) {
return *a < *b;
}
inline bool cmpy(const point& a, const point& b) {
return (a. y < b. y) || (a. y == b. y && a. x < b. x);
}
point a[maxn];
int n, m, c[maxn][maxk], cx[maxn], tx[maxn], t[maxn], maxx, ans;
int *r[maxn];
void prec() {
c[0][0] = 1;
for (int i = 0; i <= n; ++ i)
c[i][0] = 1;
for (int i = 1; i <= m; ++ i) {
for (int j = 0; j < i; ++ j)
c[j][i] = 0;
for (int j = i; j <= n; ++ j)
c[j][i] = c[j - 1][i] + c[j - 1][i - 1];
}
}
void dispx() {
for (int i = 0; i < n; ++ i)
r[i] = &a[i]. x;
sort(r, r + n, cmpP);
maxx = 0;
for (int i = 0, l = *r[0] - 1; i < n; ++ i)
if (*r[i] == l)
*r[i] = maxx;
else
l = *r[i], *r[i] = ++ maxx;
memset(tx, 0, sizeof(tx));
for (int i = 0; i < n; ++ i)
++ tx[a[i]. x];
}
void btChg(int* t, int p, int v) {
for (; p <= maxx; p += (p & -p))
t[p] += v;
}
int btQry(int* t, int p) {
int s = 0;
for (; p; p -= (p & -p))
s += t[p];
return s;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
memset(t, 0, sizeof(t));
memset(cx, 0, sizeof(cx));
scanf("%*d%*d%d\n", &n);
for (int i = 0; i < n; ++ i)
scanf("%d%d", &a[i]. x, &a[i]. y);
scanf("%d", &m);
prec();
dispx();
sort(a, a + n, cmpy);
ans = 0;
for (int i = 0, j; i < n; i = j) {
for (j = i; j < n && a[j]. y == a[i]. y; ++ j);
for (int k = i + m - 1; k + m < j; ++ k)
if (a[k]. x < a[k + 1]. x)
ans += (btQry(t, a[k + 1]. x - 1) - btQry(t, a[k]. x))
* c[k - i + 1][m] * c[j - k - 1][m];
for (int k = i; k < j; ++ k) {
int x = a[k]. x;
btChg(t, x, -c[cx[x]][m] * c[tx[x] - cx[x]][m]);
++ cx[x];
btChg(t, x, c[cx[x]][m] * c[tx[x] - cx[x]][m]);
}
}
printf("%d\n", ans & 0x7fffffff);
}