2025国庆集训得reminiscences

本文章用来记录本人的一次集训学习，记叙的内容主要有集训的主要知识点，一些知识点若有新的感悟也会写下来，以及集训的整体感受。

没啥好讲的。

开始正式上课！

教室里的人要比我想象中少得多。

上午讲了一些较基础的算法，包括二分，分治，贪心和搜索（实际上一上午绝大部分时间都在讲搜索）。

搜索本身其实没啥难点，主要还是得考虑怎么优化、剪枝。尽可能多的去找一些性质，能剪掉就都剪掉，当然剪枝后的时间复杂度是非常玄学的，具体得看能剪掉多少冗余。这里有一道很恶心的练剪枝的题，可以来逝一逝。（被恶心了1.5 h）

回温了一下折半搜索，是指将要搜索的区间分成两半，每一部分分别进行搜索，最后将两部分搜索得到的结果合起来，就是最终答案。这样时间复杂度是可以直接开一个方的，如原来 $n=40$ 时时间复杂度为 $O(2^n)$ ，即 $2^{40}$ ，显然过不了，但折半搜索可以把时间复杂度砍到 $O(2^{\frac{n}{2}})$ ，即 $2^{20}$ ，就可以被接受了，但常数可能会大一点点。所以，能用搜索但数据范围略微超出我们能接受的范围，就可以考虑折半。（自己切掉一道折半的绿，开心）

贪心是一个很奇妙的东西，它很需要一些灵光一现的idea。我的建议是要大胆去想，去猜，猜出来一个就得好好想想它的正确性（可能需要很多对拍），觉得没问题就大胆去写，俗话说得好，OI是一门感性的学科！

整堂课体感还挺舒服，没有很难，就是思考与互动的时间给的很少（可以说是几乎没有）。

接下来，下午就开讲万恶的输俱劫狗了！

俗话说的好，数据结构千千万，Segment Tree占一半（其实是我自己编的），较为快速地过了一遍ST表和LCA后就大篇幅开始讲线段树了。

P.S. ：那么为什么不讲Fenwick Tree呢？我猜测是因为太基础了xxs都会（其实我已经忘了），以及除了代码比线段树好写外其他方面都打不过线段树。

LCA还是挺值得讲的，除了xxs都会的倍增求LCA外，还有用欧拉序求LCA，树剖求LCA（不过到底是谁在写树剖），应该还有其他方法，但目前来看学习的必要性不大。

倍增求LCA妇孺皆知，家喻户晓，利用倍增的思路往上跳 $2^k$ 下，很明显预处理的时间复杂度是 $O(n \log n)$ 的，单次询问是 $O( \log n)$ 的，很大的一个优势是好写。

欧拉序求LCA的方法是先通过 dfs 一遍得到整棵树的欧拉序，得出欧拉序中每个节点的深度构成的序列，再将LCA转化成该序列上的RMQ问题。具体来说，想要知道两个点 $x,y$ 的LCA，就可以在欧拉序上找到这两个点（出现两次取任意一次即可），求出深度序列上区间 $[x,y]$ 的最小值所对应的点便是两者的LCA，原理其实很好理解，这是欧拉序的神奇性质，从 $x$ 走到 $y$ 的过程中一定会经过 $LCA(x,y)$，但不会经过 $LCA(x,y)$ 的祖先。很明显，区间最小值可以用ST表维护，预处理时间复杂度为 $O(n \log n)$ ，单次询问时间复杂度为 $O(1)$ 。很明显要比传统的倍增要快，代码的话理解了写起来就不难。

还有一种就是树剖求LCA。用的是树剖中的重链剖分，我们可以通过比较两个点所在链的链顶高低，让链顶更靠下的蹦到上一条链去，等到两点到了同一条链上就取更靠下的点做LCA。很直观吧？预处理时间复杂度就是树剖的 $O(n)$ ，单次询问时间复杂度为 $O(\log n)$ ，但比倍增的常数小，通常跑不满。不过正常情况下谁会写呢？

此为三种求LCA的做法，各有优劣，反正是学到了。

接下来就是人见人爱的线段树了！

众所周知，线段树是一种最基础且应用最为广泛的数据结构。它可以快速地维护序列上的某些信息。且线段树的区间操作有一个非常重要的思想是懒标记，将线段树的标记留在这层并标一个tag，到要用的时候再下传到儿子。

一种操作想要用传统的线段树维护，需要维护区间信息，且区间信息能够快速合并。若是进行区间操作，需要考虑的事情更多：

所以用线段树的时候就需要考虑怎么去做这些事。