萌萌哒cdq分治

cdq分治的思想非常简单, 就是每次分别递归处理在左半边区间内和右半边区间内答案的贡献, 然后像归并排序一样把左半边和有半边合起来, 顺带统计一下左半边区间中的修改对右半边区间中的询问做出的贡献。 归并排序求逆序对就是cdq分治最简单的应用了。

容易分析得出应用到cdq分治时需要满足这些条件:每个修改对于每个询问的影响都是独立的; 我们可以快速地统计出来一堆指定修改操作对一个询问总共的贡献。

经典的应用比如说数点问题。

bzoj 3262: 陌上花开

是最简单的三维数点, 这时候直接把第一维排一个序, 然后第二维上cdq分治, 合并的时候如果一个询问点原属于右半边区间, 那么所有原属于左半边区间(即第一维比询问点大)且合并后在它前面(即第二维比询问点大)且第三维比询问点大的点都会对询问点有着1的贡献。 所以只需要把合并后的序列从小往大扫一遍, 然后用一个树状数组存一下当前原属于左半边区间且第三维大于x的数有多少个, 那么每一个询问点在这次合并中就都可以做到O(logn)的查询了。

Tsinsen A1485. Catch The Penguins 抓企鹅(张闻涛)

四维数点

有很多种办法都可以搞, 比较简单的比如说上一个三维数点然后开一个树状数组套平衡树就行了。

yy了cdq分治套cdq分治的做法, 也非常简单。 接着上面三维的那个说,我们合并完左右区间后想要加入在pos处的询问的答案是所有当前位置小于pos且原来在左半边区间的点, 而这个就又转化为了一个三维数点问题了! 原来在左半边的所有询问和原来在右半边的所有修改在当前都是没有意义的了删掉就好了。

这种做法的一个非常好的地方就是可以一直加维数加下去, 每加一维就套上一层cdq分治, 时间复杂度套一个log, 但是它的优点在于空间复杂度始终是O(n)的啊O(n)的啊, 当套到更多维的时候树套树会越发地不好写但是这样做始终非常好些哒。

时间: 05-06

萌萌哒cdq分治的相关文章

CDQ分治与整体二分小结

前言 这是一波强行总结. 下面是一波瞎比比. 这几天做了几道CDQ/整体二分,感觉自己做题速度好慢啊. 很多很显然的东西都看不出来 分治分不出来 打不出来 调不对 上午下午晚上的效率完全不一样啊. 完蛋.jpg 绝望.jpg. 关于CDQ分治 CDQ分治,求的是三维偏序问题都知道的. 求法呢,就是在分治外面先把一维变成有序 然后分治下去,左边(l,mid)关于右边(mid+1,r)就不存在某一维的逆序了,所以只有两维偏序了. 这个时候来一波"树状数组求逆序对"的操作搞一下二维偏序 就可

【BZOJ3963】[WF2011]MachineWorks cdq分治+斜率优化

[BZOJ3963][WF2011]MachineWorks Description 你是任意性复杂机器公司(Arbitrarily Complex Machines, ACM)的经理,公司使用更加先进的机械设备生产先进的机器.原来的那一台生产机器已经坏了,所以你要去为公司买一台新的生产机器.你的任务是在转型期内尽可能得到更大的收益.在这段时间内,你要买卖机器,并且当机器被ACM公司拥有的时候,操控这些机器以获取利润.因为空间的限制,ACM公司在任何时候都只能最多拥有一台机器. 在转型期内,有若

BZOJ 2225 [Spoj 2371]Another Longest Increasing(CDQ分治)

[题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=2225 [题目大意] 给定N个数对(xi,yi),求最长上升子序列的长度. 上升序列定义为{(xi,yi)}满足对i<j有xi<xj且yi<yj. [题解] CDQ分治,将每个区间按照a排序,用区间左边的数据来更新右边的最长上升序列, 为排除a相等但是b上升情况的误统计,在排序时加入下标作为第二关键字, 使得a相等的情况下标小的后更新. [代码] #include <cs

BZOJ 3262: 陌上花开 [CDQ分治 三维偏序]

Description 有n朵花,每朵花有三个属性:花形(s).颜色(c).气味(m),又三个整数表示.现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量.定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb.显然,两朵花可能有同样的属性.需要统计出评出每个等级的花的数量. Input 第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值. 以下N行,每

HDU 5618:Jam&#39;s problem again(CDQ分治+树状数组处理三维偏序)

http://acm.hdu.edu.cn/showproblem.php?pid=5618 题意:-- 思路:和NEUOJ那题一样的.重新写了遍理解了一下,算作处理三维偏序的模板了. 1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6 #define INF 0x3f3f3f3f 7 #d

ACdream1157 Segments(CDQ分治 + 线段树)

题目这么说的: 进行如下3种类型操作:1)D L R(1 <= L <= R <= 1000000000) 增加一条线段[L,R]2)C i (1-base) 删除第i条增加的线段,保证每条插入线段最多插入一次,且这次删除操作一定合法3) Q L R(1 <= L <= R <= 1000000000) 查询目前存在的线段中有多少条线段完全包含[L,R]这个线段,线段X被线段Y完全包含即LY <= LX <= RX <= RY) 初学CDQ分治是看了B

BZOJ 2726: [SDOI2012]任务安排( dp + cdq分治 )

考虑每批任务对后面任务都有贡献, dp(i) = min( dp(j) + F(i) * (T(i) - T(j) + S) ) (i < j <= N)  F, T均为后缀和. 与j有关的量只有t = dp(j) - F(i) * T(j) , 我们要最小化它. dp(j)->y, T(j)->x, 那么y = F(i) * x + t, 就是给一些点和一个斜率...然后最小化截距, 显然维护下凸包就可以了. 然后因为无比坑爹的出题人....时间可以为负数, 所以要用平衡树维护(

SPOJ LIS2 Another Longest Increasing Subsequence Problem 三维偏序最长链 CDQ分治

Another Longest Increasing Subsequence Problem Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19929 Description Given a sequence of N pairs of integers, find the length of the longest incre

CDQ分治与整体二分总结

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