CDQ分治

CDQ分治

科技前沿 • 2025-02-25 08:03 • 阅读 54

大家好，我是讯享网，很高兴认识大家。

一、大致思路

我们拿逆序对这个二维偏序问题开始说。对于逆序对，我们可以分治排序，也可以先排序再用一个树状数组求出来。那么如果我们能用一种手段把三维偏序问题降维，就可以很容易地解决了。那么怎么降维？答案是，用分治！
于是我们的重点就转化称如何用分治降维。
值得一提的是，CDQ分治大致有两个基本形式：多维偏序降维 和 动态修改转换成静态修改统一查询。只要问题能转化成这两个形式，那就可以考虑用CDQ分治了。

二、算法简介

CDQ分治适用于满足这两个条件的数据结构题：

修改之间对于答案的贡献是独立的，修改操作之间互不影响修改效果
题目可离线

我们将整个操作序列[l,r]等分成前一半操作序列（后文简称前序列）[l,mid]和后一半操作序列（简称后序列）[mid+1,r]，可以发现这样两个性质：

后序列中修改操作不会对前序列中操作序列产生影响
后序列中每一个询问x仅受两部分影响：[l,mid]中的修改操作，[mid+1,r]中在x之前的修改。

讯享网

关于第二条性质，实际上并不是所有问题都满足该性质。但是，由于思维方式的一致，我们对于”后序列对前序列也有影响“问题的求解并不赘述，基本流程和实现没有太大差别，注意灵活变通。

三、详解分治过程

四、例题

P3810 【模板】三维偏序（陌上花开）
来源
模板题
自认为我的码风已经变得温和很多了

#include<bits/stdc++.h> using namespace std; #define il inline #define re register #define lowbit(x) (-(x)&(x)) il int read(){ 
    int s=0,w=1;char c=getchar(); while(c<'0'||c>'9'){ 
    if(c=='-') w=-1;c=getchar();} while(c>='0'&&c<='9'){ 
    s=(s<<1)+(s<<3)+c-'0';c=getchar();} return s*w; } const int N=2e5+10; int n,K,f[N],ans[N],cnt; struct node{ 
    int x,y,z,id,sz;}a[N],q[N]; il bool operator==(const node &c,const node &d){ 
    return c.x==d.x && c.y==d.y && c.z==d.z; } namespace FW{ 
   //Fenwick-Tree int tr[N]; il void upd(int x,int val){ 
    while(x<=K) tr[x]+=val,x+=lowbit(x); } il int getsum(int x){ 
    int res=0; while(x>0) res+=tr[x],x-=lowbit(x); return res; } } using namespace FW; il bool cmp(node c,node d){ 
    if(c.x!=d.x) return c.x<d.x; if(c.y!=d.y) return c.y<d.y; return c.z<d.z; } il void CDQ(int l,int r){ 
    if(l==r) return; int mid=l+r>>1; CDQ(l,mid),CDQ(mid+1,r); int p1=l,p2=mid+1,p=l; while(p1<=mid && p2<=r){ 
    if(a[p1].y<=a[p2].y) q[p]=a[p1],upd(a[p1].z,a[p1].sz),++p1,++p; else q[p]=a[p2],f[a[p2].id]+=getsum(a[p2].z),++p2,++p; } while(p1<=mid) q[p]=a[p1],upd(a[p1].z,a[p1].sz),++p1,++p; while(p2<=r) q[p]=a[p2],f[a[p2].id]+=getsum(a[p2].z),++p2,++p; for(re int i=l;i<=mid;i++) upd(a[i].z,-a[i].sz),a[i]=q[i]; for(re int i=mid+1;i<=r;i++) a[i]=q[i]; } int main() { 
    n=read(),K=read(); for(re int i=1;i<=n;i++) q[i]=(node){ 
   read(),read(),read(),i,0}; sort(q+1,q+1+n,cmp); for(re int i=1;i<=n;i++){ 
    if(q[i]==q[i-1]) a[cnt].sz++; else a[++cnt]=q[i],a[cnt].id=cnt,a[cnt].sz=1; } CDQ(1,cnt); for(re int i=1;i<=cnt;i++) f[a[i].id]+=a[i].sz-1,ans[f[a[i].id]]+=a[i].sz; for(re int i=0;i<n;i++) printf("%d\n",ans[i]); return 0; }

讯享网

end

CDQ分治

CDQ分治

一、大致思路

二、算法简介

三、详解分治过程

四、例题

相关推荐