CDQ分治之三维偏序问题

前言

上篇博文介绍了二维偏序问题的解决方法。
现在将参量提升到3个，该咋办呢？
树套树？？？
理解难度->INF 代码难度->INF 烦躁程度->INF
那就上新工具 CDQ分治。
CDQ分治这名字一点也不表面，其实是以神犇陈丹琦名字命名的。

适用条件

首先CDQ必须满足的条件：
1.修改操作对询问的贡献独立，修改操作之间互不影响效果。
2.题目允许使用离线算法。

实现原理

首先我们对询问和修改队列二分，我们就能发现：
1.后半队列对前半队列的操作无影响。
2.后半队列中的询问仅受前半队列操作和它之前的后半队列的操作。
首先对于前半队列，由1可知它没有任何限制，那我们就递归之。
对于后半队列，明显后半队列的修改操作不受前面操作的影响。
那么对于后半队列的询问操作，由2可知该问题完全被转化为了“给定一些操作后进行询问”的静态离线问题，这样极大地降低了我们的编程难度。我们设这个操作的复杂度为O(f(n))。
而我们所搜的深度为O(logn)，所以时间复杂度为O(f(n)logn)。
需要注意的是，我们虽然降低了代码难度，但代价是时间复杂度的提高。
当然不排除高级数据结构的常数问题

如何解决三维偏序问题

基本思路是 1维排序 2维CDQ 3维数据结构（当然是比较简单的了）
首先我们把第一维的X排序。
然后二分区间。
当前区间为 l-r 按照 y 升序的原则进行排序。
当 a[i].x<=mid时，为左区间的数，把z扔进树状数组中
当 a[i].x>mid，为右区间的数，查询答案。
分治下去，即可得到全部答案。
简单说：我们每次添加区间前一半的点，后一半进行查询（原因不好用语言表达，大致意思为一个点到区间前端的这段区间可以由若干个CDQ区间的整个前半组成）

注意事项

1.离散化.
2.如果一系列点的三个参量完全相同，由于我们顺着添加，树状数组查出的答案只有最后一个正确，倒数第二个差1，倒数第三个差2……别忘了添加上。
3.对于y排序，我们可以直接对两段区间Sort，然而归并排序本身就是分治，我们可以在CDQ的过程中进行归并排序，要比Sort少一个log

实际效率问题

这道题目还有一种树状数组套Treap的方法
n*log^2(n)
实际效率

还有CDQ套CDQ的方法（即二三维全部用CDQ维护）

CDQ套树状数组

不排除啥快读，指针影响速度，仅供参考，大神勿喷。

题目链接

Luogu
BZOJ
两题目一样，只是BZOJ为权限题目，方便一下大家。

AC Code

压行压的有点厉害，不过CDQ中写的很清晰。

#include 
#include 
#include 
#define il inline
#define lowbit(x) x&(-x)
using namespace std;
const int maxm=1e5+100;
struct node{int x,y,z,ans,id;
};
node a[maxm],b[maxm];
int sum[maxm*2],ans[maxm],k,n;
il int read()
{int x=0,w=1;char ch=0;while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}return x*w;
}
il void ins(int x,int w){for(int i=x;i<=k;i+=lowbit(i)) sum[i]+=w;}
il int ask(int x){int ans=0;for(int i=x;i;i-=lowbit(i)) ans+=sum[i];return ans;}
il bool same(node x1,node x2){return (x1.x==x2.x)&&(x1.y==x2.y)&&(x1.z==x2.z);}
il bool comp(node x1,node x2){return (x1.xvoid CDQ(int l,int r)
{if(l>=r) return;int mid=(l+r)>>1;CDQ(l,mid),CDQ(mid+1,r);for(int i=l,j=l,p=mid+1;i<=r;i++) {if(j<=mid&&(p>r||a[j].y<=a[p].y)) b[i]=a[j++];else b[i]=a[p++];}//归并排序,在这段区间中把y排好.for(int i=l;i<=r;i++) {a[i]=b[i];if(a[i].id<=mid) ins(a[i].z,1);//插入小的 else a[i].ans+=ask(a[i].z);//大的查询 }for(int i=l;i<=r;i++) if(a[i].id<=mid) ins(a[i].z,-1);//消除影响 
}
int main()
{n=read(),k=read();for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].z=read();sort(a+1,a+n+1,comp);int tot=1;node now;for(int i=n;i>=1;i--){if(same(a[i],now)) a[i].ans+=tot++;else now=a[i],tot=1;}for(int i=1;i<=n;i++)a[i].id=i;CDQ(1,n);for(int i=1;i<=n;i++) ans[a[i].ans]++;for(int i=0;iprintf("%d\n",ans[i]);return 0; 
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！