CDQ分治与整体二分小结

前言

  这是一波强行总结。

  下面是一波瞎比比。

  这几天做了几道CDQ/整体二分,感觉自己做题速度好慢啊。

  很多很显然的东西都看不出来 分治分不出来 打不出来 调不对

  上午下午晚上的效率完全不一样啊。

  完蛋.jpg 绝望.jpg。

关于CDQ分治

  CDQ分治,求的是三维偏序问题都知道的。

  求法呢,就是在分治外面先把一维变成有序

  然后分治下去,左边(l,mid)关于右边(mid+1,r)就不存在某一维的逆序了,所以只有两维偏序了。

  这个时候来一波"树状数组求逆序对"的操作搞一下二维偏序

  就可以把跨过中线的,左边更新右边的情况计算出来。

  注意:只计算左边的操作对右边的询问的贡献!

  然后左右两边递归处理就好了。

  正确性:按照线段树的形态递归的CDQ分治,保证每一对三元组在线段树上都有且仅有一个LCA(这不废话吗),而这一组答案就会且仅会在LCA处计算。如果在LCA下面,点对不在一个work内自然不会计算。如果在LCA上面了,点对就在同一侧,不会互相更新。

  复杂度:设一次work的复杂度是f(len),则复杂度是O(f(n)logn)。

  一般都在分治里用树状数组,一般的复杂度就是O(nlog2n)的。

  一般是这样的套路:假设三维偏序分别为a,b,c;

  在main函数里保证a递增。

  然后在CDQ里先分治左右,传下去的时候a仍然递增,不破坏性质。

  然后分治完左右两边后,需保证左右两边分别b都是递增的(a不重要)。

  然后就是类似归并排序的操作了。

  此时左边的a肯定都小于右边的a,那么如果对于一个右边的元素

  之前类似归并的操作就可以保证所有小于b的左边的元素都已经遍历过。

  那么找c也小于它的?值域线段树/树状数组等数据结构维护一下就好了。

  然后你这么归并了一波后,就发现统计完答案后b是有序递增的了(这个时候a已经不重要了)。

  对于上层操作,符合"左右两边分别b是递增的"了。

  BZOJ陌上花开竟然是权限题?这是在搞笑。

  好吧BZOJ动态逆序对,之前写过的,做两次CDQ就好了。

  BZOJ稻草人,也是CDQ。

  

关于整体二分

  整体二分主要是把所有询问放在一起二分答案,然后把操作也一起分治。

  讲起来有些玄学。

  想想:二分答案的时候,对于一个答案,是不是有些操作是没用的?

  比如二分一个时间,那么时间后面发生的操作就是没有用的。

  二分一个最大值,比mid大的都是没用的。

  整体二分就是利用了这么一个性质。

  二分答案,然后把没有用的操作扫进右边,和答案在[mid+1,r]的询问一起递归处理。

  把有用的操作放进左边,和答案在[l,mid]的一起递归处理。

  注意答案在[mid+1,r]的询问要算上放进了左边的操作的贡献,开个变量记下来/直接减掉都可以。

  注意整体二分在solve内的复杂度一定只能与区间长度线性相关,不能每次都有别的复杂度!

  比如一次solve的复杂度是O(lenlogn)就可以,O(len+m)就不行。

  大概就是这么一个东西。

  复杂度?和CDQ是一样的,都是O(f(len)logn)。

  例题?BZOJ3110 K大数查询 Codevs Meteors。

  一样的套路了。

关于一些要注意的地方

  归并一定要把剩下的搞完!每次我都忘记这码子事!

  树状数组不能暴力清零!记个time或者依葫芦画瓢减回去都可以,一定不能清零!

  不要在CDQ里面套sort,太慢辣!

时间: 08-25

CDQ分治与整体二分小结的相关文章

CDQ分治与整体二分总结

Cdq分治和整体二分是两个很奇妙的东西.他们都是通过离线的思想来进行优化,从而更快的求出解. 整体二分通俗的讲就是二分答案,但是它了不起的地方是一下子把所有的答案都二分出来了,从而可以一下子得出所有查询. CDQ分治通俗的讲就是二分查询.通常的做法是把所有的查询分成两半,然后通过递归先计算出左边一半的所有的查询,然后通过这些已知的左半边的值来更新右半边的值.这里,最最重要的思想是通过左半边来更新右半边.更具体一点,就是用左半边的修改来更新右半边的查询. 重要的事情说话三遍: CDQ分治就是通过左

【cdq分治】cdq分治与整体二分学习笔记Part1.整体二分

之所以把cdq分治和整体二分放在一起学习,是因为他们两个实在太像了-不管是做法还是代码- 感觉整体二分可能会比cdq分治稍微简单那么一点点?所以先学整体二分.(感觉他们的区别在于整体二分是对每个操作二分答案,cdq是分治了操作序列) 整体二分是对答案进行二分,其具体操作如下: (比如以ZJOJ2013K大数查询为例) 具体过程 Step1.从(L,R)二分答案.mid=(L+R)>>1,用线段树维护原序列中(a,b)位置比mid大的数有多少个,同时记录对序列的操作分别是什么操作. Step2.

