學習筆記-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);

然后再根據位置關系進行統計，既然如此，考慮排序方式，有什么辦法可以快速統計后面的會產生貢獻的元素呢？
這個時候我們就會想到歸并演算法， \(\rightarrow 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]\)，
最后要清空樹狀陣列，

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/295924.html

標籤：C++

上一篇：【C++ Primer Plus】編程練習答案——第5章