主题

主题

 
   

关于整体二分以及代码的笔记

  • 一道题

(这玩意毕竟也是论文里面的东西,在此做笔记罢)

求区间第k小的数。

这个主席树尚且是比较简单的。由于没有强制在线,我们可以用整体二分来做。

我们二分答案mid。

如果这个区间内比mid小的数字个数sum小于或等于查询的k,就应该把mid调小一点。否则我们就把mid调大一点。

现在有很多个询问。

那么我们当前就处理(ansl,ansr,S)的问题。S是询问的集合。

(询问的集合我们可以通过对询问顺序的调整,来实现对S的)

所以用一棵树状数组。这棵树状数组的下标是区间的下标。每一次我们把当前[ansl..ansr]的所有元素插入到树状数组中。之后我们对于一个询问,查询有多少个小于或等于mid的数字。

如果sum小于或等于k,就把这些询问放到左边,否则就放到右边。放在右边的询问,k需要减去当前的sum。

当ansl=ansr的时候,就是递归终点。此时被分到[ansl..ansr]的区间的询问,答案就是ansl(ansr)。


  • 扯淡

整体二分的思想不难。但是写起来总是有一些人糊里糊涂边界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:

代码


 

  • 复杂度相关?

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

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

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






 
 
评论
 
 
热度(1)