admin 管理员组

文章数量: 1086019

CDQ分治——学习笔记

前言
因为中国集训队的大佬们总会发明一些新的东西，所以中国的计算机竞赛水平才会一直处于国际前沿，而cdq分治也是某一年的集训队成员发明的算法。

什么是CDQ分治
cdq分治是一种分治（这不是废话嘛），和一般的分治一样，它先考虑前半部分，再考虑后半部分，再考虑前半部分对后半部分的影响，而cdq分治的精髓就在于处理前半部分对后半部分的影响。

例题：陌上花开
经典的三维偏序问题，我们可以用cdq来解决。
我们先不考虑有重复的问题。
我们先通过依次排序使s变得有序，去掉一维，再通过分治去掉一维。具体是每次将当前区间分为左边和右边，左边编号为1，右边编号为2，再按c排一边序，只考虑编号为1的花对编号为2的花的影响，每次遇到编号为1的话将他的m加入平衡树，遇到编号为2的花查询当前平衡树中m小于等于自身的，即可顺利解决这题了。
代码：

#include <bits/stdc++.h>
using namespace std;const int maxn=1e5+1000;
const int inf=1e7;
struct stu
{int x,y,z,num;friend bool operator == (stu t1,stu t2){if(t1.x==t2.x&&t1.y==t2.y&&t1.z==t2.z) return 1;return 0;}
}d[maxn];
struct lily
{int y,z,type,id,num;
}a[maxn];
int ans[maxn],level[maxn],cnt,n,k1;bool cmp(lily t1,lily t2)
{if(t1.y!=t2.y) return t1.y<t2.y;else if(t1.z!=t2.z) return t1.z<t2.z;else return t1.type<t2.type;
}bool cmp1(stu t1,stu t2)
{if(t1.x!=t2.x) return t1.x<t2.x;else if(t1.y!=t2.y) return t1.y<t2.y;else return t1.z<t2.z;
}struct Splay_tree
{int root,val[maxn],c[maxn][2],fa[maxn],size[maxn],num[maxn];void pushup(int x){size[x]=size[c[x][0]]+size[c[x][1]]+num[x];}void rotate(int x){int y=fa[x],z=fa[y],k=c[y][1]==x,w=c[x][!k];c[z][c[z][1]==y]=x,c[x][!k]=y,c[y][k]=w;if(w) fa[w]=y;fa[y]=x;fa[x]=z;pushup(y);pushup(x);}void splay(int x,int tar){while(fa[x]!=tar){int y=fa[x],z=fa[y];if(z!=tar) rotate((c[y][1]==x)^(c[z][1]==y)?x:y);rotate(x);}if(tar==0) root=x;}void insert(int val1,int num1){int now=root,f=0;while(now&&val[now]!=val1) { f=now;now=c[now][val1>val[now]]; }if(now==0){now=++cnt;val[now]=val1;size[now]=num1;num[now]=num1;c[now][0]=c[now][1]=0;fa[now]=f;if(f==0) root=now;else { c[f][val1>val[f]]=now;splay(now,0); }}else{num[now]+=num1;pushup(now);splay(now,0);}}void find(int val1){int now=root;while(c[now][val1>val[now]]&&val[now]!=val1) now=c[now][val1>val[now]];splay(now,0);}int query(int val1){find(val1);return size[c[root][0]]+num[root]*(val[root]<=val1);}void init(){root=0;cnt=0;c[0][0]=c[0][1]=val[0]=num[0]=size[0]=fa[0]=0;}}T;void cdq(int l,int r)
{if(l==r) return;T.init();
//    T.root=0;cnt=0;int mid=(l+r)>>1;for(int i=l;i<=mid;i++) { a[i].y=d[i].y;a[i].z=d[i].z;a[i].type=0;a[i].num=d[i].num;a[i].id=i; }for(int i=mid+1;i<=r;i++) { a[i].y=d[i].y;a[i].z=d[i].z;a[i].type=1;a[i].num=d[i].num;a[i].id=i; }sort(a+l,a+r+1,cmp);
//    for(int i=l;i<=r;i++) cout<<a[i].id<<' '; cout<<endl;for(int i=l;i<=r;i++){if(!a[i].type)T.insert(a[i].z,a[i].num);else{int kk=T.query(a[i].z);level[a[i].id]+=kk;}}cdq(l,mid);cdq(mid+1,r);
}int main()
{scanf("%d%d",&n,&k1);for(int i=1;i<=n;i++) { scanf("%d%d%d",&d[i].x,&d[i].y,&d[i].z);d[i].num=1; }sort(d+1,d+1+n,cmp1);d[0].x=d[0].y=d[0].z=-inf;int n2=0;for(int i=1;i<=n;i++){if(d[i]==d[n2]) d[n2].num++;else d[++n2]=d[i];}for(int i=1;i<=n2;i++) level[i]=d[i].num-1;
//    for(int i=1;i<=n2;i++) printf("%d %d %d %d\n",d[i].x,d[i].y,d[i].z,d[i].num);cdq(1,n2);
//    for(int i=1;i<=n2;i++) printf("%d\n",level[i]);for(int i=1;i<=n2;i++) ans[level[i]]+=d[i].num;for(int i=0;i<=n-1;i++) printf("%d\n",ans[i]);return 0;
}


本文标签： CDQ分治学习笔记

版权声明：本文标题：CDQ分治——学习笔记 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1686560602a10400.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。