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

浅谈分块思想在一类数据处理问题中的应用 北京市第八十中学罗剑桥 本文讨论的范围 一类与线性序列和树形结构有关的数据处理问题特征 1 在竞赛中常常出现2 没有专门的数据结构解法或者数据结构解法十分复杂 什么是分块思想 将一个问题分解为若干个规模较小的子问题优势 1 如果子问题的规模很小 可以设计关于子问题规模的复杂度较高的算法 2 如果子问题的数目很少 可以对每类子问题使用复杂度与整个问题规模有关的算法 3 如果每个子问题内部的元素具有共同的性质 可以使用针对性的算法 线性序列的分块化 从第一个元素开始 每连续的S个元素组成一个块 若剩余的元素不足S个 令它们组成一个块 例子 序列元素数目N 7 块的大小S 3 线性序列的分块化 性质 设N为序列的元素数目 S为块的大小 1 块的数目不超过N S 1 2 对于任意区间 L R 可以分解成若干个完整的块以及剩余的不超过2S个元素 如果能在块的层次上概括块内元素的信息 并且可以快速将不同部分的信息合并 就能够快速地得到任意区间的信息了 例一 一个N个数的序列 你要执行M次操作 操作有两种类型 1 从第一个数开始 每隔Di个位置的数加上Xi 2 查询区间 Li Ri 的所有元素的和 1 N M 105 任意时刻所有数均为绝对值不超过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 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 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序列的末尾 11 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 1 DFS序的性质 1 相邻两个元素之间仅有三种关系 同一个点 父子关系 兄弟关系 2 任意两项之间的连续子序列恰好对应了树上一条路径 路径上除LCA以外的点至少出现1次 3 DFS序列中任意一个区间以及这个区间所有元素的LCA恰好对应树上的一个连通块 将DFS序列分块 每一块与其LCA就对应了树上的一个连通块 例二 一个N个点的树 边有权值 你需要计算对于每个点 其他所有点到它的距离中第K小的值 1 K N 50 000 边的权值为绝对值不超过1 000的整数 例二 样例 1 2 3 4 5 10 3 7 5 N 5 K 2 distance 1 3 8 10 10distance 2 3 5 7 13distance 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为u和v的最近块内祖先 则点u到根的距离点u到p的距离 点v到p的距离 例二 分析 例二 分析 1 对于一个连通块 首先以一个点r遍历全树 计算出每类点到最近块内祖先 LIA 的距离 并且将每类点按到LIA的距离排序 2 然后 依次计算块内每个点的答案 使用二分答案的办法 3 如何统计到点ri距离不超过x的点的数目 以ri为根遍历块内的所有点 算出它们到ri的距离 对每类点二分查找加上LIA到ri的距离以后不超过x的最大的数的位置即可 例二 复杂度分析 连通块的大小为S 第一次遍历和排序的时间复杂度为O NlogN 每个点 二分答案和查找的时间复杂度为O log2N 所以处理一个块的复杂度是O NlogN Slog2N 总的时间复杂度为O N2logN S NSlog2N 如果设S 总的时间复杂度为O N1 5log1 5N 分块与预处理 预处理的条件线性序列上 预处理任意两块之间的信息 每次询问时经过若干次增量得到询问区间的信息 树形结构中 贪心算法标记若干关键点 预处理任意两个关键点之间的信息 每次询问时经过若干次增量得到询问路径的信息 分块与离线算法 与分块与预处理的方法有一定的相似之处 核心 没有必要记录过多信息 在预处理的同时计算询问的答案 具体可参考论文 感谢 感谢中国计算机学会 感谢我的指导老师贾志勇老师长期以来的关心和帮助 感谢集训队的胡伟栋教练和唐文斌教练 特别感谢北京人大附中的范浩强同学的大力帮助和启发 感谢学长黄纪元同学的帮助 感谢我的父母对我的无微不至的关心和照顾 Thankyou Questionsarewelcome 参考文献 ThomasH Cormen CharlesE Leiserson RonaldL Rivest CliffordStein IntroductiontoAlgorithms 2nded 潘金贵等译 机械工业出版社 JonKleinberg EvaTardos AlgorithmDesign 清华大学