hdu 5618 Jam’s problem again (cdq分治+BIT,三维偏序)

题目链接

题意:

If two point such as (xi,yi,zi) and (xj,yj,zj) xixj yiyj zizj, the bigger one level add 1

问每个point的level是多少。

思路:

cdq分治,先去重并统计相同的点的数量,需要注意要记录原id对应到了哪个新id

 

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行,每行三个整数si, ci, mi (1 <= si, ci, mi <= K),表示第i朵花的属性

Output

包含N行,分别表示评级为0…N-1的每级花的数量。

Sample Input

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

Sample Output

3
1
3
0
1
0
1
0
0
1

HINT

1 <= N <= 100,000, 1 <= K <= 200,000

 

思路:

第一发cdq分治,果然很好写。

cdq分治学习笔记

题目很裸,好像没什么好分析的。

代码风格的话,我是看lwt菊苣代码长大的

 

 

cdq分治学习笔记

起因是队里的大佬们都会这东西,而我一个老年选手竟然还不会,实在说不过去。

cdq分治显然是分治的一种,cdq的意思就是超短裙啦(

这东西网上资料很多(然而还是学不会

先放一波资料:

资料1

【教程】简易CDQ分治教程&学习笔记

[偏序关系与CDQ分治]【学习笔记】

学习笔记——cdq分治

[学习笔记] CDQ分治 从感性理解到彻底晕菜

lwt菊苣的博客

下面转自lwt菊苣的博客,豁然开朗。

  • 与普通分治的区别
    普通分治中,每一个子问题只解决它本身(可以说是封闭的)
    CDQ分治中,对于划分出来的两个子问题,前一个子问题用来解决后一个子问题而不是它本身
  • 适用的情况
    在很多问题中(比如大多数数据结构题),经常需要处理一些动态问题
    然而对动态问题的处理总是不如静态问题来的方便,于是就有了CDQ分治
    但使用CDQ分治的前提是问题必须具有以下两个性质:

    • 修改操作对询问的贡献独立,修改操作互不影响效果
    • 题目允许使用离线算法。
  • 一般步骤
    • 将整个操作序列分为两个长度相等的部分(分)
    • 递归处理前一部分的子问题(治1)
    • 计算前一部分的子问题中的修改操作对后一部分子问题的影响(治2)
    • 递归处理后一部分子问题(治3)

    特别说明:
    在整个过程中,最核心的就是步骤3
    此时前一部分子问题中的修改操作相对后一部分子问题来说是静态处理,因此可以更加方便地计算后一部分子问题

 

cdq分治求三维偏序美滋滋

一般是,第一维排序,第二维cdq,第三维套一层数据结构(不然的话就要数据结构套数据结构啦差评

cdq的复杂度和分治的复杂度一样也是O(nlgn),所以可以理解成cdq可以一层数据结构?因为比树套树之类好写,所以有广泛应用(?