【洛谷日報#150】CDQ分治學(xué)習(xí)筆記

長沙7喜 2019-04-13

展開全文

CDQ顯然是一個人的名字，陳丹琪（NOI2008金牌女選手）

這種離線分治算法被算法界稱為'cdq分治'

我們知道，一個動態(tài)的問題一定是由'更改''查詢'操作構(gòu)成的，顯然，有些“更改”會改變'查詢的結(jié)果'，而有些不能。

如果我們合理安排一個次序，把每一個查詢分成幾個部分，分別計算值，最后合起來就是原來詢問的值。

離線算法和在線算法的概念不用過多解釋.

接下來通過幾個例題將基本的CDQ分治算法解釋明白.

A. 從逆序?qū)﹂_始的二維偏序問題

下面將給出逆序?qū)Φ念}目：

例題 A1：逆序?qū)Φ亩x是對于序列a[],取第i個元素和第j個元素,滿足i

求解給定序列a中有多少對逆序?qū)Γ阈枰敵鰧?shù).

對于100%的數(shù)據(jù) a ≤ 5 * 10^5

我們都知道可以用樹狀數(shù)組和歸并排序兩種方法做，這里我們只講歸并排序(默認樹狀數(shù)組大家都會)

不斷把[l,r]細分，每次取mid=(l+r)/2 然后指針i和j分別指向區(qū)間[l,mid]和[mid+1,r]并且單調(diào)

先確定i不動，把j右移歸并，如果滿足a[i]>a[j]記錄逆序?qū)€數(shù)加mid-i+1意味著a[i],i ∈ [i,mid]和 a[j]互成逆序?qū)?，跳出把i移動

依次，直到完成所有區(qū)間，復(fù)雜度O(n log_2 n)

核心代碼Code：

void sort(int l,int r,int mid)
{
    for (int i=l;i<=mid;i++) a[i]=t[i];
    for (int i=mid+1;i<=r;i++) b[i]=t[i];
    int i=l,j=mid+1,k=l;
    while (i<=mid&&j<=r) {
        if (a[i]<=b[j]) c[k++]=a[i++];
        else c[k++]=b[j++],ans+=mid-i+1;
        //當前的b中當前的j和剩下的ai都是一對逆序?qū)?nbsp;
    }
    while (i<=mid) c[k++]=a[i++];
    while (j<=r) c[k++]=b[j++];
    for (int i=l;i<=r;i++) t[i]=c[i]; 
}
void merge_sort(int l,int r)
{
    int mid=(l+r)/2;
    if (l<mid) merge_sort(l,mid);
    if (r>mid) merge_sort(mid+1,r);
    sort(l,r,mid); 
}

然后這個問題反映什么實質(zhì)呢，顯然我們可以造出2個維度記偏序(t,i)表示時間為t，位置為i

由于我們按照順序讀入，那么默認第一維偏序是有序的，便忽略了這一維度的記錄和排序。

換句話說，在歸并的時候雖然左區(qū)間和右區(qū)間里面值不一定相等，但是左區(qū)間的所有元素都排在右區(qū)間前面

這是基于第一維偏序是有序的情況下進行的.

然而，對于有些情況，第一維偏序的記錄和第一維偏序的排序是不可省略的！

下面給出樹狀數(shù)組的模板題，請用CDQ分治（二維偏序）方法AC本題。

例題A2：維護含n個元素的原始序列a[]，有m個操作,2種不同格式：

1 x k 含義：將第x個數(shù)加上k

2 x y 含義：輸出區(qū)間[x,y]內(nèi)每個數(shù)的和

請正確輸出每一個2操作的答案，不強制在線。

對于100%的數(shù)據(jù) n,m ≤ 5 * 10^5

Solution：把原始序列讀入操作變化成插入第i個位置上加上對應(yīng)的值，參與cdq分治。

首先把查詢拆成兩個,減去x-1的前綴和和加上y的前綴和（前綴和優(yōu)化的思路）

每一個詢問記錄4個量type[類型],x,y(兩個參數(shù)),idx（若是詢問操作表示是第幾個詢問）

時間作為默認有序的第一維度，用cdq分治維護第二維度位置（歸并按照位置歸并）。

僅考慮左邊的更改對右邊查詢的影響，更改只有在左側(cè)有影響，當 tl≥ mid 且a[tl].x<a[tr].x 同時滿足的情況下，將前綴和sum+=y[加上的值]