[整体二分]【学习笔记】【更新中】

先小结一下吧 主要为个人理解 整体二分 理解 $zyz:$整体二分是在权值上进行$CDQ$分治 我觉得更像是说$:$整体二分是在答案上进行$CDQ$分治 整体二分是二分答案在数据结构题上的扩展 因为数据结构题二分的答案通常是第几个操作之后,需要进行一些操作(预处理)之后才能判断,所以每次询问二分还不如从前往后暴力找 整体二分可以解决这样的问题 核心就是维护一个$cur$数组保存当前的影响,分治到$[l,r]$时只需要计算$[l,mid]$的影响再与$cur$里的合并就好了 这样分治里的操作就只与

4538: [Hnoi2016]网络 链剖 + 堆(优先队列) / 整体二分

GDOI之后写的第一道题.看到之后没什么感觉(是我太弱,中途一度想用kpm之前在某道题上用过的链表的方法.想了想应该不可能.) 好!让我们来分析这道题吧!首先简化模型,它是要求维护树上的一些路径,支持添加和修改,要求不经过某个点的路径的最大权值(不经过某个点,我一度想到了动点分,虽然我还不会). 我们可以先考虑在链上(其实仔细一想,如果链上的你会做,那么树上的大多数情况下便是多个了链剖而已吧!)的情况.在链上,有一些区间覆盖,要求没有覆盖某个点的区间的最大权值.那么我们接着想如果询问2询问了一个

整体二分初探 两类区间第K大问题 poj2104 & hdu5412

看到好多讲解都把整体二分和$CDQ$分治放到一起讲 不过自己目前还没学会$CDQ$分治 就单独谈谈整体二分好了 先推荐一下$XHR$的 <浅谈数据结构题的几个非经典解法> 整体二分在当中有较为详细的讲解 先来说一下静态第$K$小的整体二分解法 $(POJ2104)$ 题目链接:http://poj.org/problem?id=2104 所谓整体二分 就是利用所有的询问相互独立而把它们$($此题没有修改操作$)$通过二分把它们分治进行处理 不妨先来考虑下一个简单易懂的$O(NlogS)$的排序

整体二分初步

部分内容引自myt论文:树状数组延伸和离线优化(CDQ.整体二分和莫队) 大致思路 1.确定答案范围[L,R],mid=L+R>>1;2.算出答案在[L,mid]内的操作对答案在[mid+1,R]内的操作的贡献;3.将答案在[L,mid]内的操作放入队列Q1,solve(Q1,L,mid)将答案在[mid+1,R]内的操作放入Q2,solve(Q2,mid+1,R) 伪代码 divide(hd,tl,l,r){ if(hd>tl) exit if(l==r){ for(i->hd

【bzoj3672】[Noi2014]购票 斜率优化+CDQ分治+树的点分治

题目描述 给出一棵以1为根的带边权有根树,对于每个根节点以外的点$v$,如果它与其某个祖先$a$的距离$d$不超过$l_v$,则可以花费$p_vd+q_v$的代价从$v$到$a$.问从每个点到1花费的最小代价(中途可以经停其它点) 输入 第 1 行包含2个非负整数 n,t,分别表示城市的个数和数据类型(其意义将在后面提到).输入文件的第 2 到 n 行,每行描述一个除SZ之外的城市.其中第 v 行包含 5 个非负整数 $f_v,s_v,p_v,q_v,l_v$,分别表示城市 v 的父亲城市,它到

整体二分

随便写一点整体二分的东西. 这个整体二分啊,非常的简单 拿最简单的出来说吧 poj2104 n,m<=100000 给一个长为n的数列a,有m个询问 每次输入l,r,k询问al~ar中第k小的是哪一个. [solution] 你们可能说主席树. 然而有一个空间只要O(n)的做法,没错,就是整体二分. 那么这个整体二分是什么呢. 首先,我们把询问丢进一个struct 里面 然后我们二分一个答案mid 然后我们O(nlogn)求出每个询问的范围中<=mid的数的个数tot 显然啊,如果这个数量to

初学CDQ分治-NEU1702

关于CDQ分治,首先需要明白分治的复杂度. T(n) = 2T(n/2)+O(kn), T(n) = O(knlogn) T(n) = 2T(n/2)+O(knlogn), T(n) = O(knlog^2n) T(n) = 2T(n/2)+O(k), T(n) = O(kn) 那么我们要处理[l, r]内的询问,我们可以分别处理[l, m]和[m+1, r]的询问,然后以较小的复杂度计算出[l, m]对[m+1, r]的贡献. 最简单的cdq就是三维偏序问题. 两点(x1, y1, z1)和(