离散化与差分结合应用例题精讲

一、离散化是什么1.为什么用离散化引入当题目给我们几个区间涂色总长为20亿要求我们统计最后有颜色的区域。聪明的我们立刻就想建立一个数组每接收到一个区间就遍历该区间打上标记。最后遍历整个数组统计带有标记的元素个数太暴力了吧。但是聪明的我们又很快发现数组没办法容纳20亿的数据会爆数组。既然如此那我们该怎么办呢2.离散化思考过程于是我们开始思考首先给我们的区间只占这20亿数据的一小部分也就是说存在大量的数据是没有用的。其次给我们的区间可能会有重叠的情况比如[2,6]和[3,9]这种情况我们必须想办法去掉重复的数据。针对这两种情况我们以给出{[2,6],[3,9],[11,16],[11,18]}为例从2到18是不是很大假装很大方便讲解题目很可能是1-999999里面是不是有重叠区间这时候我们大脑中开始出现一个图我们会想该怎么去重呢首先看出[2,6][3,9]有重叠部分[11,16][11,18]有重叠部分这个时候我们可以把每个相邻的点看成一个小片段即[2,3][3,6][6,9][9,11][11,16][16,18]然后再看看每个小片段是否包含在大片段里面我们会发现只有[9,11]不在那么把这个小片段去掉然后就会发现剩下的小片段是不重叠的那么我们只需要计小片段的长度之和就可以了。这个时候我们已经解决了区间重叠带来的计数不方便的问题。3.计算机中离散化的过程以上的操作相当于什么呢相当于我们把所有的坐标拿过来排序去重就会得到这么一个序列。{2,3,6,9,11,16,18}每组相邻的元素就构成上一段的小片段这时候再结合下标看就如下图。我们可以有原来的20亿长数组需要下标对应变成了7元素长数组。原来的索引变成了元素我们就这样建立了一个映射关系从2 3 6....18映射到了0 1 2 3....6发现了没有此时我们又解决了数据过大的问题。这个时候我们怎么统计先判断在不在覆盖区间内怎么判断呢把原来给出的{[2,6],[3,9],[11,16],[11,18]}记录下来然后遍历新数组的每组相邻元素[l,r]是否被包含在这些区间内部就可以然后怎么求长度呢这里我们已经解决了两个难题了是不是可以直接通过累加新数组每组相邻元素的差1就可以得到最后的答案了但这时候如果给出区间为n个切成小区间后为m个每个小区间都要遍历一遍所有大区间看看是否在大区间内还要对每个小区间都进行一遍这样的操作最后的时间复杂度为一旦给出数据过多就会超时。4.差分的应用那么该怎么优化我们再回到20亿数组去我们用20亿数组的时候回怎么统计这些小片段的长度有没有想到差分但是没有20亿的数组我们这时候可不可以在新数组里差分呢当然可以首先要明确原理依然是统计每组相邻包含在覆盖范围内的差值即每个小片段的长度那么我们第一步还是看看小区间是不是被覆盖就需要根据给出的大区间所以对大区间差分我们构造差分数组这个差分数组是和新数组对应的。对每一组大区间[l,r]然后进行标准差分操作。注意是对l,r在新数组的索引cha[indexof[l]]; cha[indexof[r]]--;这个时候[l,r]的其余已经打上标记了注意这里打上标记和对20亿数组[l,r]区间每个元素打上标记的含义不同而是对新数组的[l,r]区间打上标记这也是映射解决数组超大无法遍历打标记的根本优势所在。例如对给出的[2,6]我们是对差分数组的2,6对应新数组下标处就是0,2处打标记。差分数组打完标记后前缀和统计注意因为是依据大区间打标记的所以依然存在重叠现象所以不能直接统计和而是只要这个位置前缀大于0就说明被覆盖过所以这个小片段在覆盖范围内就对这个小区间求和即相邻两项的差值最后得出答案。这就是离散化和差分的结合应用——对超大数组的某些区间的覆盖问题。其中解决两个问题的过程就是离散化把原来极度分散的有用数据聚集起来得到一个新的映射从而去掉大量无用数据并且防止重复。其中离散化的排序去重部分的代码实现如下Collections.sort(list); //排序 ListInteger tempnew ArrayListInteger(); //暂存新数组 for(int i0;ilist.size();i) { if(i0 || !list.get(i).equals(list.get(i-1))) //第一个数不重复一定会存进去 { temp.add(list.get(i)); } } listtemp;最后对离散化后的数据进行高效统计的差分过程如下int lenlist.size(); //离散化后的长度 int []chanew int[len1]; //去重后长度len1 for(int i0;in;i) { int lCollections.binarySearch(list,op[i][0]); //获取下标 int rCollections.binarySearch(list,op[i][1]); cha[l]; cha[r]--; } int sum0; int ans0; for(int i0;ilen;i) { sumcha[i]; if(sum0) //只要大于0就说明被覆盖了 { anslist.get(i1)-list.get(i); } }5.思路总结1.数组太大没法直接暴力2.发现排序去重可以缩小数组离散化3.想怎么求4.发现对大区间差分然后前缀和只要大于1就是被覆盖的规律5.利用4规律检测覆盖情况再求小区间大小二、例题P1496 火烧赤壁 - 洛谷这个例题是离散化差分的经典例题思路和上面思路完全相同。import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scnew Scanner(System.in); int nsc.nextInt(); ListInteger listnew ArrayListInteger(); int [][]opnew int[n][2]; //保存每个区间 for(int i0;in;i) { int lsc.nextInt(); int rsc.nextInt(); op[i][0]l; op[i][1]r; list.add(l); list.add(r); } Collections.sort(list); //排序 ListInteger tempnew ArrayListInteger(); for(int i0;ilist.size();i) { if(i0 || !list.get(i).equals(list.get(i-1))) //第一个数不会重复一定会存进去 { temp.add(list.get(i)); } } listtemp; int lenlist.size(); //离散化后的长度 int []chanew int[len1]; //去重后长度len1 for(int i0;in;i) { int lCollections.binarySearch(list,op[i][0]); //获取下标 int rCollections.binarySearch(list,op[i][1]); cha[l]; cha[r]--; } int sum0; int ans0; for(int i0;ilen;i) { sumcha[i]; if(sum0) { anslist.get(i1)-list.get(i); } } System.out.println(ans); } }离散化我个人感觉还是比较难的两天晚上都在思考离散化的过程但现在也不是很理解接下来我可能还会做两个有关离散化的例题加深一下对离散化的认识。感谢大家观看如有不足敬请指正。