P2154 [SDOI2009]虔诚的墓主人

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll MOD=2147483648;
const int MAXN=100005;
ll num[MAXN];
ll num2[MAXN];
ll n,m,w,k;
struct N{
	ll x,y;
}point[MAXN];
bool cmp1(N p1,N p2){
	if(p1.x!=p2.x)return p1.x<p2.x;
	return p1.y<p2.y;
}         
bool cmp2(N p1,N p2){
	if(p1.y!=p2.y)return p1.y<p2.y;
	return p1.x<p2.x;
}    
ll h[MAXN],l[MAXN]; 
ll r[MAXN];
ll b[MAXN],tmp[MAXN];
void add(int x,ll v){
	while(x<MAXN){
		b[x]+=v;
		x+=(x&(-x));
	}
}
ll sum(int x){
	ll res = 0;
	while(x){
		res+=b[x];
		x-=(x&(-x));
	}
	return res;
}     
ll C[MAXN][20];
int main()
{
	ll cnt = 0;
	scanf("%lld %lld",&n,&m);
	scanf("%lld",&w);
	for(int i=1;i<=w;i++)scanf("%lld %lld",&point[i].x,&point[i].y);
	scanf("%lld",&k);
	sort(point+1,point+1+w,cmp2);
	
	for (int i = 0; i <= w; i++) C[i][0] = 1;
    for (ll i = 1; i <= w; i++) for (ll j = 1; j <= min(i, k); j++)
        C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        
	for(int i=1;i<=w;i++){
		if(i==1 || point[i].y!=point[i-1].y)cnt++;
		tmp[i] = cnt;
	}
	for(int i=1;i<=w;i++){
		point[i].y = tmp[i];
		num2[tmp[i]]++;//y 列 常青树的个数 
	}
	sort(point+1,point+1+w,cmp1);
	cnt = 0;
	for(int i=1;i<=w;i++){
		if(i==1 || point[i].x!=point[i-1].x)cnt++;
		tmp[i] = cnt; 
	}
	for(int i=1;i<=w;i++){
		point[i].x = tmp[i];
		num[tmp[i]]++;//x 行 常青树 的个数
	}
	ll ans = 0,col;//col 列向上 的个数 
	cnt = 0;
	for(int i=1;i<=w;i++){
		if(i==1 || point[i].x!=point[i-1].x)cnt = 0;
		col = point[i].y;
		ll v = ++h[col];
		v = v>=k && num2[col] - v >=k ? C[v][k]*C[num2[col] - v][k]%MOD : 0; cnt++;
		add(col,v-r[col]); r[col] = v;
		if(i==w || cnt <k || num[point[i].x] - cnt <k || point[i].x!=point[i+1].x || point[i+1].y - point[i].y <=1)
			continue;
		ans+= ( C[cnt][k]*C[num[ point[i].x ] - cnt][k]%MOD )*(sum(point[i+1].y - 1) - sum(point[i].y) )%MOD;
	}
	printf("%lld\n",(ans+MOD)%MOD);
	return 0; 
}