Love_Elaina's Blog

伟大的离线算法！

前言

由于之前太菜，写的东西比较难蚌，所以被我隐藏了。

因为看到一些写的稀里糊涂的题解，所以我纳闷了好久 CDQ 分治到底是啥，于是就有了这篇学习笔记。

在看这篇之前，你应当掌握树状数组与双指针。

算法介绍

CDQ 分治是一种离线的算法思想，大致可以解决以下三类问题：

1. 与多维数点有关的问题。
2. 1D /1D DP 的优化与转移。
3. 把一些动态的东西转化为静态问题。

CDQ 分治的思想最早由 IOI2008 金牌得主陈丹琦在高中时整理并总结。（崇拜）

算法内容

解决与点对有关的问题

形如给定一个序列，求其中满足某些特殊限制的点对的数量。

CDQ 分治处理某一个序列的算法流程大致如下：

1. 首先找到这个序列的中点 $mid$ 。
2. 把序列拆成两个子序列 $[l,mid],[mid+1,r]$ 。
3. 考虑把贡献拆成三部分计算：只在 $[l,mid]$ 中的，只在 $[mid+1,r]$ 中的以及跨越 $mid$ 的。

我们在处理只在某个子序列中的贡献时，直接向下递归地处理即可，重点在于处理跨越 $mid$ 的点对。

那么就可以视情况而设法处理第三类点的。

这么说还是太抽象了，让我们看一道板子题。

三维偏序

形式化题面：给定 $n$ 个元素，每个元素有三个属性 $a,b,c$ ，求满足 $a_i \le a_j,b_i \le b_j,c_i \le c_j$ 的 $(i,j)$ 点对个数。$n,k \le 10^5$ 。

那么我们根据上述算法流程来解决一下这道题。

为了方便起见，我们把原序列去重，并记 $cnt_i$ 为元素 $a_i,b_i,c_i$ 的数量。

我们只需要考虑如何处理每一个区间跨过 $mid$ 的点对数量，也就是满足 $i\in [l,mid],j\in [mid+1,r]$ 的点对 $(i,j)$，剩下的直接套算法模板即可。

首先，我们可以把所有点对按照 $a_i$ 的大小排个序，这样在处理任意一个子区间时，就可以保证 $i \in[l,mid]$ 的 $a_i$ 必定小于 $i \in[mid+1,r]$ 的 $a_i$ 。

然后，我们分别把 $[l,mid],[mid+1,r]$ 这两个子区间按照 $b_i$ 排序。

这样虽然会使得某一个子区间内的 $a_i$ 顺序被打乱，但是我们只需要处理 $i \in [l,mid],j\in [mid+1,r]$ 的点对，以上排序完后仍然可以保证前半部分的 $a_i$ 必定小于后半部分的 $a_i$ ，所以并不会出错。

接着，我们可以开一个权值树状数组，并且考虑双指针，定义 $q$ 在区间 $[mid+1,r]$ 内，$p$ 在区间 $[l,mid]$ 内。对于每个 $q$ ，枚举 $p$，直到找到最靠后的 $p$ 满足 $b_p \le b_q$ 为止，每一次都将权值树状数组中 $c_p$ 的位置加上 $cnt_p$ ，找到上述的 $p$ 后，将 $ans_q$ 加上权值树状数组中 $[1,c_q]$ 的贡献即可。

时间复杂度：以上过程最多执行 $O(n \log n)$ 次，每一次时间复杂度瓶颈在权值树状数组和排序的 $O(\log n)$ ，所以总时间复杂度为 $O(n \log n^2)$ 。

由于树状数组和排序的常数都很小，所以即使是 $10^6$ 也可以多卡一卡，万一就卡过去了呢（。

