传送门
有点难调啊。其实是我自己sb了
不过交上去 1 A 1A 1A还是平衡了一下心态。
所以这道题怎么做呢？
我们考虑对于一个点 ( x , y ) (x,y) (x,y)如果这个点成为中心，正左/右/上/下分别有 l / r / u / d / l/r/u/d/ l/r/u/d/棵树，那么对于这个点 A n s = ( l k ) ∗ ( r k ) ∗ ( u k ) ∗ ( d k ) Ans=\binom {l} {k}*\binom {r} {k}*\binom {u} {k}*\binom {d} {k} Ans=(kl​)∗(kr​)∗(ku​)∗(kd​)
发现离散化之后直接枚举是 O ( n 2 ) O(n^2) O(n2)的。
于是我们用扫描线做。
按 y y y为第一关键字， x x x为第二关键字排个序。
然后用 b i t bit bit维护上下两侧的总方案数，左右的直接在扫的时候统计。
这样边做边更新答案就行了。
代码：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
const long long mod=1ll<<31;
const int N=1e5+5;
int n,k,vx[N],vy[N],sigx,sigy,bit[N],C[N][15],L[N],R[N],U[N],D[N],ans=0;
struct Node{int x,y;}p[N];
inline int lowbit(int x){return x&-x;}
inline void update(int x,int v){for(int i=x;i<=sigx;i+=lowbit(i))bit[i]+=v;}
inline int query(int x){int ret=0;for(int i=x;i;i-=lowbit(i))ret+=bit[i];return ret;}
inline bool cmp(const Node&a,const Node&b){return a.y==b.y?a.x<b.x:a.y<b.y;}
int main(){
	n=read(),n=read(),n=read();
	for(int i=1;i<=n;++i)p[i].x=vx[i]=read(),p[i].y=vy[i]=read();
	k=read(),C[1][1]=C[1][0]=1;
	for(int i=2;i<=n;++i){
		C[i][0]=1;
		for(int j=1;j<=k;++j)C[i][j]=C[i-1][j-1]+C[i-1][j];
	}
	sort(vx+1,vx+n+1),sigx=unique(vx+1,vx+n+1)-vx-1,sort(vy+1,vy+n+1),sigy=unique(vy+1,vy+n+1)-vy-1;
	for(int i=1;i<=n;++i)p[i].x=lower_bound(vx+1,vx+sigx+1,p[i].x)-vx,p[i].y=lower_bound(vy+1,vy+sigy+1,p[i].y)-vy,++U[p[i].x],++R[p[i].y];
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;++i){
		if(p[i-1].y^p[i].y)goto UPD;
		ans+=C[R[p[i].y]][k]*C[L[p[i].y]][k]*(query(p[i].x-1)-query(p[i-1].x));
		UPD:++L[p[i].y],--R[p[i].y],update(p[i].x,-C[U[p[i].x]][k]*C[D[p[i].x]][k]),--U[p[i].x],++D[p[i].x],update(p[i].x,C[U[p[i].x]][k]*C[D[p[i].x]][k]);
	}
	cout<<1ll*(ans+mod)%mod;
	return 0;
}