\(cdq\) 分治是一种离线分治算法，可以将动态问题改变为静态问题，不适用于强制在线。其实现时通常将需要进行的操作存进一个
结构体，然后对这些操作进行分治。
打 \(cdq\) 分治时一个直观的感受就是很好想思路，但就是不知道怎么打。。。
它一共有三个需要干的
-
1 找到范围中点 \(mid\) ,递归解决 \((l,mid)\)
-
2 递归解决 \((mid+1,r)\)
-
3 找出 \(mid\) 左边的修改对 \(mid\) 右面的查询的影响，计入答案
\(cdq\) 分治的主要作用是解决偏序问题，所以只要一道题的询问信息有明显的比较关系，我们就可以考虑用 \(cdq\) 解决，所以
经常会在一些树套树的题的题解区看到有 \(dalao\) 用 \(cdq\) 碾过去
模板
这里的板子是 \(cdq\) 内归并排序的板子和配队的树状数组的板子，好像要快一点？
\(cdq\) 内的 \(if,else\) 应根据题目适当修改
点击查看代码
struct tree
{
inline int lowbit(int x){return x&-x;}
inline void add(int x,int y)
{
while(x<=n)
{
if(vis[x]!=dfn) vis[x]=dfn,c[x]=0;
c[x]+=y;
x+=lowbit(x);
}
}
inline int query(int x)
{
int temp=0;
while(x)
{
if(vis[x]==dfn)temp+=c[x];
x-=lowbit(x);
}
return temp;
}
}e;
inline void cdq(int l,int r)
{
if(l==r) return;
int mid=l+r>>1;
cdq(l,mid),cdq(mid+1,r);
dfn++;
int ll=l,rr=mid+1;
for(int i=l;i<=r;i++)
{
if(ll<=mid&&q[ll].x<=q[rr].x||rr>r)
{
if(q[ll].opt==0)e.add(q[ll].y,-q[ll].xy);
a[i]=q[ll];
ll++;
}
else
{
if(q[rr].opt==1)ans[q[rr].id]=min(ans[q[rr].id],e.query(q[rr].y)+q[rr].xy);
a[i]=q[rr];
rr++;
}
}
for(int i=l;i<=r;i++) q[i]=a[i];
}
二维偏序
这个题实际上就是一个二维偏序问题，我们考虑对一个点 \(x\) 有贡献的操作有什么，是比它时间早的且坐标靠前的点
所以这里的两维分别是时间，坐标。
点击查看代码
#include<bits/stdc++.h>
#define int long long
const int maxn=5e5+10;
using namespace std;
struct lsx{int x,c,opt,cnt,ct;}q[maxn*3],t[maxn*3];
int n,m,ct,a[maxn],cnt,ans[maxn],s[maxn];
bool cmp(lsx a,lsx b){return a.x!=b.x?a.x<b.x:a.opt>b.opt;}
void cdq(int l,int r)
{
if(l==r) return ;
int mid=l+r>>1,temp=0;
for(int i=l;i<=r;i++)
if(q[i].cnt<=mid&&q[i].opt) temp+=q[i].c;
else if(q[i].cnt>mid&&!q[i].opt) ans[q[i].ct]+=temp*q[i].c;
int ll=l,rr=mid+1;
for(int i=l;i<=r;i++) if(q[i].cnt<=mid) t[ll++]=q[i];else t[rr++]=q[i];
for(int i=l;i<=r;i++) q[i]=t[i];
cdq(l,mid),cdq(mid+1,r);
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i];
}
for(int i=1;i<=m;i++)
{
int x;
scanf("%lld",&x);
if(x==1) ++cnt,scanf("%lld%lld",&q[cnt].x,&q[cnt].c),q[cnt].opt=1,q[cnt].cnt=cnt;
else
{
int l,r;
scanf("%lld%lld",&l,&r);
++ct,++cnt;
q[cnt]={l-1,-1,0,cnt,ct};
++cnt;
q[cnt]={r,1,0,cnt,ct};
ans[ct]=s[r]-s[l-1];
}
}
sort(q+1,q+cnt+1,cmp);
cdq(1,cnt);
for(int i=1;i<=ct;i++) printf("%lld\n",ans[i]);
return 0;
}
三维偏序
这题的三个偏序关系已经给出，第一维 \(sort\)，第二维 \(cdq\) ，第三维数据结构
点击查看代码
#include<bits/stdc++.h>
const int maxn=3e5+10;
using namespace std;
int n,k,cnt,c[maxn],dfn,vis[maxn],ans[maxn],temp[maxn];
struct lsx{int x,y,z,id,w;}q[maxn],t[maxn],a[maxn];
bool cmp(lsx a,lsx b)
{
return a.x!=b.x?a.x<b.x:(a.y!=b.y?a.y<b.y:a.z<b.z);
}
bool check(lsx a,lsx b)
{
if(a.x==b.x&&a.y==b.y&&a.z==b.z) return 1;
else return 0;
}
int lowbit(int x){return x&-x;}
void add(int x,int y)
{
while(x<=k)
{
if(vis[x]!=dfn) vis[x]=dfn,c[x]=0;
c[x]+=y;
x+=lowbit(x);
}
}
int query(int x)
{
int temp=0;
while(x)
{
if(vis[x]==dfn)temp+=c[x];
x-=lowbit(x);
}
return temp;
}
void cdq(int l,int r)
{
if(l==r) return;
int mid=l+r>>1;
cdq(l,mid),cdq(mid+1,r);
dfn++;
int ll=l,rr=mid+1;
for(int i=l;i<=r;i++)
{
if(ll<=mid&&q[ll].y<=q[rr].y||rr>r)
{
add(q[ll].z,q[ll].w);
t[i]=q[ll++];
}
else
{
temp[q[rr].id]+=query(q[rr].z);
t[i]=q[rr++];
}
}
for(int i=l;i<=r;i++) q[i]=t[i];
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
}
sort(a+1,a+n+1,cmp);
int l=1;
while(l<=n)
{
int r=l+1;
while(r<=n&&check(a[l],a[r]))r++;
q[++cnt]=a[l];
q[cnt].w=r-l;
q[cnt].id=cnt;
l=r;
}
cdq(1,cnt);
for(int i=1;i<=cnt;i++) ans[temp[q[i].id]+q[i].w-1]+=q[i].w;
for(int i=0;i<n;i++) printf("%d\n",ans[i]);
return 0;
}
三维偏序应用
这题考虑对一个坐标产生影响的操作是：时间更早，坐标考前，且比他大的值/时间更早，坐标考后，且比他小的值
所以这里的三个偏序关系是：时间，坐标，大小。
直接删肯定不好操作，我们反过来插入，考虑每次插入时新加的逆序对数有多少，权值树状数组维护即可。（要跑两遍）
点击查看代码
#include<bits/stdc++.h>
#define int long long
const int maxn=1e5+10;
using namespace std;
int n,m,cnt,c[maxn],dfn,vis[maxn],ans[maxn],t,x[maxn],pre[maxn];
int in[maxn];
struct lsx{int t,pos,x,id;}q[maxn],a[maxn];
struct tree
{
inline int lowbit(int x){return x&-x;}
inline void add(int x,int y)
{
while(x<=n)
{
if(vis[x]!=dfn) vis[x]=dfn,c[x]=0;
c[x]+=y;
x+=lowbit(x);
}
}
inline int query(int x)
{
int temp=0;
while(x)
{
if(vis[x]==dfn)temp+=c[x];
x-=lowbit(x);
}
return temp;
}
}e;
inline void cdq(int l,int r)
{
if(l==r) return;
int mid=l+r>>1;
cdq(l,mid),cdq(mid+1,r);
dfn++;
int ll=l,rr=mid+1;
for(int i=l;i<=r;i++)
{
if(ll<=mid&&q[ll].pos<q[rr].pos||rr>r)
{
e.add(q[ll].x,1);
ll++;
}
else
{
ans[q[rr].id]+=e.query(n)-e.query(q[rr].x);
rr++;
}
}
dfn++;
ll=mid,rr=r;
for(int i=l;i<=r;i++)
{
if(ll>=l&&q[ll].pos>q[rr].pos||rr<=mid)
{
e.add(q[ll].x,1);
ll--;
}
else
{
ans[q[rr].id]+=e.query(q[rr].x-1);
rr--;
}
}
ll=l;rr=mid+1;
for (int i=l;i<=r;i++)
{
if ((ll<=mid&&q[ll].pos<q[rr].pos)||rr>r) a[i]=q[ll++];
else a[i]=q[rr++];
}
for(int i=l;i<=r;i++) q[i]=a[i];
}
signed main()
{
// freopen("P3157_1.in","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>x[i];
}
for(int i=1;i<=m;i++)
cin>>in[i],pre[in[i]]=1;
for(int i=1;i<=n;i++)
{
if(!pre[x[i]])
{
q[++cnt]={cnt,i,x[i],0};
}
else pre[x[i]]=i;
}
for(int i=m;i>=1;i--)
{
q[++cnt]={cnt,pre[in[i]],in[i],m-i+1};
}
cdq(1,cnt);
for(int i=1;i<=m;i++) ans[i]+=ans[i-1];
for(int i=m;i>=1;i--)
cout<<ans[i]<<'\n';
return 0;
}
求关于某个点曼哈顿距离（\(x,y\) 坐标）最近的点——\(dis(A,B) = |Ax-Bx|+|Ay-By∣\)
假设所有的点都在查询点的左下方，\(dis(A,B) = (Ax-Bx)+(Ay-By) = (Ax+Ay)-(Bx+By)\)
只要求满足\(Bx<Ax,By<Ay\) 且 \(Bx,By\) 之和最大的点就好了。
把整个平面翻转三次，进行四次\(cdq\) 分治，每次都只考虑左下的点即可
点击查看代码
#include<bits/stdc++.h>
const int maxn=1e6+1;
const int M=1e6+2;
using namespace std;
int n,m,cnt,c[M+8],dfn,vis[maxn],ans[maxn];
int in[maxn];
struct lsx{int x,y,id,xy,opt;}q[maxn],a[maxn],b[maxn];
struct tree
{
inline int lowbit(int x){return x&-x;}
inline void add(int x,int y)
{
while(x<=M)
{
if(vis[x]!=dfn) vis[x]=dfn,c[x]=1e9;
c[x]=min(c[x],y);
x+=lowbit(x);
}
}
inline int query(int x)
{
int temp=1e9;
while(x)
{
if(vis[x]==dfn)temp=min(c[x],temp);
x-=lowbit(x);
}
return temp;
}
}e;
inline void cdq(int l,int r)
{
if(l==r) return;
int mid=l+r>>1;
cdq(l,mid),cdq(mid+1,r);
dfn++;
int ll=l,rr=mid+1;
for(int i=l;i<=r;i++)
{
if(ll<=mid&&q[ll].x<=q[rr].x||rr>r)
{
if(q[ll].opt==0)e.add(q[ll].y,-q[ll].xy);
a[i]=q[ll];
ll++;
}
else
{
if(q[rr].opt==1)ans[q[rr].id]=min(ans[q[rr].id],e.query(q[rr].y)+q[rr].xy);
a[i]=q[rr];
rr++;
}
}
for(int i=l;i<=r;i++) q[i]=a[i];
}
int main()
{
// freopen("P4169_10.in","r",stdin);
// freopen("ans.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
memset(ans,0x7f,sizeof ans);
cin>>n>>m;
int x,y,z;
for(int i=1;i<=n;i++)
{
cin>>x>>y;x++,y++;
b[i]={x,y,0,x+y,0};
}
for(int i=1;i<=m;i++)
{
cin>>z>>x>>y;x++,y++;
b[i+n]={x,y,0,x+y,z-1};
if(b[i+n].opt==1)
{
b[i+n].id=++cnt;
}
}
for(int i=1;i<=n+m;i++) {
q[i]=b[i];
}
cdq(1,n+m);
for(int i=1;i<=n+m;i++) {
q[i]=b[i];
q[i].x=M-b[i].y;q[i].y=b[i].x;
q[i].xy=q[i].x+q[i].y;
}
cdq(1,n+m);
for(int i=1;i<=n+m;i++) {
q[i]=b[i];
q[i].x=M-b[i].x;q[i].y=M-b[i].y;
q[i].xy=q[i].x+q[i].y;
}
cdq(1,n+m);
for(int i=1;i<=n+m;i++) {
q[i]=b[i];
q[i].x=b[i].y;q[i].y=M-b[i].x;
q[i].xy=q[i].x+q[i].y;
}
cdq(1,n+m);
for(int i=1;i<=cnt;i++)
{
cout<<ans[i]<<'\n';
}
return 0;
}