cdq分治和整體二分

cdq分治

ps：先膜拜陳丹琦大神，Orz%%%。

作用

很多動态的題目都需要進階資料結構，代碼量很大，這時候cdq分治就展現了它的強大。隻要不強制線上，cdq分治就可以将動态轉化為靜态處理，而且代碼複雜度低，易調試，是很不錯的方法！

實作

cdq分治是将整個操作序列進行分治，分治步驟如下：

1.将序列拆分為兩半，[L,mid]和[mid+1,R]。

2.考慮[L,mid]所有操作對[mid+1,R]的影響，并計算。

3.由于[L,mid]和[mid+1,R]是和[L,R]相同的子問題，于是遞歸處理。

在cdq分治之前，通常要讓操作序列滿足一定的順序（比如按照時間排序，使[L,mid]所有操作在[mid+1,R]之前）。而在cdq分治時，也可能需要讓操作序列再次滿足一定的順序。

cdq分治典型的應用是三維偏序，然而我并不知道三維偏序準确定義是什麼，考慮這樣一個題目：給出n個三維點(x,y,z)，(xi,yi,zi)>=(xj,yj,zj)定義為xi>=xj且yi>=yj且zi>=zj。求每個點>=多少個其他點。

如果點是二維的，那麼就可以先按照x第一關鍵字，y第二關鍵字排序，然後利用樹狀數組就可以計算每個點>=多少個其他點。然而點是三維的，不過我們可以用同樣的想法。先按照x第一關鍵字，y第二關鍵字，z第三關鍵字排序。x不用管，y和z用資料結構來維護，但這樣代碼量就比較大了。

如果我們把每個點看做操作，排序過後一個點會影響前面的點嗎？不會，隻會影響後面的點，是以我們想到了cdq分治。将操作序列分為[L,mid]和[mid+1,R]，然後按照y第一關鍵字，區間（左小右大）第二關鍵字排序，這樣就可以不用管y了，而z和二維問題一樣，用樹狀數組即可。最後再處理一下完全相同的節點就可以得到答案。

模闆

以HDU5618為例。

這就是上面說的問題，不多解釋了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=,maxm=;

int te,n,MAX,ans[maxn+];
struct Point3D
{
    int x,y,z,id;
    bool operator == (const Point3D &a) {return x==a.x&&y==a.y&&z==a.z;}
};
Point3D p[maxn+],tem[maxn+];
struct FenwickTree
{
    int s[maxm+];
    int lowbit(int x) {return x&(-x);}
    void Insert(int x,int tem) {while (x<=MAX) s[x]+=tem,x+=lowbit(x);}
    int Ask(int L,int R)
    {
        int x,sum=;L--;
        x=L;while (x) sum-=s[x],x-=lowbit(x);
        x=R;while (x) sum+=s[x],x-=lowbit(x);
        return sum;
    }
};
FenwickTree tr;

bool Eoln(char ch) {return ch==||ch==||ch==EOF;}
int readi(int &x)
{
    int tot=,f=;char ch=getchar(),lst='+';
    while ('9'<ch||ch<'0') {if (ch==EOF) return EOF;lst=ch;ch=getchar();}
    if (lst=='-') f=-f;
    while ('0'<=ch&&ch<='9') tot=tot*+ch-,ch=getchar();
    x=tot*f;
    return Eoln(ch);
}
bool mycmp1(const Point3D &a,const Point3D &b)
{
    if (a.y<b.y) return true;
    if (a.y==b.y&&a.id<b.id) return true;
    return false;
}
void cdqBinary(int L,int R)
{
    if (L==R) return;int mid=L+(R-L>>);
    for (int i=L;i<=mid;i++) tem[i]=p[i],tem[i].id=;
    for (int i=mid+;i<=R;i++) tem[i]=p[i];
    sort(tem+L,tem++R,mycmp1);
    for (int i=L;i<=R;i++)
        if (!tem[i].id) tr.Insert(tem[i].z,); else
        ans[tem[i].id]+=tr.Ask(,tem[i].z);
    for (int i=L;i<=R;i++) if (!tem[i].id) tr.Insert(tem[i].z,-);
    cdqBinary(L,mid);cdqBinary(mid+,R);
}
bool mycmp2(const Point3D &a,const Point3D &b)
{
    if (a.x<b.x) return true;
    if (a.x==b.x&&a.y<b.y) return true;
    if (a.x==b.x&&a.y==b.y&&a.z<b.z) return true;
    if (a.x==b.x&&a.y==b.y&&a.z==b.z&&a.id<b.id) return true;
    return false;
}
int main()
{
    freopen("cdqBinary.in","r",stdin);
    freopen("cdqBinary.out","w",stdout);
    readi(te);
    while (te--)
    {
        readi(n);MAX=;
        for (int i=;i<=n;i++)
        {
            readi(p[i].x);readi(p[i].y);readi(p[i].z);
            p[i].id=i;MAX=max(MAX,p[i].z);
        }
        sort(p+,p++n,mycmp2);
        memset(ans,,sizeof(ans));
        for (int i=n-,tot=;i>=;i--)
        {
            if (p[i]==p[i+]) tot++; else tot=;
            ans[p[i].id]=tot;
            //cdq分治處理時隻往前統計相同三維點，是以要再向後統計一下相同三維點
        }
        cdqBinary(,n);
        for (int i=;i<=n;i++) printf("%d\n",ans[i]);
    }
    return ;
}
           

