首页 > 其他分享 >cdq 分治

cdq 分治

时间：2024-05-04 16:44:24浏览次数：24  
标签：pr 偏序 int 分治 mid cdq pl

1 概念

cdq 分治，是一种分治思想而非具体算法。它是基于分治思想，将复杂的问题拆分求解。

与一般分治算法不同的是，一般分治所拆分的子问题互相独立、互不干扰、形式与原问题一致。而在 cdq 分治中，每次划分出的两个子问题，是利用前面的子问题解决后面的子问题。也就是说，对于序列 \([l,r]\)，我们先解决 \([l,mid)\) 的子问题，然后处理 \([l,mid)\) 对于 \([mid,r]\) 的贡献、影响，接着递归处理 \([mid,r]\)。

cdq 分治是一种离线算法，做题时需要注意这点。

2 基础例题

2.1 偏序问题

偏序问题是利用 cdq 分治求解的经典问题。

在这之前我们先需要看一个分治的经典应用：归并排序。

2.1.1 归并排序

void merge_sort(int l, int r) {
	if(l == r) return ;
	int mid = (l + r) >> 1;
	merge_sort(l, mid);
	merge_sort(mid + 1, r);
	int pl = l, pr = mid + 1;
	for(int i = l; i <= r; i++) {
		if((a[pl] < a[pr] && pl <= mid) || pr > r) {
			b[i] = a[pl++];
		}
		else {
			b[i] = a[pr++]; 
		}
	}
	for(int i = l; i <= r; i++) {
		a[i] = b[i];
	}
}

这是经典的归并排序代码，看上去就是一个普通分治。但是我们知道，归并排序的一个经典用途就是求逆序对。

我们将核心部分修改为这样：

int ans = 0;
void merge_sort(int l, int r) {
	if(l == r) return ;
	int mid = (l + r) >> 1;
	merge_sort(l, mid);
	merge_sort(mid + 1, r);
	int pl = l, pr = mid + 1;
	for(int i = l; i <= r; i++) {
		if((a[pl] < a[pr] && pl <= mid) || pr > r) {
			b[i] = a[pl++];
		}
		else {
			b[i] = a[pr++];
			ans += mid - pl + 1;
		}
	}
	for(int i = l; i <= r; i++) {
		a[i] = b[i];
	}
}

现在我们重新审视一下这个归并排序。它首先将整个区间 \([l,r]\) 分成两部分求解。而在合并的过程中，当右半部分的某一个值小于当前左半部分时，左半部分剩下的所有数字一定都和右半部分的这个值构成逆序对。

也就是说，归并排序求逆序对实际上已经运用了 “用左边信息计算右边信息” 的思想了。这也是 cdq 分治一个简单的应用。而本质上，这就是一个二维偏序问题。

2.1.2 二维偏序

题意：有 \(n\) 个二元组 \((a_i,b_i)\)，求出满足 \(a_j< a_i,b_j< b_i\) 且 \(i\ne j\) 的 \((i,j)\) 的数量。

考虑我们刚刚求逆序对的过程，其实是给出二元组 \((i,a_i)\)，求 \(i< j,a_i> a_j\) 的数量。这本质上就是一个二维偏序问题。

不同的地方在于，逆序对已经自动将 \(i\) 排好序了。那我们也可以仿照，在二维偏序中首先将 \(a_i\) 排序，然后求解的就是 \(b\) 上的 “顺序对” 问题了。

也就是说，我们求解二维偏序的时候其实是通过一次排序降掉了一维 \(a_i\)，然后利用 cdq 处理第二维。这也是求解高维偏序的基本思路：降维。

（当然我们发现 \(b\) 上的问题也可以用树状数组解）

那我们看一下二维偏序的模板：「一本通 4.1 例 2」数星星 Stars。代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int Maxn = 2e5 + 5;

int n;
struct node {
	int x, y;
	int num;
	bool operator < (const node &b) const {
		if(x == b.x) return y < b.y;
		return x < b.x;
	}
}p[Maxn], b[Maxn];

