laekov

写完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);

}