主题

主题

 
   

关于整体二分代码的笔记

  • 扯淡

整体二分的思想不难。但是写起来总是有一些人糊里糊涂边界RE什么的。比方说本蒟。

于是在这里再次整理一下整体二分的代码。

这一次的看上去比较好看了。虽然好像还是有点长。


  • 多个参数(l,r)

我们可能在二分的时候,有一个ansl与ansr,我们也有一个表示集合的数组quel与quer。

然后本蒟就搞不清mid啥的到底怎么做。

后来想到是二分答案啊——那自然是分ansl与ansr啊。


  • 怎么维护集合

本蒟感觉swap的方法比较繁琐,加上本来就不太清楚边界情况。所以用的是归并的思想。

假设现在我们用A数组来进行二分判断。用一个临时数组tmp。定义tmp数组的指针tl与tr。

每一次确定了应该放在左边还是右边的时候,就让两个指针移动。

最后把这个tmp数组复制给原来的A数组。

另一种方法——我们可以采取指针+vector的方法,空间复杂度是O(nlogans)的。


  • 参数的边界

我们发现每一次的递归是(ansl,mid)与(mid+1,ansr)。那么类比线段树的部分,答案的边界情况自然是ansl==ansr。然后把当前[quel..quer]的询问处理完。

然而quel与quer则不同。

看着本蒟的代码——

在最初始话的时候,tl=quel-1,tr=quer+1,当有一个询问应该被扔到左边的时候,我们做的操作是tmp[++tl]=A[vi];当有一个询问应该被扔到右边的时候,我们做的操作是tmp[tr--]=A[vi]。

最后的时候递归中,集合的参数为(quel,tl)与(tr,quer)。

这样就会出现在一个递归程序里面quel>quer的情况。

所以集合的边界情况是quel>quer。


  • 代码

最后搬一个代码吧,BZOJ 2738:

https://code.csdn.net/snippets/2213874


 

  • 复杂度相关?

我们递归最多有O(log(ans))层。所以一个询问最多会被处理O(log(ans))次。

这样就复杂度就比较清晰了。

如果一个询问的二分判断是O(k)的,一层的处理是O(f)的,那么复杂度就是O(mklog(ans)+flog(ans))。






 
 
评论
 
 
热度(1)