CDQ分治详解，一维、二维、三维偏序

2024-02-27 05:52
文章标签 详解 三维 分治 二维 一维 cdq 偏序

本文主要是介绍CDQ分治详解，一维、二维、三维偏序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

    • 零、偏序关系
    • 一、一维偏序
    • 二、二维偏序
    • 三、三维偏序(CDQ)
      • 3.1CDQ分治
      • 3.2CDQ分治解决三维偏序的流程
    • 四、OJ练习
      • 4.1三维偏序模板题
        • 4.1.1原题链接
        • 4.1.2AC代码
      • 4.2老C的任务
        • 4.2.1原题链接
        • 4.2.2解题思路
        • 4.2.3AC代码
      • 4.3动态逆序对
        • 4.3.1原题链接
        • 4.3.2解题思路
        • 4.3.3AC代码

零、偏序关系

设R是集合A上的一个关系，如果R是自反的、反对称的、传递的，则称R为一个偏序关系(或称部分序关系、半序关系)。

通常，将偏序关系R写做≤，读做“小于或等于”。
对于一维、二维、三维我们有着不同的处理手段。

一、一维偏序

给你一个长度为n的序列，求出每个元素在序列中比其小的元素数目。

这是最为简单的偏序问题，处理方法也很简单：将原序列升序排序，当然如果有重复元素，我们要适当进行去重处理。

二、二维偏序

有n个元素，第i个元素有ai,bi两个属性,求出每个下标i，满足j != i，aj ≤ ai且bj ≤ bi的j的数目

基本思路：按照第一维排序，然后计算前一半对于后一半的影响。

基于这样的思路，我们有两种做法：

F1归并排序

和归并排序计算逆序对很像

  • 先按照ai进行排序，然后对bi进行归并排序
  • 归并排序时，序列被划分为[l, mid]和[mid + 1, r]两个序列
  • 虽然按照bi进行归并排序会导致ai的顺序混乱，但是两个序列仍然满足左边序列的ai不大于右边序列的ai
  • 当我们双指针合并两个序列时，当要存放右边序列的元素时，可以根据左边指针和左边界的相对位置计算其贡献
  • 时间复杂度O(nlogn)

F2树状数组

  • 先按照ai进行排序，然后开树状数组维护当前遍历位置之前值小于等于bi的元素数目
  • 遍历按照第一维排序后的序列，ans[i] = query(b[i])
  • 时间复杂度O(nlogn)

代码十分简单，这里不再给出

三、三维偏序(CDQ)

有n个元素，第 i个元素有ai，bi，ci三个属性，设 f(i) 表示满足 aj ≤ ai且 bj ≤ bi 且 cj ≤ ci且 j != i 的 j 的数量。

对于d ∈ [0, n) ，求 f(i) = d 的i数量。

虽然问题变成了三维偏序，但是基本思路还是按照某个维度排序，然后计算前面对后面的影响，通过这样的策略，达到将问题降维的效果。

3.1CDQ分治

CDQ分治是以曾经的IOI选手陈丹琦命名的一种离线的分治算法，主要用于解决偏序问题。

3.2CDQ分治解决三维偏序的流程

同样有归并排序和树状数组两种做法，我们这里给出树状数组做法。

  • 先按一维属性排序和去重
    1.假设三维分别是x，y，z，先按x排序。
    2.然后去掉重复元素，记录每个元素出现的次数cnt
  • CDQ分治：类似归并排序的思想，先按第一维属性划分为前一半和后一半，回归时计算前一半对后一半的影响
  1. 分治后每次将前一半、后一半分别按y排序。虽然现在x的顺序被打乱了，但是前一半的x还是都小于后一半的，所以只计算前一半对后一半的偏序关系，是不会受到x影响的。
  2. 用双指针 i,j来维护前一半和后一半，每次将j后移一位时，若y[i] <= y[j]，则不断后移i，并不断将z[i]加入树状数组。然后再查询树状数组中有多少数<=z[j]，即<= e[j]的偏序数量。
  3. 最后要清空树状数组。
    时间复杂度O(nlog^2n)