整體二分

ps：先膜拜發明整體二分的我不知道是誰的人，Orz%%%

作用

和cdq分治一樣，也是将動态轉化為靜态。

實作

整體二分也是對操作序列進行處理。但和cdq分治稍微有些不同，因為整體二分需要二分處理答案範圍[L,R]：

1.如果L==R，說明答案已經确定了，将目前序列中所有詢問的答案定為L(R)。

2.二分答案mid。

3.考慮序列中靠前的操作對靠後的詢問的影響。

4.對序列進行分塊，序列中<=mid的操作放到左邊，>mid的放到右邊。

5.遞歸處理相同子問題[L,mid]和[mid+1,R]。

整體二分經典應用是區間第K大。二分答案mid之後，按順序周遊序列，如果是插入删除修改等操作，且數值<=mid，說明這些操作和[mid+1,R]無關，是以放到左邊，如果數值>mid，說明這些操作和[L,mid]無關，是以放到右邊，同時累加>mid的個數（比如使用樹狀數組）。如果是查詢，先詢問查詢區間中>mid的個數，記為now，如果查詢數值＜now，說明該查詢的答案<=mid，和[mid+1,R]無關，是以放到左邊，但是查詢數值要減去now（因為放到左邊後[mid+1,R]的就沒了），如果查詢數值>=now，說明該查詢的答案>mid，和[L,mid]無關，是以放到右邊。

模闆

以BZOJ3110為例。

這就是上面說的問題，不多解釋了。下面的代碼用到了樹狀數組區間增減，比線段樹友善很多。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=,maxm=,MAXINT=((<<)-)*+;

int n,m,ans[maxm+];
struct Work
{
    int id,td,L,R,k;
};
Work wk[maxm+],tem[][maxm+];
struct FenwickTree
{
    LL s[][maxn+];
    void clear() {memset(s,,sizeof(s));}
    int lowbit(int x) {return x&(-x);}
    void Insert(int L,int R,LL tem)
    {
        int x;R++;
        x=L;while (x<=n) s[][x]+=tem,s[][x]+=tem*(L-),x+=lowbit(x);
        x=R;while (x<=n) s[][x]-=tem,s[][x]-=tem*(R-),x+=lowbit(x);
    }
    LL Ask(int L,int R)
    {
        int x;LL sum=;L--;
        x=L;while (x) sum-=s[][x]*L-s[][x],x-=lowbit(x);
        x=R;while (x) sum+=s[][x]*R-s[][x],x-=lowbit(x);
        return sum;
    }
};
FenwickTree tr;

void AllBinary(int L,int R,int l,int r)
{
    if (l>r) return;
    if (L==R)
    {
        for (int i=l;i<=r;i++) if (wk[i].td==) ans[wk[i].id]=L;
        return;
    }
    int num[],mid=L+(R-L>>);num[]=num[]=;
    for (int i=l;i<=r;i++)
        if (wk[i].td==)
        {
            if (wk[i].k<=mid) tem[][++num[]]=wk[i]; else
            tem[][++num[]]=wk[i],tr.Insert(wk[i].L,wk[i].R,);
        } else
        {
            LL now=tr.Ask(wk[i].L,wk[i].R);
            if (now<wk[i].k) wk[i].k-=now,tem[][++num[]]=wk[i]; else
            tem[][++num[]]=wk[i];
        }
    for (int i=l;i<=r;i++) if (wk[i].td==&&wk[i].k>mid) tr.Insert(wk[i].L,wk[i].R,-);
    for (int i=;i<=num[];i++) wk[l+i-]=tem[][i];
    for (int i=;i<=num[];i++) wk[l+num[]+i-]=tem[][i];
    AllBinary(L,mid,l,l+num[]-);AllBinary(mid+,R,l+num[],r);
}
int main()
{
    freopen("AllBinary.in","r",stdin);
    freopen("AllBinary.out","w",stdout);
    scanf("%d%d",&n,&m);int L=MAXINT,R=-MAXINT;
    for (int i=;i<=m;i++)
    {
        scanf("%d%d%d%d",&wk[i].td,&wk[i].L,&wk[i].R,&wk[i].k);wk[i].id=i;
        if (wk[i].td==) L=min(L,wk[i].k),R=max(R,wk[i].k);
    }
    memset(ans,,sizeof(ans));
    AllBinary(L,R,,m);
    for (int i=;i<=m;i++) if (ans[i]!=ans[]) printf("%d\n",ans[i]);
    return ;
}
           

效率

假設cdq分治和整體二分中的操作複雜度為T，則cdq分治和整體二分的效率均為 O(T∗log2(n)) 。非常不錯。

然而我這個蒟蒻要熟練掌握cdq分治和整體二分看來還需要很久……