這個時候第一維已經(jīng)默認有序了，也就是說明亂序下左邊操作的時間一定在右邊操作之前，所以更改對右邊有影響，影響是sum

同時對于位置歸并cdq，雖然打亂了這一部分時間，但是對于大塊時間的劃分是沒有影響的.

我們更新的是處理過[mid,r]這一段的答案，如果tr>r不在這個區(qū)間內(nèi)，需要舍去

一種通俗的寫法是，將tr>r的情況歸屬到更改的影響中，這樣不會對答案造成干擾.

這是核心代碼Code：

void cdq(int l,int r)
{
    if (l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid); cdq(mid+1,r);
    int tl=l,tr=mid+1,sum=0;
    fp(i,l,r) {
        if ((tl<=mid&&a[tl]<a[tr])||tr>r) {
            if (a[tl].type==1) sum+=a[tl].y;
            b[i]=a[tl++];
        } else {
            if (a[tr].type==2) ans[a[tr].idx]-=sum; //2代表-sum{l-1}
            if (a[tr].type==3) ans[a[tr].idx]+=sum;//3代表+sum{r}
            b[i]=a[tr++];
        }
    }
    fp(i,l,r) a[i]=b[i];
}

B. 從二維偏序到三維偏序

一維偏序直接sort

二維偏序第1維sort，第2維cdq分治

三維偏序第1維sort，第2維cdq分治，第3維數(shù)據(jù)結(jié)構(gòu)

下面給出三維偏序問題：

給定n個有序三元組(a,b,c)，求對于每個3元組(a,b,c)，

有多少個3元組(a_i,b_i,c_i)滿足a_i<a且b_i<b且c_i<c.

仿造上面的寫法，對第1維a排序，對第2維b歸并cdq，

對于第3維c,我們借助權(quán)值樹狀數(shù)組，每次從左邊取出三元組(a,b,c)，根據(jù)c值在樹狀數(shù)組中進行修改

從右邊的序列中取出三元組(a,b,c)時，在樹狀數(shù)組中查詢c值小于(a,b,c)的三元組的個數(shù)

注意，每次使用完樹狀數(shù)組要把樹狀數(shù)組清零

下面我們給出一個例題，即陌上花開是luogu三維偏序的模板題

例題B1：陌上花開

有n個元素，每個元素有a_i,b_i,c_i三種屬性，定義兩個元素大小比較為：

若a_i>a_j且b_i>b_j且c_i>c_j簡記為i>j，對于不同元素i，需要統(tǒng)計他比多少元素大，

就是元素i的權(quán)f(i)，問對于 d∈ [0,n-1] 有多少x∈ [1,n] 的取值f(x)=d 輸出一個數(shù)組表示 d=0,1,2,3…n-1時的答案

對于100%的數(shù)據(jù) n ≤ 10^5

Solution：

首先是可能存在一些相同的元素的，我們定義元素相同為三種屬性均相同。這樣較為難處理，第一步我們把他們合并起來了。

于是對于每種元素，記錄了四個參數(shù)a,b,c,w,id表示三種屬性、數(shù)量、他的標號。

然后對其第1維a進行排序[其實在去重這一步我們事實上已經(jīng)完成了這一操作]

然后對于第2維b進行cdq分治，在每一處分治的時候樹狀數(shù)組維護插入和查詢，每次需要插入的時候在值域樹狀數(shù)組維護數(shù)量的前綴和，

插入的時候，對于z處加上數(shù)量w,update(z,w)，查詢的時候，在ans[id]+=query(z)。

然后就可以統(tǒng)計出對于每一朵花有多少元素比他大了，記錄在ans[id]中，id ∈ [1,n]

輸出的時候還需要統(tǒng)計，別忘了加上自己的那份w和減去自己的1！

核心代碼Code:

/去重操作
    sort(t+1,t+1+n,cmp1);
    int i=1,j; tot=0;
    while (i<=n){
        j=i+1;
        while (j<=n&&same(t[i],t[j])) j++;
        j--;
        a[++tot]=t[i]; a[tot].w=(j-i+1); a[tot].id=tot;
        i=j+1;
    }
