来一发优美的线段树版题解$QwQ$。
对于一块墓碑，它的贡献是上方取$k$棵树、下方取$k$棵树、左边取$k$棵树、右边取$k$棵树方案数的乘积。
即：假设一块墓碑上、下、左、右分别有$u,d,l,r$棵树（下同），其贡献为$C(u,k)*C(d,k)*C(l,k)*C(r,k)$。
预处理出组合数，离散化后扫描线扫$x$轴，注意到$y$轴上的两棵树之间的点它们的$u$和$d$是相同的
就像这样：
也就是说它们的$C(u,k)*C(d,k)$是可以$O(1)$算出来的。那么就能维护一下$\sum C(l_i,k)*C(r_i,k)$乘起来算进答案里。
首先算出$y$轴每列有多少棵树，以此为初始$r$值，$l$为$0$，从左到右扫。遇到一棵树就把这一列的$r$减$1$，$l$加$1$，并更新这个点的$C(l,k)*C(r,k)$。对同一排上的两棵树查询中间的$\sum C(l_i,k)*C(r_i,k)$即可。
树状数组蒟蒻不会更新$QAQ$，都放在了线段树上搞。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#define maxn 100005
#define inf 0x3f3f3f3f
const long long mod = 2147483648ll;
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
template<typename T>
inline T read(){
T x=0;
int y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
long long C[11][maxn],c[maxn];
int disx[maxn],disy[maxn],init[maxn],lenx,leny;
vector<int>X[maxn];
struct Segment_Tree{
long long dat[maxn<<2];
int ll[maxn<<2],rr[maxn<<2];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
inline void update(int node){
dat[node]=(dat[ls(node)]+dat[rs(node)])%mod;
}
void build(int l,int r,int node){
if(l==r){
rr[node]=init[l];
return;
}
int mid=l+r>>1;
build(l,mid,ls(node));
build(mid+1,r,rs(node));
}
void add(int poi,int l,int r,int node){
if(l==r){
--rr[node],++ll[node];
dat[node]=c[rr[node]]*c[ll[node]]%mod;
//更新组合数
return;
}
int mid=l+r>>1;
if(poi<=mid)add(poi,l,mid,ls(node));
else add(poi,mid+1,r,rs(node));
update(node);
}
long long ask(int L,int R,int l,int r,int node){
if(L<=l&&R>=r)return dat[node];
int mid=l+r>>1;
long long ans=0;
if(L<=mid)ans=ask(L,R,l,mid,ls(node));
if(R>mid)ans+=ask(L,R,mid+1,r,rs(node));
return ans%mod;
}
}st;
struct tree{
int x,y;
}t[maxn];
int main(){
C[0][0]=1;
read(),read();
int n=read();
for(register int i=1;i<=n;++i)
disx[++lenx]=t[i].x=read(),disy[++leny]=t[i].y=read();
sort(disx+1,disx+lenx+1);
sort(disy+1,disy+leny+1);
lenx=unique(disx+1,disx+1+lenx)-disx-1;
leny=unique(disy+1,disy+1+leny)-disy-1;
//离散化
int k=read();
for(register int i=1;i<=n;++i){
++init[t[i].y=lower_bound(disy+1,disy+1+leny,t[i].y)-disy];//初始的r值
X[lower_bound(disx+1,disx+1+lenx,t[i].x)-disx].push_back(t[i].y);
C[0][i]=1;
for(register int j=1;j<=k;++j)
C[j][i]=(C[j][i-1]+C[j-1][i-1])%mod;
c[i]=C[k][i];
//预处理组合数。因为都是关于k的就压进了一个数组
}
st.build(1,leny,1);
long long ans=0;
for(register int i=1;i<=lenx;++i){
sort(X[i].begin(),X[i].end());//一定要排序
if(!X[i].empty())st.add(X[i][0],1,leny,1);
for(register int j=1;j<X[i].size();++j){
if(X[i][j-1]+1<X[i][j]&&j>=k&&X[i].size()-j>=k)(ans+=st.ask(X[i][j-1]+1,X[i][j]-1,1,leny,1)*c[j]%mod*c[X[i].size()-j]%mod)%=mod;
st.add(X[i][j],1,leny,1);
}
}
printf("%lld\n",ans);
}
