BZOJ 1227 [SDOI2009] 虔诚的墓主人 离线+树状数组+离散化

鸣谢：140142耐心讲解缕清了我的思路题意：由于调这道题调的头昏脑涨，所以题意自己搜吧，懒得说。方法：离线+树状数组+离散化解析：首先深表本蒟蒻对出题人的敬(bi)意(shi)。这道题简直丧心病狂，看完题后大脑一片空白，，整个人都不好了，刚开始的思路是什么呢？暴力思想枚举每个墓碑，然后计算每个墓碑的虔诚度，然后再来统计。不过看看数据范围呢？10^9*10^9的矩阵，最多才10^5个树，光枚举就已经超时了，所以肯定不行。(不过要是考试真没思路我就那么搞了- -！)然后也想到来枚举墓碑，不过还是些许犹豫，毕竟偏差较大，写的话实现难。然后我就不知道怎么搞了。今天140142神犇耐心的给我讲了大体的思路。就是呢，把所有的点按x从大到小,x相同y从大到小排序，然后呢一个个来枚举。

用如上的图来说。先明确树状数组在本题是如何体现的。首先这个树状数组存的值是什么？其中，c是组合数，u[i]是对于i这个总坐标，当前的上面的树的个数，d代表向下求。现在这些点的顺序应该已经排好了，那么我来模拟一下正解的过程。显然第一个遍历的点应该是[0，3]。这时候我们能做什么呢？ 统计他的左边有多少点，右边有多少点，当然，把他归到左边。为什么？因为我们是从左到右处理，所以后面假设这一排还有点的话，[0,3]这个点当然在左边。统计完左右后，我们还能维护当前的上下，道理差不多吧。经过很多的实验，个人认为统计这些点上下左右最好用map来搞，非常实用。以上就是第一个遍历过程。接下来，到[1,3]这个点，此时呢，这个点又到了新的一排，所以左右的话应该重新维护一下，而上下呢？显然只是上–，下++。但是这时候就要注意了。在对上下进行操作之前，当前的树状数组显然存的是[0,3]时候的值，所以我们要进行更新。而怎么更新呢？因为现在树状数组存的是，而我们要将之更新成，也就是对应着上–，下++。为什么要这么做呢?让我们接着遍历。[3,0]这个点同样换行了，所以维护左右，上下也填到树状数组。[3,1]这个店没有换行，所以左++，右–，上下填到树状数组。

**

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

**

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

所以说，树状数组的作用就是维护这段区间的的和的，只不过是多了动态更新，也就是每个点过后，都要重新更新树状数组的值。树状数组的用法就说完了，如果没懂，亦或是看看别人的题解，亦或是请教请教AC的人，亦或是理解理解上面这个求和公式。接下来图中我特意留了几个空行，我们发现，2,4,7这三列并没有什么卵用，完全可以删除掉，不过这个删除是必须的，因为10^9的边长的矩形，咱们只算其中10^5个点，光是内存就开不下，所以离散化一下列，也就是纵坐标是必然的。后记：我太弱ll ;;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) ;}

回味起来却有久久不会退去的余香。