题面描述

样例输入

5 6

13

0 2

0 3

1 2

1 3

2 0

2 1

2 4

2 5

2 6

3 2

3 3

4 3

5 2

2

样例输出

6

题解

这题真是(#@-^%~!*.......)

简直变态啊，好好的一个坟头非得整出一道题。。。

算了，甭说了分析一下题目吧。

我们发现这题的 \(n,m\) 范围是达到了10亿的级别。这。。。

好像直接想不出正解，我们先去看看部分分。

发现 \(n,m \leqslant 1000\) 的这部分好像可做。

我们 \(O(N^2)\) 对于每个点扫过去，然后如果这个点不是常青树就可以统计一下答案，怎么统计呢？

考虑组合数学：

设在某个方向上有 \(a\) 个常青树，我们只要选 \(k\) 个那么就是 \(C_{a}^{k}\)，这个点的方案数就是所有方向的这些方案乘起来。

愉快的解决子问题之后考虑解决本题。

然后我们发现一个性质：

图片全部由睿智画图生成，见谅

当点位于两棵树之间时其实他们在 \(y\) 轴方向的方案是一样的。

那么我们考虑快速直接的求出一段常青树之间的区间的方案数。

原来的是：

\(\sum_{i=tree[l]}^{tree[r]} C_{L[i]}^{k}*C_{R[i]}^{k}*C_{U[i]}^{k}*C_{D[i]}^{k}\)

根据乘法分配率可以直接提出变成

\(C_{U[i]}^{k}*C_{D[i]}^{k}*\sum_{i=tree[l]}^{tree[r]}C_{L[i]}^{k}*C_{R[i]}^{k}\)

又想到刚刚的性质，那么我们是不是可以快速求出这个式子的前半部分，后半部分怎么办呢？

我们不但要支持查询一段区间\(C_{L[i]}^{k}*C_{R[i]}^{k}\)的和,还要让这个 \(L[i],R[i]\) 发生变化。

这个时候灵光一闪————

我们将题目给我们的坐标们排个序(\(x\)第一关键字，\(y\)第二关键字)这样所有x相同的点都在一起，我们就可以直接求出这段区间的那个式子的前半部分，后半部分的维护又想到要支持区间求和和单点修改。想到树状数组。

考虑到写一个二维的树状数组还是很难维护，那么我们索性用一维的，把 \(x\) 那一维统统交给排序处理，这样我们只要记录一个树状数组 \(s[i]\) 表示当在 \(y\) 轴 \(i\) 方向的时候已经放了 \(s[i]\) 个常青树在左边，那么右边就可以动态地用总的个数减一减或者直接动态维护(减一减，加一加)。

对于 \(x\) 坐标 相同的我们每次只要同样动态维护下面有几个常青树了。

至于代码应该蛮好写了，代码不懂的可以看看代码注释。

还是蛮好的一道题可以锻炼思维，不懂的欢迎私信(大概意一时半会二不会AFO)。

扶我起来我还能苟,

#include
    
     using namespace std;#define int long long #define x first#define y secondinline char gc(){    static char buf[1<<20],*p1=buf,*p2=buf;    if(p1==p2){        p2=(p1=buf)+fread(buf,1,1<<20,stdin);        if(p1==p2) return EOF;    }    return *p1++;}inline int read(){    int x=0;char ch=gc();    while(!isdigit(ch)) ch=gc();    while(isdigit(ch)) x=x*10+ch-'0',ch=gc();    return x;}int w;typedef pair
     
       PII;const int N=1e5+5,P=2147483648LL;int x[N],y[N],c[N][15];// c是组合数int t[N],s[N];// t为当纵坐标是t时左边常青树的个数int NumOfX[N],NumOfY[N];// 这两个分别表示横坐标为x的点的个数和纵坐标为y的个数（总个数）PII p[N];// 用来存一下离散之后的坐标，pair真好用inline int lowbit(int x){    return x&(-x);}inline void update(int x,int plus){    plus%=P;    while(x<=w){        s[x]=(s[x]+plus)%P;        x+=lowbit(x);    }}inline int query(int x){    int ret=0;    while(x){        ret=(ret+s[x])%P;        x-=lowbit(x);    }    return ret;}// 树状数组signed main(){    read();read();    w=read();    for(int i=1;i<=w;++i) x[i]=p[i].x=read(),y[i]=p[i].y=read();    int k=read();    c[0][0]=1;    for(int i=1;i<=w;++i){        c[i][0]=1;        for(int j=1;j<=k;++j)            c[i][j]=(c[i-1][j]+c[i-1][j-1])%P;    }    sort(x+1,x+w+1);    sort(y+1,y+w+1);    for(int i=1;i<=w;++i)         p[i].x=lower_bound(x+1,x+w+1,p[i].x)-x,NumOfX[p[i].x]++;    for(int i=1;i<=w;++i)         p[i].y=lower_bound(y+1,y+w+1,p[i].y)-y,NumOfY[p[i].y]++;    // 离散和初始化组合数    sort(p+1,p+w+1);    int DOWN=1,ans=0;// DOWN记录当前常青树的下面（包括当前）有几棵常青树    for(int i=1;i