钟鼓楼

钟楼瘦，鼓楼胖

0%

算法设计-分治

Posted on In
Symbols count in article: 7.2k Reading time ≈ 7 mins.

一、CDQ 分治

因为时间的关系，我也不确定我理解的这个套路是否是所谓的 “CDQ 分治”，还是只是一种具有二维偏序特征的模板。

在这种题目中，我们一般会对于一个二维结构体去排序，比如说

struct Node
{
	int x;
	int y;
};

而且排序一般会发生两次，第一次是在开始前先对某个维度进行一遍排序，然后在分治过程中，利用归并排序的思想，在二分的过程中对于另一个维度再次进行排序。也就是如下模板

struct Node
{
	int x;
	int y;
};
// 处理数组
Node a[MAXN];

bool cmp_x(const Node &a, const Node &b)
{
    return a.x < b.x;
}

bool cmp_y(const Node &a, const Node &b)
{
    return a.y < b.y;
}

void rec(int left, int right)
{
    // 边界条件的处理，也可能是其他的
	if (left == right)
    {
        return;
    }
    
    int mid = (left + right) >> 1;
    rec(left, mid);
    rec(mid + 1, right);
    
    // 利用此时 [left, mid], [mid + 1, right] 已经相对于 y 有序的性质，进行一些操作
    // process
    // .....
    
    // inplace_merge 是 std 里的一个方法，他会将有序的 [left, mid) 和 [mid, right) 数组合并成有序的 [left, right) 数组，同时不需要用临时数组
    inplace_merge(a + left, a + mid + 1, a + right + 1, cmp_y);
}

int main()
{
    // input a
    sort(a + left, a + right + 1, sort_x);
    rec(left, right);
}

按照 CDQ 分支的标准定义，它是“每一次划分出来的两个子问题，前一个子问题用来解决后一个子问题，而不是其本身”，这个说法就比较的费解，不过考虑到二分的性质，所有的“后一个问题”就可以组成问题的全体，所以也不是太难理解。

至于为什么前一个问题可以解决后一个问题，我觉得它这里是侧重于两点，一个是在 rec 的操作过程中（就是注释的部分），经常遍历 [mid + 1, right] 这个区间上的元素，同时每次都考虑的是该区间上的元素与 [left, mid] 前面这个区间上全体元素的作用。那么具体利用的性质有两点：

  • [mid + 1, right] 上的所有元素都相对于 [left, mid] 上的元素在 x 维上有序，这是第一次排序导致的。
  • [left, mid] 上的元素是相对于 y 维有序的，这是第二次排序导致的。

我们利用第一条性质确定了作用关系，也就是说，因为右侧元素在 x 维上一定比左侧元素大，所以我们可以进行一定的处理。，第二条性质确定了作用方式，也就是说，因为左侧元素是有序的，所以我们无论是查找还是累加还是贪心，都是很方便的。

在算法运行的过程中，会发现原本相对于 x 有序的数组，逐渐变成了相对于 y 有序的数组，但是因为分治“一层层”进行的特性，所以即使有序性逐渐丧失和重构，也会在母问题中保证对于 x 的有序性，在子问题中保证低于 y 的有序性。

在复杂性分析方面，因为 merge 是 $O(n)$ 的，所以只要 process 的过程是一个复杂度不超过 $O(n^2)$ 的过程，这要求对于右侧每个元素的处理时间复杂度要小于 $O(n)$ ，也就意味着基本上要利用到有序的性质，那么就可以达到优化的目的。

首先看求解逆序数的题目

逆序对

题目描述

猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。

最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

输入格式

第一行，一个数 $n$，表示序列中有 $n$个数。

第二行 $n$ 个数，表示给定的序列。序列中每个数字不超过 $10^9$。

输出格式

输出序列中逆序对的数目。

样例 #1

样例输入 #1

6
5 4 2 6 3 1

样例输出 #1

11

提示

对于 $25\%$ 的数据，$n \leq 2500$

对于 $50\%$ 的数据，$n \leq 4 \times 10^4$。

对于所有数据，$n \leq 5 \times 10^5$

这道题的答案如下

#include <cstdio>
#include <iostream>
using namespace std;
int n, a[500010], c[500010];
long long ans;

void rec(int left, int right) 
{
    if (left == right)
        return;

    int mid = (left + right) / 2, i = left, j = mid + 1, k = left;
    rec(left, mid), rec(mid + 1, right);

	// 这里将 process 和 merge 的过程融合到了一起
    while (i <= mid && j <= right)
        if (a[i] <= a[j])
		{
            c[k++] = a[i++];
		}
        else
		{
            c[k++] = a[j++];
			// 统计答案，利用的是 [left, mid] 的有序性，所以可以直接计算出在 [left, mid] 中大于 a[j] 的元素的个数  
			ans += mid - i + 1; 
		}
    while (i <= mid)
        c[k++] = a[i++];
    while (j <= right)
        c[k++] = a[j++];
    for (int l = left; l <= right; l++)
        a[l] = c[l];
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    rec(1, n);
    printf("%lld", ans);
    return 0;
}

