BZOJ原题链接

洛谷原题链接

又是扫描线，题解可看大佬的博客（太懒了不想打）

#include<cstdio>

#include<algorithm>

using namespace std;

const int N = 1e5 + 10;

const long long mod = 2147483648LL;

struct dd {

	int x, y;

};

dd a[N];

int ls_x[N], ls_y[N], sx[N], sy[N], S[N], C[N][12], nwy[N], la[N], xl, yl;

inline int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

	for (; c < '0' || c > '9'; c = getchar())

		p |= c == '-';

	for (; c >= '0' && c <= '9'; c = getchar())

		x = x * 10 + c - '0';

	return p ? -x : x;

}

inline int MOD(long long x)

{

	if (x < mod)

		return x;

	return x % mod;

}

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

inline void add(int x, int y)

{

	for (; x <= yl; x += lowbit(x))

		S[x] = MOD(1LL * S[x] + y);

}

inline int ask(int x)

{

	int s = 0;

	for (; x; x -= lowbit(x))

		s = MOD(1LL * s + S[x]);

	return s;

}

bool comp(dd x, dd y)

{

	if (!(x.x ^ y.x))

		return x.y < y.y;

	return x.x < y.x;

}

inline int minn(int x, int y) { return x < y ? x : y; }

inline int BSX(int x)

{

	int l = 1, r = xl, mid;

	while (l <= r)

	{

		mid = (l + r) >> 1;

		if (!(ls_x[mid] ^ x))

			return mid;

		ls_x[mid] > x ? r = mid - 1 : l = mid + 1;

	}

	return 0;

}

inline int BSY(int x)

{

	int l = 1, r = yl, mid;

	while (l <= r)

	{

		mid = (l + r) >> 1;

		if (!(ls_y[mid] ^ x))

			return mid;

		ls_y[mid] > x ? r = mid - 1 : l = mid + 1;

	}

	return 0;

}

int main()

{

	int i, j, n, m, s, o, v, an = 0;

	re(); re();

	n = re();

	for (i = 1; i <= n; i++)

	{

		ls_x[i] = a[i].x = re() + 1;

		ls_y[i] = a[i].y = re() + 1;

	}

	m = re();

	sort(ls_x + 1, ls_x + n + 1);

	sort(ls_y + 1, ls_y + n + 1);

	ls_x[n + 1] = ls_y[n + 1] = -1;

	for (i = 1; i <= n; i++)

		if (ls_x[i] ^ ls_x[i + 1])

			ls_x[++xl] = ls_x[i];

	for (i = 1; i <= n; i++)

		if (ls_y[i] ^ ls_y[i + 1])

			ls_y[++yl] = ls_y[i];

	for (i = 1; i <= n; i++)

	{

		a[i].x = BSX(a[i].x);

		a[i].y = BSY(a[i].y);

		sx[a[i].x]++;

		sy[a[i].y]++;

	}

	sort(a + 1, a + n + 1, comp);

	for (C[0][0] = 1, i = 1; i <= n; i++)

		for (j = C[i][0] = 1, o = minn(i, m); j <= o; j++)

			C[i][j] = C[i - 1][j] + C[i - 1][j - 1];

	for (i = 1; i <= n; i++)

	{

		if (a[i].x ^ a[i - 1].x)

			s = 0;

		else

		{

			s++;

			an = MOD(an + MOD(1LL * MOD(1LL * ask(a[i].y - 1) - ask(a[i - 1].y)) * MOD(1LL * C[s][m] * C[sx[a[i].x] - s][m])));

		}

		nwy[o = a[i].y]++;

		v = MOD(1LL * C[nwy[o]][m] * C[sy[o] - nwy[o]][m]);

		add(o, v - la[o]);

		la[o] = v;

	}

	printf("%lld", (1LL * an + mod) % mod);

	return 0;

}