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。

相关文章

Python标准库之数据压缩和存档的应用详解

Python标准库之数据压缩和存档的应用详解

《Python标准库之数据压缩和存档的应用详解》在数据处理与存储领域,压缩和存档是提升效率的关键技术,Python标准库提供了一套完整的工具链,下面小编就来和大家简单介绍一下吧... 目录一、核心模块架构与设计哲学二、关键模块深度解析1.tarfile：专业级归档工具2.zipfile：跨平台归档首选3.
阅读更多...
idea的终端(Terminal)cmd的命令换成linux的命令详解

idea的终端(Terminal)cmd的命令换成linux的命令详解

《idea的终端(Terminal)cmd的命令换成linux的命令详解》本文介绍IDEA配置Git的步骤：安装Git、修改终端设置并重启IDEA,强调顺序,作为个人经验分享,希望提供参考并支持脚本之... 目录一编程、设置前二、前置条件三、android设置四、设置后总结一、php设置前二、前置条件
阅读更多...
python中列表应用和扩展性实用详解

python中列表应用和扩展性实用详解

《python中列表应用和扩展性实用详解》文章介绍了Python列表的核心特性：有序数据集合,用[]定义,元素类型可不同,支持迭代、循环、切片,可执行增删改查、排序、推导式及嵌套操作,是常用的数据处理... 目录1、列表定义2、格式3、列表是可迭代对象4、列表的常见操作总结1、列表定义是处理一组有序项目的
阅读更多...
python使用try函数详解

python使用try函数详解

《python使用try函数详解》Pythontry语句用于异常处理,支持捕获特定/多种异常、else/final子句确保资源释放,结合with语句自动清理,可自定义异常及嵌套结构,灵活应对错误场景... 目录try 函数的基本语法捕获特定异常捕获多个异常使用 else 子句使用 finally 子句捕获所
阅读更多...
C++11范围for初始化列表auto decltype详解

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3
阅读更多...
SQL Server 中的 WITH (NOLOCK) 示例详解

SQL Server 中的 WITH (NOLOCK) 示例详解

《SQLServer中的WITH(NOLOCK)示例详解》SQLServer中的WITH(NOLOCK)是一种表提示,等同于READUNCOMMITTED隔离级别,允许查询在不获取共享锁的情... 目录SQL Server 中的 WITH (NOLOCK) 详解一、WITH (NOLOCK) 的本质二、工作
阅读更多...
springboot自定义注解RateLimiter限流注解技术文档详解

springboot自定义注解RateLimiter限流注解技术文档详解

《springboot自定义注解RateLimiter限流注解技术文档详解》文章介绍了限流技术的概念、作用及实现方式,通过SpringAOP拦截方法、缓存存储计数器,结合注解、枚举、异常类等核心组件,... 目录什么是限流系统架构核心组件详解1. 限流注解 (@RateLimiter)2. 限流类型枚举 (
阅读更多...
Java Thread中join方法使用举例详解

Java Thread中join方法使用举例详解

《JavaThread中join方法使用举例详解》JavaThread中join()方法主要是让调用改方法的thread完成run方法里面的东西后,在执行join()方法后面的代码,这篇文章主要介绍... 目录前言1.join()方法的定义和作用2.join()方法的三个重载版本3.join()方法的工作原
阅读更多...
Spring AI使用tool Calling和MCP的示例详解

Spring AI使用tool Calling和MCP的示例详解

《SpringAI使用toolCalling和MCP的示例详解》SpringAI1.0.0.M6引入ToolCalling与MCP协议,提升AI与工具交互的扩展性与标准化,支持信息检索、行动执行等... 目录深入探索 Spring AI聊天接口示例Function CallingMCPSTDIOSSE结束语
阅读更多...
C语言进阶(预处理命令详解)

C语言进阶(预处理命令详解)

《C语言进阶(预处理命令详解)》文章讲解了宏定义规范、头文件包含方式及条件编译应用,强调带参宏需加括号避免计算错误,头文件应声明函数原型以便主函数调用,条件编译通过宏定义控制代码编译,适用于测试与模块... 目录1.宏定义1.1不带参宏1.2带参宏2.头文件的包含2.1头文件中的内容2.2工程结构3.条件编
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2