【学术篇】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