集训队论文答辩(罗剑桥)

《集训队论文答辩(罗剑桥)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浅谈分块思想在一类数据处理问题中的应用北京市第八十中学罗剑桥本文讨论的范围一类与线性序列和树形结构有关的数据处理问题特征：1.在竞赛中常常出现2.没有专门的数据结构解法或者数据结构解法十分复杂什么是分块思想将一个问题分解为若干个规模较小的子问题优势：1.如果子问题的规模很小，可以设计关于子问题规模的复杂度较高的算法；2.如果子问题的数目很少，可以对每类子问题使用复杂度与整个问题规模有关的算法；3.如果每个子问题内部的元素具有共同的性质，可以使用针对性的算法。线性序列的分块化从第一个元素开始，每连续的S个元素组成一个块。若剩余的元素

2、不足S个，令它们组成一个块。例子：序列元素数目N=7，块的大小S=3.SS线性序列的分块化：性质设N为序列的元素数目，S为块的大小。1.块的数目不超过N/S+1.2.对于任意区间[L,R],可以分解成若干个完整的块以及剩余的不超过2S个元素。如果能在块的层次上概括块内元素的信息，并且可以快速将不同部分的信息合并，就能够快速地得到任意区间的信息了。例一一个N个数的序列。你要执行M次操作。操作有两种类型：1.从第一个数开始，每隔Di个位置的数加上Xi。2.查询区间[Li,Ri]的所有元素的和。1<=N,M<=105.任意时刻所有数均为

3、绝对值不超过109的整数。例一：样例N=5,M=4.7151182ADD:Di=2,Xi=18151283ASK:Li=1,Ri=4answer:8+15+12+8=43ADD:Di=4,Xi=-53151283ASK:Li=1,Ri=4answer:3+15+12+8=38例一：分析将序列分块，令每块的大小为。考虑在块的层次上维护每个块的所有元素的和。首先，预处理的复杂度为O(N)。1.对于询问操作，只需计算出询问区间对应的完整的块与多余的元素的和，时间复杂度为O()。N=10.Ask:Li=3,Ri=8.[3,4,5][1,2

4、,3][7,8,9][10]answer=5+6+7+8=26.2.对于修改操作，复杂度还是很高，怎么办呢?例一：分析这时还是要用到分块的思想。发现，只有当Di比较小的时候修改的元素才会很多。解决方法：1.每个元素和块只考虑Di>=的修改操作的影响。2.用数组记录Di<的每个Di的修改量的和。在查询时枚举每个小于的Di，O(1)计算对答案的影响即可。此算法总的时间复杂度为O(n+m)。例一：分析N=10[3,4,5][1,2,3][7,8,9][10]1.ADDDi=1,Xi=3Sum:12,6,24,10;Di[1~3]:3,0

5、,0.2.ADDDi=4,Xi=1.[4,4,5][1,3,3][7,8,10][10]Sum:13,7,25,10;Di[1~3]:3,0,0.树形结构的分块化树的DFS序：从根开始深度优先遍历，每次遇到一个点进栈或出栈，就把它放到DFS序列的末尾。1234511,21,2,41,2,4,41,2,4,4,51,2,4,4,5,51,2,4,4,5,5,21,2,4,4,5,5,2,31,2,4,4,5,5,2,3,31,2,4,4,5,5,2,3,3,1DFS序的性质1.相邻两个元素之间仅有三种关系：同一个点；父子关系；兄弟关

6、系。2.任意两项之间的连续子序列恰好对应了树上一条路径，路径上除LCA以外的点至少出现1次。3.DFS序列中任意一个区间以及这个区间所有元素的LCA恰好对应树上的一个连通块。将DFS序列分块，每一块与其LCA就对应了树上的一个连通块！例二一个N个点的树。边有权值。你需要计算对于每个点，其他所有点到它的距离中第K小的值。1<=K

7、3]:10,13,18,20distance[4]:5,8,12,18distance[5]:7,10,12,20例二：分析相邻的点之间的答案具有很强的相关性：设点u的答案为ans[u].若存在一条边(u,v)的权值等于c,则点v的答案是ans[u]-c到ans[u]+c之间的数。考虑将树分成若干个规模等于S的连通块。一次计算出一个连通块内所有点的答案。例二：分析对一个连通块，以块内的某个点为根。性质1：无论以块内的哪个点为根，每个点到根的路径上的第一个块内的点是不变的。推论：将所有点按最近块内祖先分类。考虑同类的点u,v，设p为

8、u和v的最近块内祖先。则点u到根的距离<=点v到根的距离<=>点u到p的距离<=点v到p的距离例二：分析例二：分析1.对于一个连通块，首先以一个点r遍历全树，计算出每类点到最近块内祖先(LIA)的距离。并且将每类点按到LIA的距离排序。2.然后，依