CDQ分治学习笔记
2023/4/28 1:22:17
本文主要是介绍CDQ分治学习笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
CDQ分治学习笔记
-
CDQ分治学习笔记
- 前言
- CDQ分治思想
-
例题
-
1、翻转对
- 分析
- code
-
1、翻转对
-
P3810 三维偏序(陌上花开)
- 输入格式
- 输出格式
-
样例 #1
- 样例输入 #1
- 样例输出 #1
- 提示
- 分析
- code
前言
之前在gdkoi讲解是有人用 \(CDQ\) 分治A了day1 T3。好像分治FFT要用到,而且其他人都学过了,所以蒟蒻再次恶补一手之前的知识点。
\(CDQ\) 显然是一个人的名字,陈丹琪(NOI2008金牌女选手)。
CDQ分治思想
分治就是分治,“分而治之”的思想。显然CDQ分治不是普通的分治
因为这一类问题又有一个共同特点就是 左区间会对右区间产生贡献 。
我们一般要先求左区间的答案,然后再求左区间对右区间的贡献,最后求右区间的答案。
前置知识:归并排序求逆序对,不会的可以看一下这个。
树状数组 也要用到一点。
例题
1、翻转对
然后我们看一下这一题:翻转对。
题目传送门
题⽬描述
给定⼀个⻓度为 \(n\) 的数组 \(nums\) ,如果 \(i < j\) 且 \(nums[i] > 2 * nums[j]\), 我们就将 \((i , j)\) , 称作⼀个重要翻转对。你需要返回给定数组中的重要翻转对的数量。
数据规模
\(n ≤ 100000\)
分析
很明显这还只是普通的分治
这题用一个简单的归并排序就可以完成,思路差不多,在归并排序求逆序对的代码稍微改一下,把逆序对变成了翻转对⽽已。
code
很明显这是网上抄的,主要是我的力扣账号忘记密码了
class Solution{ private int cnt; public int reversePairs(int[] nums){ int len=nums.length; sort(nums, Arrays.copyOf(nums, len),0,len-1); return cnt; } private void sort(int[] src,int[] dest,int s,int e){ if (s>=e){ return; } int mid=(s+e)>>1; sort(dest,src,s,mid); sort(dest,src,mid+1,e); merge(src,dest,s,mid,e); } private void merge(int[] src,int[] dest,int s,int mid,int e) { int i=s,j=mid+1,k=s; while (i<=mid&&j<=e){ if((long)src[i]>2*((long)src[j])){ cnt+=mid-i+1; j++; } else{ i++; } } i=s; j=mid+1; while(i<=mid&&j<=e){ if (src[i]<=src[j]){ dest[k++]=src[i++]; } else{ dest[k++]=src[j++]; } } while(i<=mid){ dest[k++]=src[i++]; } while(j<=e){ dest[k++]=src[j++]; } } }
P3810 三维偏序(陌上花开)
题目传送门
这道题应该是学过 \(CDQ\) 分治的人都做过了(毕竟是版题,还是紫色的)。
有 $ n $ 个元素,第 $ i $ 个元素有 $ a_i,b_i,c_i $ 三个属性,设 $ f(i) $ 表示满足 $ a_j \leq a_i $ 且 $ b_j \leq b_i $ 且 $ c_j \leq c_i $ 且 $ j \ne i $ 的 \(j\) 的数量。
对于 $ d \in [0, n) $,求 $ f(i) = d $ 的数量。
输入格式
第一行两个整数 $ n,k $,表示元素数量和最大属性值。
接下来 $ n $ 行,每行三个整数 $ a_i ,b_i,c_i $,分别表示三个属性值。
输出格式
$ n $ 行,第 $ d + 1 $ 行表示 $ f(i) = d $ 的 $ i $ 的数量。
样例 #1
样例输入 #1
10 3 3 3 3 2 3 3 2 3 1 3 1 1 3 1 2 1 3 1 1 1 2 1 2 2 1 3 2 1 2 1
样例输出 #1
3 1 3 0 1 0 1 0 0 1
提示
$ 1 \leq n \leq 10^5$,$1 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5 $。
分析
这题是一个三维偏序,我们先看一下把它转换成二维偏序 \(a_j \leq a_i\) \(b_j \leq b_i\) 时怎么做。
我们把 \(a\) 为第一关键字排序,然后用树状数组动态维护维护 \(b_j \leq b_i\) 的个数,时间复杂度:\(O(n\log_2 n)\)
然后考虑本题。
我们还是将 \(a\) 数组为第一关键字,\(b\) 数组为第二关键字,\(c\) 数组为第三关键字排序。
然后用类似于普通分治的方法,将 \([l , r]\) 分成 \([l , mid]\) \([mid + 1 , r]\) 两个区间。两个区间内部按照 \(b\) 数组为第一关键字,\(c\) 数组为第二关键字排序,然后同时遍历两个子区间,利⽤树状数组将左区间对右区间的贡献统计到右区间上。
可能有点难懂,大家可以看一下代码 感性 理解一下,还是比较简单的。
code
#include <bits/stdc++.h> #define fu(x , y , z) for(int x = y ; x <= z ; x ++) #define LL long long #define fd(x , y , z) for(int x = y ; x >= z ; x --) using namespace std; const int N = 2e5 + 5; int n , k , tr[N] , ans[N] , m; struct note { int cnt , a , b , c , ans; }s1[N] , s2[N]; int read () { int val = 0 , fu = 1; char ch = getchar (); while (ch < '0' || ch > '9') { if (ch == '-') fu = -1; ch = getchar (); } while (ch >= '0' && ch <= '9') { val = val * 10 + (ch - '0'); ch = getchar (); } return val * fu; } bool comp1 (note x , note y) { if (x.a != y.a) return x.a < y.a; if (x.b != y.b) return x.b < y.b; if (x.c != y.c) return x.c < y.c; } int lowbit (int x) { return x & (-x); } bool comp2 (note x , note y) { if (x.b != y.b) return x.b < y.b; return x.c < y.c; } void Insert (int val , int sum) { int i = val; while (i <= k) { tr[i] += sum; i += lowbit(i); } } int query (int x) { int sum = 0; while (x) { sum += tr[x]; x -= lowbit (x); } return sum; } void cdq (int l , int r) { if (l == r) return; int mid = l + r >> 1; cdq (l , mid) , cdq (mid + 1 , r); sort (s2 + l , s2 + mid + 1 , comp2); sort (s2 + mid + 1 , s2 + r + 1 , comp2); int j = l; fu (i , mid + 1 , r) { while (s2[i].b >= s2[j].b && j <= mid) { Insert (s2[j].c , s2[j].cnt); j ++; } s2[i].ans += query (s2[i].c); } fu (i , l , j - 1) Insert (s2[i].c , -s2[i].cnt); } int main () { n = read () , k = read (); fu (i , 1 , n) s1[i].a = read () , s1[i].b = read () , s1[i].c = read (); sort (s1 + 1 , s1 + n + 1 , comp1); int t = 0; s1[n + 1] = {0 , 0 , 0 , 0 , 0}; fu (i , 1 , n) { t ++; if (s1[i].a != s1[i + 1].a || s1[i].b != s1[i + 1].b || s1[i].c != s1[i + 1].c) { s2[++ m] = s1[i]; s2[m].cnt = t; t = 0; } } cdq (1 , m); fu (i , 1 , m) ans[s2[i].cnt + s2[i].ans - 1] += s2[i].cnt; fu (i , 0 , n - 1) printf ("%d\n" , ans[i]); return 0; }
这篇关于CDQ分治学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-13WebSocket学习:初学者必读的简单教程
- 2024-10-13第24/26集:TinyConf,ng-贝尔格莱夫,为什么要一直升级呢?
- 2024-10-13全面指南:在 Node 和 TypeScript 中设置 ESLint、Jest 和 Prettier
- 2024-10-12你可以借助 Claude-3 和 Lightning AI,将任何 YT 视频变成内容创作神器。
- 2024-10-12在 NVIDIA AI 的支持下,用 Llama3 在 VSCode 中当代码助手。
- 2024-10-12使用 llama.cpp 对大型语言模型(LLM)进行量化
- 2024-10-12RAG解决方案在Amazon Bedrock中的第八部分:将Amazon Cognito与Amazon EKS集成在一起
- 2024-10-12Databricks 资源包:部署工作流程
- 2024-10-12在这篇文章中,我们如何在 Apache Airflow 中调度 2000+ 个 DBT 模型?
- 2024-10-12亚马逊和谷歌对CI/CD的看法截然不同