四、OJ练习

4.1三维偏序模板题

4.1.1原题链接

P3810 【模板】三维偏序（陌上花开） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

4.1.2AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N = 100005, K = 200005;
int n, k, tot = 0;
int ans[N], tr[K];struct node
{int a, b, c, s = 1, res;bool operator==(const node &x) const{return a == x.a && b == x.b && c == x.c;}
} nodes[N];bool cmpa(const node &x, const node &y)
{if (x.a != y.a)return x.a < y.a;if (x.b != y.b)return x.b < y.b;return x.c < y.c;
}
bool cmpb(const node &x, const node &y)
{if (x.b != y.b)return x.b < y.b;return x.c < y.c;
}
void modify(int x, int v)
{for (; x <= k; x += (x & -x))tr[x] += v;
}
int query(int x)
{int res = 0;for (; x > 0; x &= (x - 1))res += tr[x];return res;
}
void CDQ(int l, int r)
{if (l == r)return;int mid = (l + r) >> 1;CDQ(l, mid), CDQ(mid + 1, r);sort(nodes + l, nodes + mid + 1, cmpb), sort(nodes + mid + 1, nodes + r + 1, cmpb);int i = l, j = mid + 1;for (; j <= r; j++){for (; i <= mid && nodes[i].b <= nodes[j].b; i++)modify(nodes[i].c, nodes[i].s);nodes[j].res += query(nodes[j].c);}for (j = l; j < i; j++)modify(nodes[j].c, -nodes[j].s);
}
int main()
{freopen("in.txt", "r", stdin);ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> k;for (int i = 1; i <= n; i++)cin >> nodes[i].a >> nodes[i].b >> nodes[i].c;sort(nodes + 1, nodes + n + 1, cmpa);for (int i = 1; i <= n; i++){if (nodes[i] == nodes[tot])nodes[tot].s++;elsenodes[++tot] = nodes[i];}CDQ(1, tot);for (int i = 1; i <= tot; i++)ans[nodes[i].s + nodes[i].res - 1] += nodes[i].s;for (int i = 0; i < n; i++)cout << ans[i] << '\n';return 0;
}

4.2老C的任务

4.2.1原题链接

[P3755 CQOI2017] 老C的任务 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

4.2.2解题思路

对于每个询问，我们要计算出矩形区域内的基站数目，数据范围允许的情况下自然可以用二维前缀和进行快速计算

但是我们发现二位前缀和维护的无非是两个维度都不超过自己的点的数目，这样我们可以用二维偏序解法计算出每个点其左下角的点的数目，这样相当于变相计算出了二维前缀和

那么对于x1，y1，x2，y2的查询，显然有ans = pre[x2][y2] - pre[x2][y1 - 1] - pre[x1 - 1][y2] + pre[x1 - 1][y1 - 1]

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

那么是否可以转化为三维偏序问题求解呢？

对于查询的点，我们都给其增加一个维度，然后加入序列，这样CDQ求出的查询点的二位前缀和，我们给要减去前缀和的点一个-1，加上的给一个1，方便后序计算答案

4.2.3AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e5 + 10;
struct node
{int a, b, c, s, id, sign;long long res;bool operator==(const node &x) const{return a == x.a && b == x.b && c == x.c;}
} nodes[N];
int n, m;
long long ans[N], tr = 0;
bool cmpa(const node &x, const node &y)
{if (x.a != y.a)return x.a < y.a;if (x.b != y.b)return x.b < y.b;return x.c < y.c;
}
bool cmpb(const node &x, const node &y)
{if (x.b != y.b)return x.b < y.b;return x.c < y.c;
}
void CDQ(int l, int r)
{if (l == r)return;int mid = (l + r) >> 1;CDQ(l, mid), CDQ(mid + 1, r);sort(nodes + l, nodes + mid + 1, cmpb), sort(nodes + mid + 1, nodes + r + 1, cmpb);int i = l, j = mid + 1;for (; j <= r; j++){for (; i <= mid && nodes[i].b <= nodes[j].b; i++)tr += !nodes[i].c * nodes[i].s;if (nodes[j].c)nodes[j].res += tr;}for (j = l; j < i; j++)tr -= !nodes[j].c * nodes[j].s;
}
int main()
{// freopen("in.txt", "r", stdin);ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++)cin >> nodes[i].a >> nodes[i].b >> nodes[i].s;for (int i = 1, a1, b1, a2, b2; i <= m; i++){cin >> a1 >> b1 >> a2 >> b2;nodes[++n] = {a2, b2, 1, 0, i, 1};nodes[++n] = {a1 - 1, b1 - 1, 1, 0, i, 1};nodes[++n] = {a2, b1 - 1, 1, 0, i, -1};nodes[++n] = {a1 - 1, b2, 1, 0, i, -1};}sort(nodes + 1, nodes + 1 + n, cmpa);CDQ(1, n);for (int i = 1; i <= n; i++)if (nodes[i].c)ans[nodes[i].id] += nodes[i].res * nodes[i].sign;for (int i = 1; i <= m; i++)cout << ans[i] << '\n';return 0;
}

