转存的 【学习1】基础优化技巧 1 / 基础字符串

**欢迎同学们正式开始省选计划的学习。** 作业每周会布置一个题单。 **作业** 是最为重要的题目。如果既不写题，也不参加模拟比赛，也不学习，相当于没有参加省选计划。请同学做好决心。 **第 1 周任务（12 月 12 日 - 12 月 18 日）** - 请同学们务必重视作业。一定要完成【作业】。如果知识点有遗漏，可以看作业页面下方做学习指导学习。 - 作业：<https://www.luogu.com.cn/training/261084> - 阅读作业页面下方的学习指导。如果有遗漏的知识点，则去学习。 - 12 月 18 日下午 13:00-18:00 模拟比赛，19:00 开始讲评。 - **学习上的问题请随时在 QQ 群提问**。 除此之外，还需要完成：uoj162、loj2742、loj6469 # 学习指导 ## 基础技巧 ~~说是技巧其实是必备技能~~，这一部分比较吃经验的积累，各个算法都有许多变种或者奇怪的应用，这需要选手对算法的本质有深刻的了解。 实际上大部分技巧是基于维护信息的性质的，所以分析透彻性质后，就知道如何去应对了。 所以下面都是常见技巧（好多 $\log$ 相关技巧）。 ### 二分系列 最简单的二分相信大家都会了！二分是对单调性的利用，只要有单调性都可以试试二分！[什么你不会二分？](https://oi-wiki.org/basic/binary/) ### 三分法 对于传统的定义域在实数上的凸函数求最值，可以使用三分法。 三分法对求值利用的效率不高，可以采用黄金分割，每次只用多求一处点值。 在 OI-wiki 中二分法的教程已经教了三分法。 ### 对于凸函数的二分 OI 中一般碰到的是离散的凸函数，其差分是单调的。所以求最值只需要使用二分法。 ### 二分答案与分数规划 二分答案是基于变量与答案之间的单调性，其教程也在 OI-wiki 的二分法中。[分数规划](https://oi-wiki.org/misc/frac-programming/)其实也是二分答案。 同样有基于凸性的二分答案，通过二分其斜率来得到答案。被称作 [wqs二分](https://blog.csdn.net/a_forever_dream/article/details/105581221)。一般可以用来计算“刚好选 $k$ 个的答案最大值”的问题，来对 DP 降维。 ## 分治系列 分治要求维护信息的性质良好。 ### 分治基础 最简单的分治可以做信息拆分与合并。通常要考虑跨越分治中心的信息合并。 [OI-Wiki 很好地阐述了分治是什么](https://oi-wiki.org/basic/divide-and-conquer/)。 推荐 [理解归并排序并用其求逆序对](https://oi-wiki.org/basic/merge-sort/)，这可以帮助你理解分治。 ### 二维分治 多了一维，但是实际上没什么变化。交错地对每一维进行分割即可。[形象的图片](https://blog.csdn.net/bpdwn2017/article/details/82014661) ### 基于时间顺序的分治 如果要求计算分治中心左右两部分信息的合并，这两部分求值的先后顺序并没有要求。如果要求计算较早操作对较晚操作的影响，那么可以通过处理左子树的信息，来计算左子树对右子树的贡献。 其思想类似于操作分块，都是考虑操作的并是否能用简单的信息代替。 这类分治一般被称作 [CDQ 分治](https://oi-wiki.org/misc/cdq-divide/)。 ### 线段树分治 按时间建立线段树，将操作覆盖到线段树上的点，那么处理一个时间的答案就是从叶子到根所有节点信息的并。利用可回退数据结构可以通过在线段树上 dfs 即可得到每个时间的答案。 注意，线段树可以处理强制在线的问题。 [博客1](https://www.cnblogs.com/Miracevin/p/10355084.html )，[博客2](https://www.cnblogs.com/luckyblock/p/13915321.html)。 ### 基于分治中心性质的写法 如果分治中遵循先递归左子树，再递归右子树的法则，那么维护一个指针去“跟踪”分治中心，这个指针移动的距离是 $O(n \log n)$ 的。利用这个性质可以获得优秀的做法。 #### 整体二分 考虑一类能够二分答案的问题，实际上可以将所有的询问一起二分：将所有询问放在分治中，判断分治中心是否大于等于其答案，并将询问分成两部分。因为每个询问在分治树的每一层中至多出现一次，所以复杂度是 $O(Q \log V)$，其中 $V$ 是二分答案的值域。 乍一看和直接二分差不多，但是考虑一类问题：如果不能够快速算出一处点值怎么办？这个时候二分就失效了。但是如果维护的信息相邻处的点值可以快速计算的话，就可以利用分治中心移动的距离不大的性质，这就是 [整体二分](https://oi-wiki.org/misc/parallel-binsearch/)。 #### 分治转移斜率优化 实际上就是整体二分转移点，因为转移点单调，所以有简单的写法。 [Gym 101002 H Jewel Thief](http://codeforces.com/gym/101002/problem/H)， [题解](https://www.cnblogs.com/birchtree/p/12060566.html) 注意到计算的点值和分治中心相关，所以同样可以利用分治中心的性质来快速计算点值。 ### 树分治 树分治一般有点分治和边分治。类似于将区间分成两半，点分治是选择一个点作为分治中心，均匀地将树分成若干份，此时选择重心较好。点分治难度较高，也有许多变种。边分治是选一条边，均匀地讲树分成两部分（因为菊花图的问题，需要将树转换为二叉树再处理）。 [树分治教程](https://oi-wiki.org/graph/tree-divide/) 树分治中还有启发式合并/点分树/动态点分树的问题。 [博客1](https://www.cnblogs.com/zzqsblog/p/6393023.html)，[博客2](https://blog.csdn.net/qq_39972971/article/details/79050767)。 ## 启发式合并 ### 基础应用 对于两个集合的合并，只需要将小的集合插入到大的集合中。对于每个元素，被插入一次其所在的集合大小至少增大一倍，所以至多被插入 $O(\log)$ 次，于是保证了复杂度为 $O(n \log n)$。 [某博客](https://www.cnblogs.com/fusiwei/p/13653748.html)。 ### 基于重链剖分的启发式合并 利用了重链剖分中每个点到根只有 $O(\log n)$ 条不同重链的性质。用奇怪的顺序来获得每个点子树的信息。 [OI-wiki](https://oi-wiki.org/graph/dsu-on-tree/)，[某博客](https://www.cnblogs.com/zwfymqz/p/9683124.html)。 实际上基于重链剖分的启发式合并可以看作将较小的子树中元素一个个插入到大子树的数据结构中。所以其复杂度和启发式合并相关。只是流传的写法表现更加优秀。 ### 基于长链剖分的启发式合并 如果一个点有用的信息只有其深度，那么做启发式合并，相当于删去长度小的链，此时每个点至多被合并一次。复杂度也就从传统启发式合并的带 $\log$ 变成了线性。 [某博客](https://www.cnblogs.com/Alan-Luo/p/10585344.html)。 ## 倍增系列 ### 基础倍增 将带有结合律信息进行二进制拆分，仅用 $O(\log)$ 段信息合并出答案。 [白话说倍增](https://blog.csdn.net/jarjingx/article/details/8180560) [OI-wiki](https://oi-wiki.org/basic/binary-lifting/) [LCA 中的倍增部分](https://oi-wiki.org/graph/lca/) ### RMQ 实际上就是重叠的信息也可以合并。[OI-wiki](https://oi-wiki.org/ds/sparse-table/) ### 倍增答案 类似于二分答案，但是是使用倍增，其实树状数组二分和 LCA 也有类似的思想。 [某博客](https://www.cnblogs.com/cervusy/p/9609213.html)。 ## 离线与扫描线 将操作对一段时间带来的影响看做一条线段，那么可以通过枚举端点来计算每一时刻的答案。 扫描线是非常常用的技巧，墙裂要求学习。 [OI-wiki](https://oi-wiki.org/geometry/scanning/)，[某博客](https://www.cnblogs.com/onioncyc/p/7349552.html)。 ## 分块系列 这里讲一些简单的分块（不是数据结构）。 ### 数论分块 利用 $\lfloor \frac{n}{b} \rfloor$ 只有 $O(\sqrt{n})$ 种取值的性质，用技巧快速枚举。 [某博客](https://www.cnblogs.com/henry-1202/p/10121854.html) ### 操作分块 当信息合并复杂度较高的时候，可以考虑定期合并，并且额外考虑零散元素的贡献。 [用题目来理解操作分块](https://www.cnblogs.com/imakf/p/13768011.html) ### 根号分治 [其实就是对大的集合和小的集合分别使用不同的算法](https://www.cnblogs.com/Hs-black/p/12693974.html) ## 字符串 本周需要大家掌握的知识点有： 1. Trie 树（其实这个东西非常基础，大家应该都会吧） 2. kmp（这个应当熟练掌握，2021 年 NOIP 都有考到） 如果以上知识点没有学过，可以到 [OIwiki](https://oi-wiki.org/string/) 上进行学习（如果会这个算法但几乎完全不了解一些实际使用的小 trick，也可以上 OIwiki 翻阅一下，了解一些实用小 trick）。我本人学习这些字符串算法的时候都是在 OIwiki 上学的，因此感觉只要好好阅读 OIwiki 上的内容就足够学懂了。当然下面也会推荐一些博客给大家，大家可以视自身情况选择性的阅读（持续更新）： [yyb 的字符串合集](https://www.cnblogs.com/cjyyb/p/10185074.html)