注意需要从小到大处理，否则序列会乱掉。每次完成后把树状数组清空，不要用 memset ，这会使复杂度变为 $O(n^2 \log n^2) 。$

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+9;
const int INF=1e18;
const int MOD=998244353;
int n,K;
int a[maxn],b[maxn],c[maxn];
struct node
{
	int a,b,c,cnt;
	int res;
	bool operator<(const node y) const{return a!=y.a?a<y.a:b!=y.b?b<y.b:c<y.c;}
}s[maxn];
bool cmp(node a,node b) {if(a.b==b.b) return a.c<b.c;return a.b<b.b;}
int t[maxn];
int lowbit(int x) {return x&-x;}
void add(int k,int x) {for(int i=k;i<=K;i+=lowbit(i)) t[i]+=x;}
//注意这里是权值树状数组，所以上界应该是原序列中的 max(a[i],b[i],c[i])。
int ask(int x,int y) 
{
	int res=0;
	for(int i=y;i;i-=lowbit(i)) res+=t[i];
	for(int i=x-1;i;i-=lowbit(i)) res-=t[i];
	return res;
}
int ans[maxn];
node tmp[maxn];
void cdq(int l,int r)
{
	if(l==r) return;
	int mid=(l+r)/2;
	cdq(l,mid);cdq(mid+1,r);//首先递归地处理小的区间
	sort(s+l,s+mid+1,cmp);sort(s+mid+1,s+r+1,cmp);
	int j=l;
	for(int i=mid+1;i<=r;i++) 
	{
		while(j<=mid&&s[j].b<=s[i].b)
		{
			add(s[j].c,s[j].cnt);
			j++;
		}
		s[i].res+=ask(1,s[i].c);
	}
	for(int i=l;i<j;i++) add(s[i].c,-s[i].cnt);
}
signed main()
{
	//freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>K;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];
	int tot=1;
	for(int i=1;i<=n;i++) s[i].a=a[i],s[i].b=b[i],s[i].c=c[i],s[i].cnt=1;
	sort(s+1,s+n+1);
	for(int i=2;i<=n;i++)
	{
		if(s[i].a!=s[tot].a||s[i].b!=s[tot].b||s[i].c!=s[tot].c) s[++tot]=s[i];
		else s[tot].cnt++;
	}//对原序列去重。
	cdq(1,tot);
	for(int i=1;i<=tot;i++) ans[s[i].res+s[i].cnt-1]+=s[i].cnt;//由于题目让我们输出 f[i]=p 的 i 数量，完全相同的元素也会对除自己之外的彼此做出贡献，所以做如上处理。
	for(int i=0;i<n;i++) cout<<ans[i]<<'\n';
	return 0;
}

如果你想追求更小的常数，可以把 CDQ 分治部分这样写：

void cdq(int l,int r)
{
	if(l==r) return;
	int mid=(l+r)/2;
	cdq(l,mid);cdq(mid+1,r);
	int p=l,q=mid+1,len=0;
	while(p<=mid&&q<=r) 
	{
		if(s[p].b<=s[q].b) add(s[p].c,s[p].cnt),tmp[++len]=s[p++];
		else s[q].res+=ask(1,s[q].c),tmp[++len]=s[q++];
	}
	while(p<=mid) add(s[p].c,s[p].cnt),tmp[++len]=s[p++];
	while(q<=r) s[q].res+=ask(1,s[q].c),tmp[++len]=s[q++];
	for(int i=l;i<=mid;i++) add(s[i].c,-s[i].cnt);
	for(int i=1;i<=len;i++) s[l+i-1]=tmp[i];
}

这个方式的优点是省去了处理每个子区间时排序的时间复杂度，而是在每次分治过程中，把序列按照 $b_i$ 就排好了序，所以在处理上一层时，就不需要再 sort 了。

实测最慢的点只需要跑 $92ms$ 。

[CQOI2011] 动态逆序对

形式化题面：给定一个序列 $n$ ，要按照某种顺序删除 $m$ 个元素，求每次删除前整个序列的逆序对个数。$n \le 10^5,m \le 5 \times 10^4$ 。

考虑记 $a_i$ 为序列中第 $i$ 个元素的权值，记 $b_i$ 为位置，记 $c_i$ 为第几个被删除，那么就变成三维偏序的板子了。

以上就是本文中 CDQ 分治如何解决数点问题的内容。对于数点问题，除了 CDQ 分治还可以用树套树，整体二分，KDT，bitset 等来解决。CDQ 的优势在于较为好写并且相对常数和时间较为优秀。不过由于 CDQ 是离线算法，如果遇到强制在线的题就还是用树套树吧。（

优化 1D/1D DP

1D/1D DP 是指一类 DP 数组是一维，转移是 $O(n)$ 的动态规划。这时可以考虑用 CDQ 分治将其时间复杂度降为 $O(n \log n^2)$ 。

算法流程可以类比求数点问题：

1. 如果 $l=r$ ，说明 $dp_r$ 已经被计算好了。直接让 $dp_r++$ 即可。
2. 把当前处理的区间的拆成两个区间 $[l,mid],[mid+1,r]$ ，并递归地调用 CDQ 分治。
3. 设法处理所有 $j \in [l,mid],i \in [mid+1,r]$ 的 $dp$ 转移。

举个例子。

二维最长上升子序列。

容易想到 $dp_i$ 为前 $i$ 个的最长上升子序列，转移也很显然：

$$dp_i=\max dp_j [a_j<a_i][b_j<a_j]+1$$

这显然是 $O(n^2)$ 的，接下来用 CDQ 分治来优化一下。

可以类比三位偏序的处理方式，处理 $l \leq j \leq mid，mid+1 \leq i \leq r$ 的转移关系的时候，我们会发现已经不用管 $j<i$ 这个限制条件了。因此，我们依然先将所有的点 $i$ 和点 $j$ 按 $a$ 值进行排序处理，然后用双指针的方式将所有满足 $b_j < b_i$ 的 $dp_j$ 扔进树状数组里，最后查一下前缀最大值更新一下 $dp_i$ 就可以了。