void cdq(int l,int r) //cdq分治
{
    if (l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    dfn++; //便于去重
    int t1=l,t2=mid+1;
    for (int i=l;i<=r;i++) {
        if ((t1<=mid&&a[t1].y<=a[t2].y)||t2>r) {
            update(a[t1].z,a[t1].w);
            b[i]=a[t1++];
        } else {
            ans[a[t2].id]+=query(a[t2].z);
            b[i]=a[t2++];
        }
    }
    for (int i=l;i<=r;i++) a[i]=b[i];
}

C. 從三維偏序到三維偏序的應(yīng)用

這一專題我們安排了兩道例題，請按照三維偏序的思想和方法，嘗試解決。

練習(xí)C1：[CQOI2011]動態(tài)逆序?qū)?/p>

練習(xí)C2：[Violet]天使玩偶/SJY擺棋子

下面對于每一個例題講解：

例題C1：逆序?qū)Φ亩x：對于序列a[],取第i個元素和第j個元素,滿足i

給出一個[1,n]的排列，按照順序依次刪除m個數(shù)，詢問當前逆序?qū)?shù)量.不強制在線。

對于100%的數(shù)據(jù) ：N≤ 10^5,M≤ 5* 10^4

Solution:可以把每次的答案分成兩個部分：原先存在的逆序?qū)?加入這個數(shù)新產(chǎn)生的逆序?qū)Γ?/p>

那么每次只要算出當前新產(chǎn)生的逆序?qū)Γ詈笏阋槐榍熬Y和即可。

考慮逆序?qū)Ξa(chǎn)生方式：

位置靠前且值比它大的。
位置靠后且比它小的。

這個問題在于有插入操作，和刪除操作，比較難過

對于逆序?qū)Φ漠a(chǎn)生是插入比他前的滿足1 or 2兩個條件的元素

對于逆序?qū)Φ膭h除是刪除時間比他后面的，滿足1 or 2兩個條件的元素。

顯然對于把時間作為第1維進行排序是不合適的(時間在前和后有不同的影響)，所以我們考慮把操作的位置作為第1維，進行排序

對于時間這1維度作為第2維度CDQ分治，

設(shè)當前刪除了第i個元素，那么在[1,i]中比它大的都要減去，在[i+1,N]中比他小的都要減去。

正序循環(huán)的時候默認先加入樹狀數(shù)組的元素的位置都是在詢問元素的前面的，所以要減去的是比詢問元素大的那一個部分 [i+1,n]

倒序循環(huán)的時候默認先加入樹狀數(shù)組的元素的位置都是在詢問元素后面的，所以要減去的是比詢問元素小的那個部分[1,n-1]

同樣的考慮影響還是處于左邊時間修改對處于右邊時間的查詢造成的影響，注意同步清空樹狀數(shù)組.

例題C2：定義兩點距離為麥哈頓距離 Dist(A,B) = |A_x - B_x|+|A_y-B_y|

給出初始n個點的坐標 (x_i,y_i) 有m個操作，

1 x y : 表示在(x,y)處新增1個點

2 x y : 表示詢問所以存在的點到點(x,y)最小距離

對于100%的數(shù)據(jù) n,m ≤ 3 * 10^5 , x_i,y_i ≤ 10^6

Solution：

如果點都在詢問點的左下方就好了…（這樣絕對值就直接消掉了）

However，人家有4個方向，怎么辦，考慮到對稱我們可以把所有點都做一次變換，稱為對稱

怎么個對稱法呢，關(guān)于x軸對稱，關(guān)于y軸對稱，關(guān)于原點對稱，對稱的意思是所有點的坐標發(fā)生變換，

以原點對稱為例，原來A在B的左下方，對稱后A就在B的右上方了，那么類似于按原點B對稱的意思。

按照x軸對稱，按照y軸對稱同理。

接下來我們只討論點在點左下方的情況（變換以后跑4遍不就好了?。?/p>

計算lx，ly表示x，y坐標最大取值+1

把Dist絕對值打開得 Dist(A,B) = |A_x - B_x|+|A_y-B_y| =A_x+A_y-(B_x+B_y)

對于給定的A點，A_x+A_y一定，當 Dist(A,B)取到最小值的時候B_x+B_y最大

所以用樹狀數(shù)組維護前綴最大值就行。

這里時間t是默認有序的作為第1維，然后cdq分治第2維x，然后用樹狀數(shù)組維護一個y,前綴最大值

