學習筆記：CDQ分治

前言

感覺這是個很厲害的算法呀，因為到處都在用，然而網上資料不是很多，到底是為什麼呢？在終于參透了其中的奧妙之後我發現：它隻是一個政策而已了。而且，不難。

原理簡述

它用來幹什麼？

用于頂替一些複雜的資料結構，說白了呢，就是好寫常數小。換一種了解方式呢，就是你不會也沒什麼關系。

當然有時候它的确是可以化簡太多了，因為樹套樹什麼的的确不好寫哈，是以還是要學的。

還有個好處就是它占用的空間很少，也不需要離散什麼的。

它的條件是什麼？

1. 可以離線
2. 修改操作相對獨立

題外話：二維偏序是個什麼

二維偏序是CDQ分治的經典例題，是以說一下到底是個啥，其實就是那個二維樹狀數組的那種格式，在平面内，可以有兩個元素無法比較大小，無法通過簡單的排序得到答案。

舉個例子就是平面上有很多點，求每個點左上方有多少個點，這就是二維偏序問題了。

正式介紹了

最常見的一個CDQ分治是歸并排序求逆序對，沒錯，這就是CDQ分治，我們把它一般化就可以了（同時也可以看出它是可以被其他資料結構代替的，逆序對可以用樹狀數組求嘛）。

我們通過求逆序對來看看CDQ分治的過程。

遞歸處理左右兩邊之後，我們按照順序處理左邊元素對右邊元素的影響。

完了。

當然這個影響的處理就是CDQ分治的核心了，中途有很多技巧嘛。

用的時候要注意對于排序那一維的選擇，仔細想一想，其實很多時候是可以随便選的。。。隻不過習慣上喜歡用時間或者下标來排序而已了。

還有就是輸出答案的時候自己想點辦法吧，這個應該沒什麼難的。

來看看CDQ更加本質的東西

最基礎的CDQ分治處理的是二維的問題，其中把一維排序之後，就不用考慮這一維的影響了，然後處理另外一維，在加入了時間（一般展現為修改操作）這個元素後，由于把時間弄成了一維，那麼它就隻能處理一維的問題了。

通過這個原理回首一些資料結構，發現其中的确是有奧妙的，大多數資料結構都可以直接處理二維問題了。

如何向高維推廣？

比如二維的話是（最簡單情況）：先排序一維，分治的時候排序第二維

三維就是：前兩維同上，第三維就用樹狀數組來維護咯。

代碼

沒什麼特别的哎，我把逆序對的貼上來吧（滑稽

這裡是左閉右開

LL dvd(int *A,int x,int y)
{
    if(y-x==)
        return ;

    int m=(x+y)/;
    LL t3=,t1=dvd(A,x,m),t2=dvd(A,m,y);

    int i=x,j=m,k=x;
    while(i<m&&j<y)
    {
        if(A[i]>A[j])
        {
            t3+=m-i;
            t[k++]=A[j++];
        }
        else
            t[k++]=A[i++];
    }
    for(;i<m;)
        t[k++]=A[i++];
    for(;j<y;)
        t[k++]=A[j++];

    for(i=x;i<y;i++) A[i]=t[i];
    return t1+t2+t3;
}