三维偏序整体二分？

· · 闲话

基于整体二分的CDQ分治实现？

众所周知的是三维偏序可以使用整体二分解决，但是今天我研究了一下，发现这个整体二分并不是一般意义下的整体二分，而是CDQ分治的一种类似整体二分的实现。

一般而言，整体二分指的是平行二分答案，这里以区间第 k 小举例。

你的 solve(ql,qr,l,r) 指的是 ql,qr 的询问的答案属于 l,r，并且二分答案，使用 BIT 维护。

但是在三维偏序（CDQ分治）中，你的整体二分二分的是一个阈值，小于的对大于的贡献，你的操作仅仅是将操作分组，而不是二分答案，所以三维偏序根本没有整体二分的写法，只是长得像整体二分的CDQ分治。

void solve(int ql,int qr,int l,int r){
    if(ql>qr)return;
    int mid=l+r>>1,cnt1=0,cnt2=0;
    for(int i=ql;i<=qr;i++){
        if(q[i].tp==1){
            if(q[i].y<=mid){
                q1[++cnt1]=q[i];
                add(q[i].z,1);
            }
            else q2[++cnt2]=q[i];
        }
        else{
            if(q[i].y<mid)q1[++cnt1]=q[i];
            else{
                q2[++cnt2]=q[i];
                ans[q[i].id]+=ask(q[i].z);
            }
        }
    }
    for(int i=1;i<=cnt1;i++)
        if(q1[i].tp==1)
            add(q1[i].z,-1);
    for(int i=1;i<=cnt1;i++)q[ql+i-1]=q1[i];
    for(int i=1;i<=cnt2;i++)q[ql+cnt1+i-1]=q2[i];
    if(l==r)return;
    solve(ql,ql+cnt1-1,l,mid);
    solve(ql+cnt1,qr,mid+1,r);
}//第一关键字x，第二关键字tp，tp=1插入，tp=2查询

我们根本没有在二分答案！而是二分一个阈值来计算答案，这一点和CDQ本质相同。