4.3动态逆序对

4.3.1原题链接

[P3157 CQOI2011] 动态逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

4.3.2解题思路

该问题和普通逆序对相比只多了一个维度——时间

那么我们将原序列元素的删除时间设置为0，删除元素删除时间从1到m依次增加，这样一来我们要求的点对即为：

ti < tj, pi < pj, vi > vj或者ti < tj, pi > pj, vi < vj

这样CDQ中我们要跑两次双指针，清空两次树状数组

对于删除元素修改树状数组的贡献我们设置为-1，原序列为1

这样就巧妙的解决了问题

4.3.3AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
const int N = 1e5 + 10, M = 5e4 + 10;
struct node
{int t, p, v, k;
} nodes[N + M];
int ans[M], tr[N];
int mp[N], n, m, tot = 0;
int query(int x)
{long long res = 0;for (; x > 0; x &= (x - 1))res += tr[x];return res;
}
void modify(int x, int v)
{for (; x <= n; x += (x & -x))tr[x] += v;
}
bool cmp(const node &x, const node &y)
{return x.p < y.p;
}
void CDQ(int l, int r)
{if (l == r)return;int mid = (l + r) >> 1;CDQ(l, mid), CDQ(mid + 1, r);sort(nodes + l, nodes + mid + 1, cmp), sort(nodes + mid + 1, nodes + 1 + r, cmp);int i = l, j = mid + 1;for (; j <= r; ++j){for (; i <= mid && nodes[i].p < nodes[j].p; ++i)modify(nodes[i].v, nodes[i].k);ans[nodes[j].t] += (query(n) - query(nodes[j].v)) * nodes[j].k;}for (j = l; j < i; j++)modify(nodes[j].v, -nodes[j].k);i = mid, j = r;for (; j > mid; --j){for (; i >= l && nodes[i].p > nodes[j].p; --i)modify(nodes[i].v, nodes[i].k);ans[nodes[j].t] += query(nodes[j].v - 1) * nodes[j].k;}for (j = mid; j > i; j--)modify(nodes[j].v, -nodes[j].k);
}
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);cin >> n >> m;for (int i = 1, x; i <= n; ++i)cin >> x, mp[x] = i, nodes[++tot] = {0, i, x, 1};for (int i = 1, x; i <= m; ++i)cin >> x, nodes[++tot] = {i, mp[x], x, -1};CDQ(1, tot); // CDQ分治for (int i = 1; i <= m; ++i)ans[i] += ans[i - 1]; // 前缀和for (int i = 0; i < m; ++i)cout << ans[i] << '\n';return 0;
}

这篇关于CDQ分治详解，一维、二维、三维偏序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/751395。

相关文章

Java中注解与元数据示例详解

Java中注解与元数据示例详解

《Java中注解与元数据示例详解》Java注解和元数据是编程中重要的概念,用于描述程序元素的属性和用途,：本文主要介绍Java中注解与元数据的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参... 目录一、引言二、元数据的概念2.1 定义2.2 作用三、Java 注解的基础3.1 注解的定义3.2 内
阅读更多...
JavaScript中的isTrusted属性及其应用场景详解

