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

}