学习笔记-cdq

暑假学了cdq，搞得不是特别明白，写一篇博客梳理一下。

cdq算法是什么？

最开始我对它的理解是归并排序，这个理解终究是狭隘了。归并排序只是cdq算法的一小部分，连冰山一角都说不上。

CDQ算法指的是：

(1.)对于一个问题：划分左右区间 ([l, mid])和([mid + 1, r])
(2.)分别解决左区间和右区间的子问题
(3.)计算左区间对右区间的影响
(4.)合并左右区间得到原问题的解。

看起来很简单的样子，正因为如此，cdq的应用范围十分的广泛，从归并排序开始，到优化dp再到各种模型，你可以在很多地方看到cdq的身影
光说不练假把式，了解了定义并不代表掌握了这个算法，需要做相关的练习。
那么就从一些题目入手，来巩固学习cdq分治，掌握其核心思想

T1 LuoguP1908逆序对

对于给定的一段正整数序列，逆序对就是序列中 (a_i>a_j) 且 (i<j) 的有序对。
暴力无疑是很好想的那么我们如何入手优化呢
首先，我们假设自己没有立刻想到cdq算法，而是从最原始的开始一步步推导，
我们要找到 (a_i>a_j) 且 (i<j) ，那么是不是对于一个a_i，不重复的话只有后面的可以影响到它的答案统计
再看暴力是如何运作的，

    for(register int i=1;i<=n;++i)
      a[i].x=read(),a[i].id=i;
    sort(a+1,a+n+1);

然后再根据位置关系进行统计，既然如此，考虑排序方式，有什么办法可以快速统计后面的会产生贡献的元素呢？
这个时候我们就会想到归并算法。 (ightarrow cdq) 算法就此登场！

绕了一大圈子，主要是想讲明思维的推导过程，这种思维方式同样也可以运用到之后的学习

T2 [Violet 3]天使玩偶

这道题先考虑回忆出来的点都在询问的点左下方时：则当(x_B + y_B)取到最大值时，(Dis(A,B)) 有最小值。实际上就是三维偏序
至于三维偏序：利用树状数组和归并进行操作
(cdq)分治每次计算前一半对后一半的影响。
具体地，
假设三维分别是 (x,y,z，)
先按(x)排序。分治时每次将前半边、后半边分别按(y)排序。
虽然现在(x)的顺序被打乱了，但是前半边还是都小于后半边的，所以要是只计算前半边对后半边的偏序关系，是不会受到(x)的影响的。
维护后一半的指针(p)，前一半的指针(q)，每次将(p)后移一位时，若(y[q]<=y[p])则不断后移(q)，并不断将(z[q])加入树状数组。然后再查询树状数组中有多少数小于等于(z[p])。
最后要清空树状数组。