Luogu

分析

设一块墓地上、下、左、右的常青树数量分别为 $u,d,l,r$，那么这块墓地的虔诚值显然为

$$ {u\choose k}{d\choose k}{l\choose k}{r\choose k} $$

直接考虑每块墓地显然是不行的，我们考虑横坐标相同、纵坐标连续的一段墓地。

这段墓地的虔诚值总和为

$$ {u\choose k}{d\choose k}\sum_{i=y_1}^{y_2}{l_i\choose k}{r_i\choose k} $$

考虑如何维护 $\sum$ 后面的东西，显然可以用一棵支持区间求和的线段树来维护，每次扫过一个点后就修改掉即可。

另外模数是 $2^{31}$ ，可以使用 int 的溢出。

具体实现及细节见代码。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,K=10+10;

int n,k;
struct point { int x,y; } p[N];
int Sx[N],topx=0,Sy[N],topy=0;
vector<int> x[N]; int sy[N];
int C[N][K];

#define ls (o<<1)
#define rs (o<<1|1)
int sl[N<<2],sr[N<<2],sumv[N<<2];
inline void pushup(int o) { sumv[o]=sumv[ls]+sumv[rs]; }
inline void build(int o,int l,int r) {
    if (l==r) { sr[o]=sy[l]; return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
inline void modify(int o,int l,int r,int p) {
    if (l==r) {
        ++sl[o],--sr[o];
        sumv[o]=C[sl[o]][k]*C[sr[o]][k];
        return;
    }
    int mid=(l+r)>>1;
    if (p<=mid) modify(ls,l,mid,p);
    else modify(rs,mid+1,r,p);
    pushup(o);
}
inline int query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return sumv[o];
    int mid=(l+r)>>1,res=0;
    if (ql<=mid) res+=query(ls,l,mid,ql,qr);
    if (qr>mid) res+=query(rs,mid+1,r,ql,qr);
    return res;
}
#undef ls
#undef rs

int main() {
    read(),read(),n=read();
    for (re int i=1;i<=n;++i) {
        Sx[++topx]=p[i].x=read();
        Sy[++topy]=p[i].y=read();
    }
    sort(Sx+1,Sx+topx+1),topx=unique(Sx+1,Sx+topx+1)-Sx-1;
    sort(Sy+1,Sy+topy+1),topy=unique(Sy+1,Sy+topy+1)-Sy-1;
    for (re int i=1;i<=n;++i) {
        p[i].x=lower_bound(Sx+1,Sx+topx+1,p[i].x)-Sx;
        p[i].y=lower_bound(Sy+1,Sy+topy+1,p[i].y)-Sy;
    }
    for (re int i=1;i<=n;++i) {
        x[p[i].x].push_back(p[i].y);
        ++sy[p[i].y];
    }
    k=read();
    for (re int i=C[0][0]=1;i<=n;++i)
        for (re int j=C[i][0]=1;j<=min(i,k);++j)
            C[i][j]=C[i-1][j]+C[i-1][j-1];
    build(1,1,topy); int ans=0;
    for (re int i=1;i<=topx;++i) {
        sort(x[i].begin(),x[i].end());
        modify(1,1,topy,x[i][0]);
        for (re int j=1;j<x[i].size();++j) {
            if (x[i][j]-x[i][j-1]>=1)
                ans=(ans+C[j][k]*C[x[i].size()-j][k]
                        *query(1,1,topy,x[i][j-1]+1,x[i][j]-1));
            modify(1,1,topy,x[i][j]);
        }
    }
    printf("%d\n",ans<0?ans+2147483648:ans);
    return 0;
}