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

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

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

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

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

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

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

画了个很sb的图

用如上的图来说。

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

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

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]时也有这个过程，只不过它与上一个点紧挨着，所以不可能有解，被我跳过了)而这个加的值应该是什么？

(∑i=24c[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 
   
     #include
     #include 
     
       #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 
      
        M ; map 
       
         line ; map 
        
          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) ; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C++输出全排列递归算法详细解释	下一篇：UVALA 3641 Leonardo’s Notebook