这道题有一些相对于模板的变异：

  • 没有对第一维进行排序：这是因为本质上第一维就是数组下标 index ，所以一定是已经排序好的。
  • merge 和 process 是混合在一起的：这是因为是可以混合在一起的，其实分开也可以。

那么这道题是如何利用二次排序的性质的呢？我们首先回顾逆序数的定义

所以有

  • 第一次排序（实际上没有排序）保证了右侧区间的 index 一定是大于左侧区间的 index 的，所以也就是一定有 i < j （如果 i 在左侧区间，j 在右侧区间），所以我们的下一步就是找到 a[i] > a[j] 的个数（固定 j）。
  • 如果一个个遍历左侧区间去获得 a[i] > a[j] 的个数，那么是不可以的，因为此时这样对于每个右侧元素的时间复杂度就变成了 $O(n)$ ，但是幸亏保证了左侧区间是是有序的，所以我们可以直接利用一个指针进行计算（也就是 a[j + 1] 一定比 a[j] 的逆序数对数多或者相等 ）。

然后看平面最小点对，这个题目严格意义上并不是 CDQ 分治

平面上的最接近点对

题目描述

给定平面上 $n$ 个点，找出其中的一对点的距离，使得在这 $n$ 个点的所有点对中，该距离为所有点对中最小的。

输入格式

第一行一个整数 $n$，表示点的个数。

接下来 $n$ 行，每行两个整数 $x,y$ ，表示一个点的行坐标和列坐标。

输出格式

仅一行，一个实数，表示最短距离，四舍五入保留 $4$ 位小数。

样例 #1

样例输入 #1

3
1 1
1 2
2 2

样例输出 #1

1.0000

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^4$，$0 \leq x, y \leq 10^9$，小数点后的数字个数不超过 $6$。

题解如下

#include <bits/stdc++.h>

using namespace std;

struct Point 
{
	double x;
	double y;
};

const int MAXN = 1e4 + 5;
Point p[MAXN];
int n;
double min_dist = 1e20;

inline void update_ans(const Point &a, const Point &b)
{
	double dist = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
	// cout << "dist: " << dist << endl;
	if (min_dist > dist)
	{
		min_dist = dist;
	}
}

bool cmp_x(const Point &a, const Point &b)
{
	if (a.x == b.x)
	{
		return a.y < b.y;
	}
	else 
	{
		return a.x < b.x;
	}
}

bool cmp_y(const Point &a, const Point &b)
{
	if (a.y == b.y)
	{
		return a.x < b.x;
	}
	else 
	{
		return a.y < b.y;
	}
}

void rec(int left, int right)
{
	// 基准情况，当区间缩小为 3 的时候，进行逐一比较，至于为啥不到 2 ，我也不清楚
	if (right - left <= 3)
	{
		for (int i = left; i <= right; i++)
		{
			for (int j = i + 1; j <= right; j++)
			{
				update_ans(p[i], p[j]);
			}
		}
		// 对于 [left, right] 区间进行按照 y 轴的排序
		sort(p + left, p + right + 1, cmp_y);
		return;
	}
	
	int mid = (left + right) >> 1;
	// 在分治前需要记录相对于 x 轴排序的 mid 的中点的 x 坐标，用于在中线处比较
	double mid_x = p[mid].x;
	// 进行分治，分治的结果是 [left, mid], [mid + 1, right] 两个区间的点都按照 y 轴排序
	rec(left, mid);
	rec(mid + 1, right);
	
	// inplace_merge 表示一种就地的 merge 行为，即将 [left, mid), [mid, right) 两个序列整合成 [left, right) 的有序序列
	// 这种 merge 本来应该是需要临时数组的，但是 inplace_merge 并不需要
	// 经过 merge 后 [left, right) 都是按照 y 轴排列的了
	inplace_merge(p + left, p + mid + 1, p + right + 1, cmp_y);
	
	// 这个 vector 中存储着所有的离 mid 近的点
	vector<Point> near;
	// 遍历所有的点，填写 near，更新答案
	for (int i = left; i <= right; i++)
	{
		// 这是满足进入 near 的条件，新的 min_dist 有可能在 near 中产生
		if (abs(p[i].x - mid_x) < min_dist)
		{
			// 遍历已有的 near，让 p[i] 与 near 相比较，near 一定是 y 升序的
			for (int j = near.size() - 1; j >= 0 && p[i].y - near[j].y < min_dist; j--)
			{
				update_ans(near[j], p[i]);
			}
			// 填充 near
			near.push_back(p[i]);
		}
	}
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> p[i].x >> p[i].y;
	}
	sort(p, p + n, cmp_x);
	rec(0, n - 1);
	
	printf("%.4lf", min_dist);
	return 0;
}

这个题目十分符合两次排序的特征：

  • 第一次排序对于 x 轴进行，这样使得点可以被划分成左右两侧。
  • 第二次排序对于 y 轴进行，并且是在分治过程中完成的。

