CDQ分治
baike 2019-12-15
分治思想
将较大规模的问题分解为规模较小的子问题，通过解决规模较小的子问题得到较大规模问题的答案
比如 归并排序 或者 快速傅立叶变换 都运用了分治思想
\(CDQ\)分治
既然加了前缀肯定和普通分治不同
\(cdq\)分治重要思想在于将问题分解为较小规模的子问题后，用一个子问题计算对另一个子问题的贡献
如果在刷题过程中遇到疑惑请回来康康上面这句话哦～
这种玄学算法没题怎么讲嘛
例题
裸题
名字好棒的题目啊
题目大意：有\(n\)个元素，第\(i\)个元素有\(a_i,b_i,c_i\)三个属性，设\(f(i)\)表示\(a_j\le a_i,b_j\le b_i,c_j\le c_i\)的\(j\)的数量
对于\(d\in [0,n)\)，求\(f(i)=d\)的数量
请仔细读题大概只有我会读错吧
一个不穿衣服的三维偏序问题，考虑怎么用\(cdq\)分治解决它呢？
cdq套cdq套cdq
我们可以考虑先对\(a_i\)这一维进行排序，令整个序列关于\(a_i\)有序，那么我们现在已经解决掉一维了！
那么接下来怎么办呢？我们可以考虑归并排序
考虑归并排序的过程，每次将当前序列\([l,r]\)分为\([l,mid]\)和\([mid+1,r]\)两个区间
由于我们已经按照\(a_i\)排完序了，所以我们对于\([l,mid]\)这个区间无论怎么操作，对于\([mid+1,r]\)这个区间来说都存在任意\(a_i < a_j ,i\in [l,mid],j\in [mid+1,r]\)
所以我们可以用每个\([l,mid]\)来更新\([mid+1,r]\)答案
但是我们当前只满足了\(a_i<a_j\)，对于\(b_i\)和\(c_i\)怎么处理呢？
我们发现，我们只要按照\(b_i\)的大小进行归并排序就可以处理掉\(b_i\)
对于\(c_i\)，我们把\([l,mid]\)出现的\(c_i\)依次插入树状数组，\([mid+1,r]\)部分得到的贡献就可以用树状数组求得了！
具体实现：
int tl=l,tr=mid+1,to=l;
//用[l,mid]来计算[mid+1,r]的贡献
while(tl<=mid&&tr<=r)
{
if(f[tl].b<=f[tr].b) update(f[tl].c,f[tl].w),t[to++]=f[tl++];//左边的插入树状数组
else f[tr].val+=query(f[tr].c),t[to++]=f[tr++];//右边的加上得到的贡献
}
while(tl<=mid) update(f[tl].c,f[tl].w),t[to++]=f[tl++];
while(tr<=r) f[tr].val+=query(f[tr].c),t[to++]=f[tr++];
for(int i=l;i<=mid;++i) update(f[i].c,-f[i].w);//消除影响
for(int i=l;i<=r;++i) f[i]=t[i];//按b排序\(emmm\)我们发现我们用这种方法需要离线，所以它只能处理可离线的问题
由于该题目一些特性，需要对\(flowers\)去重
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define mid ((l+r)>>1)
#define lowbit(x) ((x)&(-x))
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=2e5+10;
int n,cnt,up;
struct point
{
int a,b,c,w,val;
inline bool operator < (const point &t) const
{
if(a^t.a) return a<t.a;
if(b^t.b) return b<t.b;
return c<t.c;
}
}f[N],t[N];
int tr[N],ans[N];
inline void update(int x,int k)
{
for(int i=x;i<=up;i+=lowbit(i))
tr[i]+=k;
}
inline int query(int y)
{
int ret=0;
for(int i=y;i;i-=lowbit(i))
ret+=tr[i];
return ret;
}
inline void cdq(int l,int r)
{
if(l==r) return ;
cdq(l,mid);
cdq(mid+1,r);
int tl=l,tr=mid+1,to=l;
while(tl<=mid&&tr<=r)
{
if(f[tl].b<=f[tr].b) update(f[tl].c,f[tl].w),t[to++]=f[tl++];
else f[tr].val+=query(f[tr].c),t[to++]=f[tr++];
}
while(tl<=mid) update(f[tl].c,f[tl].w),t[to++]=f[tl++];
while(tr<=r) f[tr].val+=query(f[tr].c),t[to++]=f[tr++];
for(int i=l;i<=mid;++i) update(f[i].c,-f[i].w);
for(int i=l;i<=r;++i) f[i]=t[i];
}
inline void main()
{
cnt=read(),up=read();
for(int i=1;i<=cnt;++i)
{
f[i].a=read(),f[i].b=read(),f[i].c=read();
f[i].w=1;
}
sort(f+1,f+cnt+1);
n=1;
for(int i=2;i<=cnt;++i)
{
if(f[i].a==f[n].a&&f[i].b==f[n].b&&f[i].c==f[n].c) ++f[n].w;
else f[++n]=f[i];
}
cdq(1,n);
for(int i=1;i<=n;++i) ans[f[i].val+f[i].w-1]+=f[i].w;
for(int i=0;i<cnt;++i) printf("%d\n",ans[i]);
}
}
signed main()
{
red::main();
return 0;
}诺基亚好处都有啥
题目大意：
给定大小的矩阵，有两种操作：
\(1.\)向某一点\((x,y)\)增加\(k\)个人
\(2.\)询问某一矩形内有多少人
我们发现其实这个问题也可以转化为三维偏序问题，每个操作有三个属性\((x,y,t)\)，即横坐标，纵坐标，操作时间
不对，你也许会问，操作\(2\)并不是一个点！
我们可以用一个二维差分来解决，将一个询问拆成四个，每次询问代表从以原点为左下角，\((x,y)\)为右上角的矩形内有多少人
当然我们还需要一个标记来判断这个询问的贡献是正是负，不过这个东西并不用在\(cdq\)里处理～
然后就是裸体裸题了吧
