鸣谢：140142耐心讲解缕清了我的思路

题意：由于调这道题调的头昏脑涨，所以题意自己搜吧，懒得说。

方法：离线+树状数组+离散化

解析：首先深表本蒟蒻对出题人的敬(bi)意(shi)。这道题简直丧心病狂，看完题后大脑一片空白，整个人都不好了，刚开始的思路是什么呢？暴力思想枚举每个墓碑，然后计算每个墓碑的虔诚度，然后再来统计。不过看看数据范围呢？10^9*10^9的矩阵，最多才10^5个树，光枚举就已经超时了，所以肯定不行。(不过要是考试真没思路我就那么搞了- -！)

然后也想到来枚举墓碑，不过还是些许犹豫，毕竟偏差较大，写的话实现难。然后我就不知道怎么搞了。

今天140142神犇耐心的给我讲了大体的思路。

就是呢，把所有的点按x从大到小,x相同y从大到小排序，然后呢一个个来枚举。

用如上的图来说。

先明确树状数组在本题是如何体现的。

首先这个树状数组存的值是什么？

$c[u[i]][K]*c[d[i]][K]$其中，c是组合数，u[i]是对于i这个总坐标，当前的上面的树的个数，d代表向下求。

现在这些点的顺序应该已经排好了，那么我来模拟一下正解的过程。

显然第一个遍历的点应该是[0，3]。

这时候我们能做什么呢？ 统计他的左边有多少点，右边有多少点，当然，把他归到左边。为什么？因为我们是从左到右处理，所以后面假设这一排还有点的话，[0,3]这个点当然在左边。

统计完左右后，我们还能维护当前的上下，道理差不多吧。

经过很多的实验，个人认为统计这些点上下左右最好用map来搞，非常实用。

以上就是第一个遍历过程。

接下来，到[1,3]这个点，此时呢，这个点又到了新的一排，所以左右的话应该重新维护一下，而上下呢？显然只是上–，下++。但是这时候就要注意了。在对上下进行操作之前，当前的树状数组显然存的是[0,3]时候的值，所以我们要进行更新。而怎么更新呢？

因为现在树状数组存的是$c[u[3]][K]*c[d[3]][K]$，

而我们要将之更新成$c[u[3]-1][K]*c[d[3]+1][K]$，也就是对应着上–，下++。为什么要这么做呢?

让我们接着遍历。

[3,0]这个点同样换行了，所以维护左右，上下也填到树状数组。

[3,1]这个店没有换行，所以左++，右–，上下填到树状数组。

**

关键就是到了[3,5]这个点。

**

我们可以看出，此时他与[3,1]之间是有3个点满足题意的。那我们就要把这三个点的值加到答案上(其实[3,1]时也有这个过程，只不过它与上一个点紧挨着，所以不可能有解，被我跳过了)而这个加的值应该是什么？

$$(\sum_{i=2}^4c[u[i]][K]*c[d[i]][K])*c[l[5-1]][K]*c[r[5-1]][K]$$

所以说，树状数组的作用就是维护这段区间的$c[u[i]][k]*c[d[i]][k]$的和的，只不过是多了动态更新，也就是每个点过后，都要重新更新树状数组的值。

树状数组的用法就说完了，如果没懂，亦或是看看别人的题解，亦或是请教请教AC的人，亦或是理解理解上面这个求和公式。

接下来

图中我特意留了几个空行，我们发现，2,4,7这三列并没有什么卵用，完全可以删除掉，不过这个删除是必须的，因为10^9的边长的矩形，咱们只算其中10^5个点，光是内存就开不下，所以离散化一下列，也就是纵坐标是必然的。

后记：我太弱

#include <stdio.h>
#include <map>
#include <algorithm>
#define N 100100
#define mod 2147483648ll
typedef long long ll ;
using namespace std ;
struct node
{
    int x ;
    int y ;
};
node a[N] ;
int n , m , K;
int w , tot;
map <int , int> M ;
map <int , int> line ;
map <int , int> line_x ;
ll c[N][11] ;
int yy[N] ;
int f[N] ;
int u[N] ;
ll sum[N] ;
int d[N] ;
int lowbit(int x)
{
    return x & (-x) ;
}
void update(int x , ll p)
{
    while(x <= tot)
    {
        sum[x] = (sum[x] + p)% mod ;
        x += lowbit(x) ;
    }
}
ll getsum(int x)
{
    ll ret = 0 ;
    while(x)
    {
        ret = (ret + sum[x])%mod ;
        x -= lowbit(x) ;
    }
    return ret ;
}
void init()
{
    c[0][0] = 1 ;
    for(int i = 1 ; i <= w ; i++)
    {
        c[i][0] = 1 ;
        int tmp = min(i , K) ;
        for(int j = 1 ; j <= tmp ; j++)
        {
            c[i][j] = (c[i-1][j] + c[i-1][j-1])%mod ;
        }
    }
}
bool cmp(node a , node b)
{
    if(a.x == b.x) return a.y < b.y ;
    return a.x < b.x ;
}
ll ans ;
int main()
{
    scanf("%d%d" , &n , &m) ;
    scanf("%d" , &w) ;
    for(int i = 1 ; i <= w ; i++)
    {
        scanf("%d%d" , &a[i].x , &a[i].y) ;
        yy[i] = a[i].y ;
        line[a[i].y] ++ ;
        line_x[a[i].x] ++ ;
    }
    scanf("%d" , &K) ;
    init() ;
    sort(a + 1 , a + w + 1 , cmp) ;
    sort(yy + 1 , yy + w + 1) ;
    yy[0] = -1 ;
    for(int i = 1 ; i <= w ; i++)
    {
        if(yy[i] != yy[i-1])
        {
            M[yy[i]] = ++tot ;
            f[tot] = yy[i] ;
        }
    }
    for(int i = 1 ; i <= tot ; i++)
    {
        u[i] = line[f[i]] ;
        d[i] = 0 ;
    }
    int tmp_line = -1 ;
    int l , r ;
    for(int i = 1 ; i <= w ; i++)
    {
        if(a[i].x != tmp_line)
        {
            tmp_line = a[i].x ;
            l = 1 , r = line_x[a[i].x] - 1 ;
            int ori = M[a[i].y] ;
            update(ori , (c[u[ori]-1][K]*c[d[ori]+1][K]%mod-c[u[ori]][K]*c[d[ori]][K]%mod)%mod) ;
            u[ori]-- ;
            d[ori]++ ;
        }else
        {
            ll S = getsum(M[a[i].y]-1) - getsum(M[a[i-1].y]) ;
            if(S < 0) S += mod ;
            ans = (ans + ((S*c[l][K])%mod * c[r][K])%mod)%mod ;
            l ++ , r-- ;
            int ori = M[a[i].y] ;
            update(ori , (c[u[ori]-1][K]*c[d[ori]+1][K]%mod-c[u[ori]][K]*c[d[ori]][K]%mod)%mod) ;
            u[ori] -- ;
            d[ori]++ ;
        }
    }
    printf("%lld\n" , ans) ;
}