JavaScript中的isTrusted属性及其应用场景详解

《JavaScript中的isTrusted属性及其应用场景详解》在现代Web开发中,JavaScript是构建交互式应用的核心语言,随着前端技术的不断发展,开发者需要处理越来越多的复杂场景,例如事件... 目录引言一、问题背景二、isTrusted 属性的来源与作用1. isTrusted 的定义2. 为
阅读更多...
使用Python实现操作mongodb详解

使用Python实现操作mongodb详解

《使用Python实现操作mongodb详解》这篇文章主要为大家详细介绍了使用Python实现操作mongodb的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、示例二、常用指令三、遇到的问题一、示例from pymongo import MongoClientf
阅读更多...
一文详解Python中数据清洗与处理的常用方法

一文详解Python中数据清洗与处理的常用方法

《一文详解Python中数据清洗与处理的常用方法》在数据处理与分析过程中,缺失值、重复值、异常值等问题是常见的挑战,本文总结了多种数据清洗与处理方法,文中的示例代码简洁易懂,有需要的小伙伴可以参考下... 目录缺失值处理重复值处理异常值处理数据类型转换文本清洗数据分组统计数据分箱数据标准化在数据处理与分析过
阅读更多...
详解如何在React中执行条件渲染

详解如何在React中执行条件渲染

《详解如何在React中执行条件渲染》在现代Web开发中,React作为一种流行的JavaScript库,为开发者提供了一种高效构建用户界面的方式,条件渲染是React中的一个关键概念,本文将深入探讨... 目录引言什么是条件渲染？基础示例使用逻辑与运算符（&&）使用条件语句列表中的条件渲染总结引言在现代
阅读更多...
详解Vue如何使用xlsx库导出Excel文件

详解Vue如何使用xlsx库导出Excel文件

《详解Vue如何使用xlsx库导出Excel文件》第三方库xlsx提供了强大的功能来处理Excel文件,它可以简化导出Excel文件这个过程,本文将为大家详细介绍一下它的具体使用,需要的小伙伴可以了解... 目录1. 安装依赖2. 创建vue组件3. 解释代码在Vue.js项目中导出Excel文件，使用第三
阅读更多...
SQL注入漏洞扫描之sqlmap详解

SQL注入漏洞扫描之sqlmap详解

《SQL注入漏洞扫描之sqlmap详解》SQLMap是一款自动执行SQL注入的审计工具,支持多种SQL注入技术,包括布尔型盲注、时间型盲注、报错型注入、联合查询注入和堆叠查询注入... 目录what支持类型how---less-1为例1.检测网站是否存在sql注入漏洞的注入点2.列举可用数据库3.列举数据库
阅读更多...
Linux之软件包管理器yum详解

Linux之软件包管理器yum详解

《Linux之软件包管理器yum详解》文章介绍了现代类Unix操作系统中软件包管理和包存储库的工作原理,以及如何使用包管理器如yum来安装、更新和卸载软件,文章还介绍了如何配置yum源,更新系统软件包... 目录软件包yumyum语法yum常用命令yum源配置文件介绍更新yum源查看已经安装软件的方法总结软
阅读更多...
java图像识别工具类(ImageRecognitionUtils)使用实例详解

java图像识别工具类(ImageRecognitionUtils)使用实例详解

《java图像识别工具类(ImageRecognitionUtils)使用实例详解》：本文主要介绍如何在Java中使用OpenCV进行图像识别,包括图像加载、预处理、分类、人脸检测和特征提取等步骤... 目录前言1. 图像识别的背景与作用2. 设计目标3. 项目依赖4. 设计与实现 ImageRecogni
阅读更多...
Java访问修饰符public、private、protected及默认访问权限详解

Java访问修饰符public、private、protected及默认访问权限详解

《Java访问修饰符public、private、protected及默认访问权限详解》：本文主要介绍Java访问修饰符public、private、protected及默认访问权限的相关资料,每... 目录前言1. public 访问修饰符特点：示例：适用场景：2. private 访问修饰符特点：示例：
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2