整体二分小结

引入

离线算法是一类十分优秀的算法
整体二分就是其中一种可以吊打树套树

正题

什么时候用?
摘自(Fenghr)博客

当你发现多组询问可以离线的时候
当你发现询问可以二分答案而且check复杂度对于单组询问可以接受的时候
当你发现询问的操作都是一样的的时候

大体流程(代码可能好理解一些):

  1. 对所有询问一起二分一个答案
  2. 把对这个答案有影响的询问计算,丢在左边,其它在右边
  3. 把目前早已达到要求的询问丢在左边,其它计算好左边的修改后丢在右边
  4. 递归处理到头,答案赋值给询问

主要用来解决带修改区间第(k)大一类问题
至少在我写这篇博客前没见过其它类的

几道题

可能是难度排序

原文地址:https://www.cnblogs.com/cjoieryl/p/8423754.html