但是这道题的答案并不是利用左区间的性质解决右区间得出来的，但是依然利用了两次排序的性质：

  • 根据第一次排序的结果，我们找到了 x 轴中线的位置，这样才方便结束了对于两个子问题的二分后，讨论中线附近依然可能存在最小点对的可能。
  • 我们是先进行 merge，然后进行处理，也就是说，处理的时候 [left, right] 已经是一个关于 y 轴有序的数组了，此时我们再进行遍历，可以利用有序性简化 near 数组间的比较（看上去应该是一个 $O(n)$ 的时间，实际上 $O(1)$ 就可以完成）。

下面一道题可以说是 CDQ 分治的板子题，如下所示

[USACO04OPEN] MooFest G

题目描述

约翰的 $n$ 头奶牛每年都会参加“哞哞大会”。

哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。

它们参加活动时会聚在一起，第 $i$ 头奶牛的坐标为 $x_i$，没有两头奶牛的坐标是相同的。

奶牛们的叫声很大，第 $i$ 头和第 $j$ 头奶牛交流，会发出
$\max\{v_i,v_j\}\times |x_i − x_j |$
的音量，其中 $v_i$ 和 $v_j$ 分别是第 $i$ 头和第 $j$ 头奶牛的听力。

假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。

输入格式

第一行：单个整数 $n$，$1\le n\le2\times 10^4$

第二行到第 $n + 1$ 行：第 $i + 1$ 行有两个整数 $v_i$ 和 $x_i$（$1\le v_i,x_i\le2\times 10^4$）。

输出格式

单个整数：表示所有奶牛产生的音量之和

样例 #1

样例输入 #1

4
3 1
2 5
2 6
4 3

样例输出 #1

57

其题解如下

#include <bits/stdc++.h>
using namespace std;

struct Cow 
{
	int x;
	int v;
};

const int MAXN = 1e5 + 5;
Cow a[MAXN], tmp[MAXN];
int n;
long long ans;

bool cmp(const Cow &a, const Cow &b)
{
	return a.v < b.v;
}

bool cmp_x(const Cow &a, const Cow &b)
{
	return a.x < b.x;
}

void CDQ(int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int mid = (left + right) >> 1;
	CDQ(left, mid);
	CDQ(mid + 1, right);
	long long s1 = 0, s2 = 0;

	// 此时 s1 是 [left, mid] 的 x 的和	
	for (int i = left; i <= mid; i++)
	{
		s1 += a[i].x;
	}
	
	int cur = left;
	// 遍历右侧区间，计算右侧区间每个元素对左侧区间所有元素的声音
	// 对于右侧的每个元素 a[i]，其公式为：
	// a[i].x * cnt1 - s2 - a[i].x * cnt2 + s1 
	// cnt1 是左侧区间中小于 a[i].x 的元素的个数
	// cnt2 是左侧区间中大于 a[i].x 的元素的个数
	// s1 是左侧区间中小于 a[i].x 的元素的和
	// s2 是左侧区间中大于 a[i].x 的元素的和
	// 至于为啥要这样计算，是因为可以避免遍历
	// 计算利用了左右侧区间的 x 升序特性
	for (int i = mid + 1; i <= right; i++)
	{
		// cur 是左侧区间的一个分界线，其左侧都是小于 a[i].x
		while (cur <= mid && a[cur].x < a[i].x)
		{
			s2 += a[cur].x;
			s1 -= a[cur].x;
			cur++;
		}	
		long long cnt1 = cur - left;
		long long cnt2 = mid - cur + 1;
		ans += ((cnt1 * a[i].x - s2) + (-cnt2 * a[i].x + s1)) * a[i].v;
	}

	// 进行归并排序
	inplace_merge(a + left, a + mid + 1, a + right + 1, cmp_x);
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i].v >> a[i].x;
	}

	sort(a, a + n, cmp);

	CDQ(0, n - 1);

	cout << ans;
	return 0;
}

这道题属于是，无论是 $max(v_i, v_j)$ 还是 $\vert x_i - x_j \vert$ 都在暗示，必须将枚举 $(i, j)$ 对，才可以解决这个问题，但是实际上，我们可以利用两次排序，避免枚举：

  • 首先对于 v 进行排序
  • 然后在分治过程中，对于 x 进行排序。

我们是这样利用性质的（设 i 为左区间元素，j 为右区间元素）：

  • 因为右区间的 v 一定是大于左区间的 v 的，所以 $max(v_i, v_j) = v_j$ ，所以我们可以考虑对于每一个 j ，其左区间上是如何的（可以合并同类项了）
  • 因为左区间在 x 上是有序的，所以对于 $\vert x_i - x_j \vert$ 这个问题，当固定 j 的时候，一定存在一个 cur 使得当 i < cur 的时候，$x_i < x_j$ ，当 i > cur 的时候，$x_i > x_j$ ，那么就可以将绝对值去掉了，并且不再是加法而改成了乘法。