當分治求答案的時候左邊時間早于右邊，左邊影響右邊，第2維x經(jīng)過歸并左邊小于右邊，所以為了保證在左下方還需y左邊小于右邊

所以求的時候求y的這個點前綴最大值即可.（注意如果沒有請不要更新為0）

D.四維偏序(CDQ套CDQ)

下面給出四維偏序的模板題：

例題D1：現(xiàn)在有n個三元組(a_i,b_i,c_i) 求有多少組三元組對(i,j)滿足 i<j, a_i<a_j , b_i<b_j , c_i<c_j

你的程序必須輸出三元組對總對數(shù)。數(shù)據(jù)保證a,b,c三個數(shù)組都是[1,n]排列。

對于100%的數(shù)據(jù) n ≤ 5 * 10^4

(數(shù)據(jù)來自ljc20020730)

solution：我們類比二維偏序、三維偏序的方法考慮四維偏序的求解方法

首先把第1維排序，顯然是位置（這里沒記，原數(shù)組就是按照順序位置排布的）

然后對第2維進行CDQ分治，但是剩下還有2維怎么辦。

我們不妨再對第3維進行CDQ分治，然后第4維使用數(shù)據(jù)結(jié)構(gòu)統(tǒng)計。

顯然當我們歸并第2維以后數(shù)組變成了按照第2維度排序的有序數(shù)組但是第1維時間是雜亂無章的。

然而我們只關(guān)心第1維是在左邊還是右邊，并不關(guān)心具體值，于是我們可以用Left和Right來標記a值（part）

既然b已經(jīng)有序在CDQ套的cdq下面（不妨把正式求解的分治算法稱之為CDQ，CDQ中套如的子分治算法叫做cdq）

把原來CDQ中第2、3、4維換成之前做過三維偏序的1、2、3維就行了（同時注意更新時判斷，對于CDQ是不是完成了左邊更改對右邊查詢的影響）

cdq完成的目的是：在CDQ后前面部分對后面部分的影響。

step 1：對第一維進行排序。

step 2：對第1維重新標號（left或right），然后對第2維分治，遞歸解決子問題，按照第2維的順序合并。此時只是單純的合并，并不進行統(tǒng)計。

step 3：把合并后的序列復(fù)制一份，在復(fù)制的那一份中進行cdq分治。（這時第2維默認有序）即對第3維分治，遞歸解決子問題，按照第3維的順序合并。合并過程中用樹狀數(shù)組維護第4維的信息。

void cdq(int l,int r) //對于2,3,4維度重新cdq分治 
{

    if (l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid); cdq(mid+1,r);
    int i=l,j=mid+1,k=l;
    while (i<=mid&&j<=r) {
        if (t1[i].b<t1[j].b) { //按照第3維歸并 
            if (t1[i].part==Left) update(t1[i].c); //更新的前提條件第1維在左邊，影響第1維的右邊 
            t2[k++]=t1[i++];
        } else {
            if (t1[j].part==Right) ans+=query(t1[j].c); //答案累加的前提條件是第1維在右邊受到第1維左邊影響 
            t2[k++]=t1[j++];
        }
    }
    while (i<=mid) t2[k++]=t1[i++];
    while (j<=r) {
        if (t1[j].part==Right) ans+=query(t1[j].c);
        t2[k++]=t1[j++];
    }
    fp(i,l,r) {
        if (t2[i].part==Left) clear(t2[i].c);//清空樹狀數(shù)組 
        t1[i]=t2[i]; 
    }
}
void CDQ(int l,int r) //注意此時已經(jīng)默認第1維有序我們不必記錄 
{

    if (l==r) return;
    int mid=(l+r)>>1;
    CDQ(l,mid); CDQ(mid+1,r);
    int i=l,j=mid+1,k=l;
    while (i<=mid&&j<=r) {
        if (a[i].a<a[j].a) {
            a[i].part=Left; //對于第2維度a歸并，并記錄第1維是左邊(left)還是右邊(right) 
            t1[k++]=a[i++];
        } else {
            a[j].part=Right;
            t1[k++]=a[j++];
        }
    }
    while (i<=mid) a[i].part=Left,t1[k++]=a[i++];
    while (j<=r)   a[j].part=Right,t1[k++]=a[j++];
    fp(i,l,r) a[i]=t1[i]; //t1就是復(fù)制過去的數(shù)組 
    cdq(l,r);
}