int ans[Maxn];

void cdq(int l, int r) {
	if(l == r) return ;
	int mid = (l + r) >> 1;
	cdq(l, mid);
	cdq(mid + 1, r);
	int pl = l, pr = mid + 1;
	for(int i = l; i <= r; i++) {
		if((p[pl].y <= p[pr].y && pl <= mid) || (pr > r)) {
			b[i] = p[pl++];
		}
		else {
			p[pr].num += pl - l;
			b[i] = p[pr++];
		}
	}
	for(int i = l; i <= r; i++) {
		p[i] = b[i];
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> p[i].x >> p[i].y;
	}
	sort(p + 1, p + n + 1);
	cdq(1, n);
	for(int i = 1; i <= n; i++) {
		ans[p[i].num]++;
	}
	for(int i = 0; i < n; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

2.1.3 三维偏序

这才是 cdq 的模板：【模板】三维偏序（陌上花开）。

考虑到三维偏序就是在二维偏序之上再加一维，那么继续使用降维思想。

首先第一维 \(a_i\) 可以简单做掉，第二维我们考虑使用 cdq 分治。在上面二维偏序中，我们统计答案直接加上了 \(pl-l\)，但在三维偏序中我们还要判断第三维的关系才能修改答案。因此第三维可以用树状数组维护。

也就是说，三维偏序我们可以使用 cdq 分治 + 树状数组解决。时间复杂度 \(O(n\log^2 n)\)。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int Maxn = 2e5 + 5;

int n, d, m;
struct node {
	int x, y, z, val;
	int num;
	bool operator < (const node &b) const {
		if(x != b.x) return x < b.x;
		if(y != b.y) return y < b.y;
		return z < b.z;
	}
}p[Maxn], tmp[Maxn], b[Maxn];

int mx;
struct BIT {//第三维
	int c[Maxn];
	void init() {
		memset(c, 0, sizeof c);
	}
	int lowbit(int x) {
		return x & (-x);
	}
	void mdf(int x, int val) {
		for(int i = x; i <= mx; i += lowbit(i)) {
			c[i] += val;
		}
	}
	int query(int x) {
		int sum = 0;
		for(int i = x; i; i -= lowbit(i)) {
			sum += c[i];
		}
		return sum;
	}
}B;

struct Cdq {//第二维
	void cdq(int l, int r) {
		if(l == r) return;
		int mid = (l + r) >> 1;
		cdq(l, mid);
		cdq(mid + 1, r);
		int pl = l, pr = mid + 1;
		for(int i = l; i <= r; i++) {
			if((p[pl].y <= p[pr].y && pl <= mid) || (pr > r)) {
				B.mdf(p[pl].z, p[pl].val);
				b[i] = p[pl++];
			}
			else {
				p[pr].num += B.query(p[pr].z);
				b[i] = p[pr++];
			}
		}
		for(int i = l; i < pl; i++) {
			B.mdf(p[i].z, -p[i].val);
		}
        //树状数组清空不能用 memset，会 TLE
		for(int i = l; i <= r; i++) {
			p[i] = b[i];
		}
	}
}C;

int ans[Maxn];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> mx;
	for(int i = 1; i <= n; i++) {
		cin >> tmp[i].x >> tmp[i].y >> tmp[i].z; 
	}
	sort(tmp + 1, tmp + n + 1);
	int num = 0;
	for(int i = 1; i <= n; i++) {//去重
		num++;
		if(tmp[i].x != tmp[i + 1].x || tmp[i].y != tmp[i + 1].y || tmp[i].z != tmp[i + 1].z) {
			p[++m] = tmp[i];
			p[m].val = num;
			num = 0;
		}
	}
    //数据中可能存在完全一样的三元组，这些三元组之间都有贡献。但是 cdq 分治只能解决左区间对右区间的贡献。
	C.cdq(1, m);
	for(int i = 1; i <= m; i++) {
		ans[p[i].num + p[i].val - 1] += p[i].val;
	}
	for(int i = 0; i < n; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

考虑到上面我们采取降维的思想，将前两维降掉后第三维采用的是树状数组。其实，我们第三维也可以使用 cdq 分治。因此三维偏序的另一种解法就是 cdq 套 cdq。时间复杂度 \(O(n\log^2n)\)，但是常数相较于上一种做法要高。

当然 cdq 套 cdq 是解决偏序问题的通法，对于 \(k\) 维偏序，时间复杂度为 \(O(n\log ^{k-1}n)\)。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int Maxn = 2e5 + 5;

int n, mx, m;
struct node {
	int x, y, z;
	int num, ans, id;
	bool op;
	bool operator < (const node &b) const {
		if(x != b.x) return x < b.x;
		if(y != b.y) return y < b.y;
		return z < b.z;
	}
}tmp[Maxn], a[Maxn], b[Maxn], c[Maxn];

struct Cdq {
	void cdq1(int l, int r) {//第二层 cdq
		if(l == r) {
			return ;
		}
		int mid = (l + r) >> 1;
		cdq1(l, mid);
		cdq1(mid + 1, r);
		int pl = l, pr = mid + 1, cnt = 0;
		for(int i = l; i <= r; i++) {
			if((b[pl].z <= b[pr].z && pl <= mid) || pr > r) {
				c[i] = b[pl++];
				if(c[i].op == 0) {//只有在左边的点才会对右边的点产生贡献
					cnt += c[i].num;
				}
			}
			else {
				if(b[pr].op == 1) {//只有右边的点才能接受贡献
					a[b[pr].id].ans += cnt;//累加答案
				}
				c[i] = b[pr++];
			}
		}
		for(int i = l; i <= r; i++) {
			b[i] = c[i];
		}
	}
	void cdq(int l, int r) {//第一层 cdq
		if(l == r) return ;
		int mid = (l + r) >> 1;
		cdq(l, mid);
		cdq(mid + 1, r);
		int pl = l, pr = mid + 1;
		for(int i = l; i <= r; i++) {
			if((a[pl].y <= a[pr].y && pl <= mid) || pr > r) {
				b[i] = a[pl++];
				b[i].op = 0;
			}
			else {
				b[i] = a[pr++];
				b[i].op = 1;//b 中记录这个节点在放在左边还是右边
			}
		}
		for(int i = l; i <= r; i++) {
			a[i] = b[i];
			b[i].id = i;
		}
		cdq1(l, r);
	}
}C;

int ans[Maxn];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> mx;
	for(int i = 1; i <= n; i++) {
		cin >> tmp[i].x >> tmp[i].y >> tmp[i].z;
	}
	sort(tmp + 1, tmp + n + 1);
	int num = 0;
	for(int i = 1; i <= n; i++) {
		num++;
		if(tmp[i].x != tmp[i + 1].x || tmp[i].y != tmp[i + 1].y || tmp[i].z != tmp[i + 1].z) {
			a[++m] = tmp[i];
			a[m].num = num;
			num = 0;
		}
	}
	C.cdq(1, m);
	for(int i = 1; i <= m; i++) {
		ans[a[i].ans + a[i].num - 1] += a[i].num;
	}
	for(int i = 0; i < n; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

2.2 动态变静态

这也是 cdq 分治的一个基础应用。所谓动态变静态，就是将动态解决的问题化为静态问题。而一个动态问题则会有修改和查询操作，我们将他们离线下来，按照时间顺序排开，接着我们在时间轴上进行 cdq 分治。

具体的，我们先递归处理左区间，然后处理左区间的修改对于右区间的查询的影响，最后处理右区间。

例如这道题：【模板】树状数组 1，用树状数组十分简单，但是 cdq 分治也可以动态变静态完成。这里我们将查询操作拆成两个前缀和求解。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int Maxn = 2e6 + 5;

int n, m;
struct node {
	int opt, id, val;
    //opt=1 表示修改，opt=2 表示查询左端点，opt=3 表示查询右端点
    //id 表示查询或修改的下标
    //当修改时，val 表示修改的值；当查询时，val 表示查询是第几个查询
	bool operator < (const node &b) const {
		if(id != b.id) return id < b.id;
		return opt < b.opt;
	}
}q[Maxn], b[Maxn];

int tot, cnt;
int ans[Maxn];

void cdq(int l, int r) {
	if(l == r) return ;
	int mid = (l + r) >> 1;
	cdq(l, mid);
	cdq(mid + 1, r);
	int pl = l, pr = mid + 1, sum = 0;
	for(int i = l; i <= r; i++) {
		if((q[pl] < q[pr] && pl <= mid) || pr > r) {
			if(q[pl].opt == 1) sum += q[pl].val;
            //记录左区间的修改
			b[i] = q[pl++];
		}
		else {
			if(q[pr].opt == 2) ans[q[pr].val] -= sum;
			if(q[pr].opt == 3) ans[q[pr].val] += sum;
            //计算右区间的查询
			b[i] = q[pr++];
		}
	}
	for(int i = l; i <= r; i++) {
		q[i] = b[i];
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		int p;
		cin >> p;
		q[++tot] = {1, i, p};//将初始操作也看做查询
	}
	while(m--) {
		int opt, x, y;
		cin >> opt >> x >> y;
		if(opt == 1) {
			q[++tot] = {1, x, y};
		}
		else {
			q[++tot] = {2, x - 1, ++cnt};
			q[++tot] = {3, y, cnt};
		}
	}
	cdq(1, tot);
	for(int i = 1; i <= cnt; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

2.3 1D/1D 动态规划

1D/1D 动态规划是指这样一类动态规划：dp 数组为 \(1\) 维，单次转移复杂度 \(O(n)\) 的动态规划。经典的 1D/1D 动态规划模型就是最长上升子序列。

1D/1D 动态规划的优化方式有很多，例如单调队列优化、斜率优化、四边形不等式优化等等。但是 cdq 分治同样可以用于优化 1D/1D 动态规划问题。

我们以最长上升子序列为例，观察它的转移方程：

\[dp_i=\max_{j<i,a_j<a_i}\{dp_j\}+1 \]

我们发现 \(\max\) 底下那一坨是 \(j<i,a_j<a_i\)，就是一个二维偏序。因此我们在 cdq 分治的时候利用二维偏序关系更新 \(dp\) 数组即可。

但是此时要注意，我们的流程是先递归左半部分，处理左半部分对于右半部分的贡献，最后再处理右半部分。因为 \(dp\) 数组是需要更新后才能继续计算的。

代码：

void cdq(int l, int r) {
	if(l == r) {
		return ;
	}
	int mid = (l + r) >> 1;
	cdq(l, mid);
	sort(p + l, p + mid + 1, cmp);
	sort(p + mid + 1, p + r + 1, cmp);//先对左右两部分排序，满足单调性后才可以求解
	int pl = l, pr = mid + 1, mx = 0;
	for(int i = l; i <= r; i++) {
		if((p[pl].val < p[pr].val && pl <= mid) || pr > r) {
			mx = max(mx, dp[p[pl].id]);//左边记录最大值
			pl++;
		}
		else {
			dp[p[pr].id] = max(dp[p[pr].id], mx + 1);//右边直接修改
			pr++;
		}
	}
	sort(p + mid + 1, p + r + 1, cmp2);
    //按照下标排序，也就是要在递归前将下标这一维降去
	cdq(mid + 1, r);
}

时间复杂度是 \(O(n\log^2 n)\) 的，只比暴力 \(O(n^2)\) 要好一点，比不上二分贪心的 \(O(n\log n)\)。不过如果限制条件变为 \(j<i,a_j<a_i,b_j<b_i\)，，也就是二维最长上升子序列的时候，cdq 分治就是一种不错的选择了。

标签：pr,偏序,int,分治,mid,cdq,pl
From： https://www.cnblogs.com/dzbblog/p/18172458

相关文章

  • CF-797-E-根号分治
    797-E题目大意给定一个长为\(n\)序列\(a\)，有\(q\)次询问：给定\(p,k\)，你需要反复执行操作\(p=p+a_p+k\)，直到\(p>n\)为止，问你要执行多少次操作。Solution考虑两种思路：1、暴力回答询问，每次反复模拟操作，直到\(p>n\)为止，时间复杂度\(O(q·\frac{n}{k})\)。2、预处理出......
  • 点分治
    点分治本质就是树上的分治。序列的分治是不断地将序列二分，而对于树则需要利用树的重心。树的重心定义：树中一节点，以它为根的最大的子树最小。求解：跑一遍\(dfs\)求解即可。voidget_rt(intu,intfa){ siz[u]=1,max_siz[u]=0; for(autov:T[u]){ if(v.fir==fa|......
  • 洛谷2664树上游戏-点分治
    link：https://www.luogu.com.cn/problem/P2664lrb有一棵树，树的每个节点有个颜色。给一个长度为\(n\)的颜色序列，定义\(s(i,j)\)为\(i\)到\(j\)的颜色数量。以及\[sum_i=\sum_{j=1}^ns(i,j)\]现在他想让你求出所有的\(sum_i\)。一个暴力的想法：因为是求和，所以可以拆......
  • cdq分治/逆序对 一点点总结
    cdq分治/逆序对一点点总结归并排序求普通逆序对问题#include<bits/stdc++.h>#defineINinline#defineRregisterintusingnamespacestd;constintN=5e5+5;typedeflonglongll;INintread(){intf=1;charch;while((ch=getchar())<'0'||ch>&#......
  • CDQ分治
    CDQ分治它是一种非常巧妙地方法。用分治的思想处理三维偏序一类的问题：处理的问题如下：模板有$n$个元素，第$i$个元素有$a_i,b_i,c_i$三个属性，设$f(i)$表示满足$a_j\leqa_i$且$b_j\leqb_i$且$c_j\leqc_i$且$j\nei$的\(j\)的数量。对于......
  • CDQ分治学习笔记
    1.简介CDQ分治是一种思想，类似于动态规划，依照原理和写法的不同，大致分为3类：解决与点对相关的问题1D动态规划的优化及转移通过CDQ分治，将一些动态问题转化为静态问题2.解决与点对相关的问题2.1.流程1.找到序列的中点mid2.将所有的点对(i,j)划分为三类a.\(i\lemi......
  • 点分治小记
    点分治是一类高效统计树上路径问题的算法，通过优化递归深度的方法来有效保证时间复杂度。具体操作一般是以下几步：找到当前子树的重心以重心为根计算经过根节点的路径对答案的贡献将根删去并递归处理它的所有子树因为我们每次都以树的重心来作为根节点，递归深度不会超过......
  • P7431【THUPC2017】小 L 的计算题 （牛顿恒等式）（分治NTT）（多项式求逆）题解
    知识点涉及：牛顿恒等式，分治\(NTT\)，多项式求逆。这道题有一个推式子之后分治\(NTT+Ln+Exp\)的做法，不过也有一个不用\(Ln+Exp\)的做法（理论常数要小点，实际差不多）。题解：这道题可以牛顿恒等式直接推出一个非常好写的东西。首先看一下牛顿恒等式的描述：对于\(n\)次多项式\(A(......
  • 点分治
    1概念点分治是树分治的一种，主要用于处理树上路径问题。注意这颗树不需要有根，即这是一颗无根树。下面以例题分析点分治的基本思想。2基本思想首先你需要会的前置知识：树的重心。我们来看这样一道例题：【模板】点分治：给出一颗无根树，有边权，询问树上是否存在距离为\(k\)的......
  • 点分树(动态点分治)学习笔记
    1.定义在点分治的基础上加以变化，构造一颗支持快速修改的重构树，称之为点分树2.算法2.1.思路点分治的核心在于通过树的重心来划分联通块，减少合并层数，从而降低时间复杂度所以，我们可以按分治递归的顺序提出一颗树，易知树高至多为logn具体的说，对于每一个找到的重心，将上一次分治......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99