【学术篇】bzoj3262 陌上花开. cdq分治入门

花儿们已经很累了——
无论是花形、颜色、还是气味，
都不是为了给人们摆出来欣赏的，
更不是为了当做出题的素材的，
她们并不想自己这些属性被没有生命的数字量化，
并不想和其它的花攀比，
并无意分出个三六九等，
它们只想静静地开放，
完成自己这一生的使命，
而你(出题人)考虑过这些吗？
不，你只关心你自己！

题目的传送门会有的，先不要着急...

首先来看一道大水题.

给定\(n\)个元组\((x)\), 询问对于每个元组\(i\), 有多少个元组\(j\)满足\(x_i<x_j\).(一维偏序)

那不就是sort一遍就水过去了么←_←
有追求一点?
那就写个权值树状数组吧...

那我们看一道升级版.

给定\(n\)个元组\((x,y)\), 询问对于每个元组\(i\), 有多少个元组\(j\)满足\(x_i<x_j\)且\(y_i<y_j\)(二维偏序)

Emmmm.... 以\(x\)为关键字排序, 以\(y\)为关键字建树状数组好像可做.
那\(y\)权值大一点呢? 我们可以离散啊XD
好像也不难, 这样就水过去了.

那再升升级?

给定\(n\)个元组\((x,y,z)\), 询问对于每个元组\(i\), 有多少个元组\(j\)满足\(x_i<x_j,y_i<y_j\)且\(z_i<z_j\)
这就是著名的三维偏序问题. 怎么样, 不是很好做了吧?

为什么会有这样的题啊喂!!! 可是确实有这样的题.. (你看我说会有传送门嘛←_←)

冷静分析, 仔细思考, 我们可以:

排序+............树套树???

说得好像你会树套树一样...

这玩意看上去就巨tm难写啊, 有没有什么好做一点的方法啊...

cdq大爷说, 我们可以用一种特殊的分治方式水过去. orz

啥啥啥啥啥??? 分治???

分治我见过啊, 好像是个挺常见的算法...

常见的分治算法:

• 归并排序
• 快速排序
• 快速凸包算法
• 线段树

一般的分治都有着如下流程:

SOLVE(L,R)      //好像是首打油诗
-> MID=(L+R)>>1 //找到区间的中点
-> SOLVE(L,MID) //递归处理左半边
-> SOLVE(MID+1) //递归处理右半边
-> MERGE(L,R)   //合并区间的操作

而且一般情况下能拥有一个不错的复杂度:

T(n) = 2T(n/)+O(kn), T(n) = O(knlogn)
T(n) = 2T(n/)+O(knlogn), T(n) = O(knlog^2n)
T(n) = 2T(n/)+O(k), T(n) = O(kn)

分治中主要需要考虑的就是合并区间时要进行什么操作.

回到我们的三维偏序问题. 我们考虑分治解决问题.
我们对\(x\)这一维进行分治, 这样剩下的就是我们会的二维偏序了.
然后来思考合并区间时候的操作.
那么假设我们已经处理好了\([L,mid]\)和\((mid,R]\)这两个区间了.
但是这是不够滴, 我们还要考虑到, \([L,mid]\)中的点对于\((mid,R]\)来说, 也会对答案有贡献.

我们对\([L,R]\)按\(y\)排序, 对\(z\)建树状数组(该离散就离散..)
然后扫一遍, 如果\(x\in[L,mid]\), 单点加, 否则就查询.
复杂度应该是\(O(nlog^2n)\)的.

woc细节调到心态爆炸...估计还是自己码力太弱了...把注释写的详细一点吧..

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e5+10;
struct flower{
    int x,y,z;
    int cnt,ans; //个数(会重不是),答案
}a[N];
inline bool operator<(const flower& a,const flower &b){
    if(a.y==b.y){
        if(a.z==b.z) return a.x<b.x;
        return a.z<b.z;
    } return a.y<b.y;
} //yzx关键字排序(主要)
inline bool operator==(const flower &a,const flower &b){
    return a.x==b.x&&a.y==b.y&&a.z==b.z;
} 
inline bool cmp(const flower &a,const flower &b){
    if(a.x==b.x){
        if(a.y==b.y) return a.z<b.z;
        return a.y<b.y;
    } return a.x<b.x;
} //xyz关键字排序(去重)
int c[N*2],ans[N*2],k;
//闭着眼打的树状数组
inline void add(int x,int i){for(;x<=k;x+=x&-x) c[x]+=i;}
inline int query(int x,int s=0){for(;x;x-=x&-x) s+=c[x]; return s;}
//快读
inline int gn(int a=0,char c=0){
    for(;c<'0'||c>'9';c=getchar());
    for(;c>47&&c<58;c=getchar())a=a*10+c-48; return a;
}
//cdq分治!!
void solve(int l,int r){
    if(l==r) {
        a[l].ans+=a[l].cnt-1; //有重复
        return;
    }
    int mid=(l+r)>>1;
    //分治
    solve(l,mid);
    solve(mid+1,r);
    
    //分别排序
    sort(a+l,a+mid+1);
    sort(a+mid+1,a+r+1);
    int j=l;
    //对于后半段的每个点
    for(int i=mid+1;i<=r;++i){
        //如果前半段的y比较小了就可以查询到了
        while(j<=mid&&a[j].y<=a[i].y)
            add(a[j].z,a[j].cnt),++j;
        a[i].ans+=query(a[i].z);
    }
    //因为还要递归下去继续处理所以要消除影响..
    for(int i=l;i<j;++i) add(a[i].z,-a[i].cnt);
}
int main(){
    int n=gn(),m=0; k=gn();
    for(int i=1;i<=n;++i)
        a[i].x=gn(),a[i].y=gn(),a[i].z=gn();
    sort(a+1, a+n+1,cmp);
    for(int i=1;i<=n;++i)
        if(i>1&&a[i]==a[i-1]) ++a[m].cnt;
        else a[++m]=a[i],a[m].cnt=1;
    solve(1,m);
    //统计答案即可
    for(int i=1;i<=n;++i) ans[a[i].ans]+=a[i].cnt;
    for(int i=0;i<n;++i) printf("%d\n",ans[i]);
}

就这样吧...
一定记得消除影响, 注意变量名和变量的作用域, 注意枚举的先后顺序.
别的也就没啥了OvO