2015年集训队论文答辩(罗剑桥)演示文稿【荐】.pptVIP

例一：样例 N = 5, M = 4. 7 15 11 8 2 ADD: Di = 2, Xi = 1 8 15 12 8 3 ASK: Li = 1, Ri = 4 answer: 8 + 15 + 12 + 8 = 43 ADD: Di = 4, Xi = -5 3 15 12 8 3 ASK: Li = 1, Ri = 4 answer: 3 + 15 + 12 + 8 = 38 例一：分析 这时还是要用到分块的思想。 发现，只有当 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.ADD Di = 1, Xi = 3 Sum: 12, 6, 24, 10; Di[1~3]: 3, 0, 0. 2.ADD Di = 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序的性质 例二 例二：样例 例二：分析 例二：分析 例二：分析 例二：分析 例二：复杂度分析 感谢 感谢中国计算机学会。 感谢我的指导老师贾志勇老师长期以来的关心和帮助。 感谢集训队的胡伟栋教练和唐文斌教练。 特别感谢北京人大附中的范浩强同学的大力帮助和启发。 感谢学长黄纪元同学的帮助。 感谢我的父母对我的无微不至的关心和照顾。 Thank you. Questions are welcome~ 参考文献 浅谈分块思想 在一类数据处理问题中的应用 北京市第八十中学 罗剑桥 本文讨论的范围 一类与线性序列和树形结构有关的数据处理问题 特征： 1. 在竞赛中常常出现 2. 没有专门的数据结构解法 或者数据结构解法十分复杂 什么是分块思想 将一个问题分解为若干个规模较小的子问题 优势： 1. 如果子问题的规模很小，可以设计关于子问题规模的 复杂度较高的算法； 2. 如果子问题的数目很少，可以对每类子问题使用复杂 度与整个问题规模有关的算法； 3. 如果每个子问题内部的元素具有共同的性质，可以使 用针对性的算法。 线性序列的分块化 从第一个元素开始，每连续的 S 个元素组成一个块。若剩余的元素不足 S 个，令它们组成一个块。 例子：序列元素数目 N = 7，块的大小S = 3. S S 线性序列的分块化：性质 设 N 为序列的元素数目，S 为块的大小。 1. 块的数目不超过 N / S + 1. 2. 对于任意区间 [L, R], 可以分解成若干个完整的 块以及剩余的不超过 2S 个元素。 如果能在块的层次上概括块内元素的信息，并且 可以快速将不同部分的信息合并，就能够快速地得到任意区间的信息了。 例一 一个 N 个数的序列。你要执行 M 次操作。 操作有两种类型： 1. 从第一个数开始，每隔 Di 个位置的数加上 Xi。 2. 查询区间 [Li, Ri] 的所有元素的和。 1 = N, M = 105. 任意时刻所有数均为绝对值不超过109的整数。 例一：分析 将序列分块，令每块的大小为 。 考虑在块的层次上维护每个块的所有元素的和。 首先，预处理的复杂度为 O(N) 。 1.对于询问操作，只需计算出询问区间对应的完整的块与多余的元素的和，时间复杂度为 O( )。 N = 10. Ask: Li = 3, Ri = 8. [3, 4, 5] [1, 2, 3] [7, 8, 9] [10] answer = 5 + 6 + 7 + 8 = 26. 2.对于修改操作，复杂度还是很高，怎么办呢? 树形结构的分块化 树的 DFS 序： 从根开始深度优先遍历，每次遇到一个点进栈或出栈，就把它放到 DFS 序列的末尾。 1 2 3 4 5 1 1, 2 1, 2, 4 1, 2, 4, 4 1, 2, 4, 4, 5 1, 2, 4, 4, 5, 5 1, 2, 4, 4, 5, 5, 2 1, 2, 4, 4, 5, 5, 2, 3 1, 2, 4, 4, 5, 5, 2, 3, 3 1, 2, 4, 4, 5,