2024暑假总结1

Data Structure 总结：

Day1（6.27）

今天主要看了平衡树，线段树为主题的题。通常来说，涉及到翻转一个区间，那就肯定要用平衡树，平衡树的话，推荐Splay，比较好写，缺点就是常数较大。对于平衡树和线段树，最重要的点就是想每个点需要维护哪些值，对于两个区间，怎么去合并这些值。比如要求一个大问题的答案，可以先把这个值拆成另外两个小的值，然后可以再继续拆下去，知道这个值可以单独维护。还有，板子一定要记熟悉，不要等到考场上再去调板子。

Day2（6.28）

今天主要看了扫描线的主题。扫描线最基础的题就是静态二维数点，将所有询问按一个轴离线下来，然后扫一遍处理答案，对于这类静态的数点很有用，它可以将 \(\log^2\) 的树套树优化为一个 \(\log\)，且代码少了很多。而在实际做题中，就要考虑怎么把询问转化为二维数点。一个最常见的转化是“反演”，比如将考虑询问包含了哪些元素转化为一个元素对哪些询问有贡献。另一种转化是容斥，最常见的就是将至少包含一个变为总数减去不包含任意一个。在实际写题中，要注意代码的常数问题。

Day3（6.29）

今天主要看了扫描线更高级的应用。第一类问题是区间子区间问题，这种问题一般涉及到区间历史值，做法就是将询问离线然后用扫描线扫，询问一个区间的历史信息。这类问题的难点是如何维护区间历史信息，应考虑好两个区间标记叠加时哪个标记有贡献，再合并标记，标记下放时同理。第二类问题是维护一个序列的时间问题，通常做法是将维护序列转化为维护时间。用一个数据结构维护时间序列，然后用差分+扫描线来做。要注意的是，如果普通的线段树，平衡树做不了的话，可以考虑根号算法，比如分块。

Day4（6.30）

今天主要看了分块+莫队。其中莫队有很多种形式的莫队，比如普通莫队，回滚莫队，子树莫队等。但是这些莫队的本质还是一样的，即有很多个集合，两个集合间的距离是这两个距离的对称差，你需要求一条路径经过每一个集合，使得这条路径的总距离尽可能小。对于序列上的莫队，这个长度是 \(\mathcal{O}(n\sqrt m)\)。这也就相当于维护一个集合，支持插入，删除，查询一个值。如果集合不太好支持删除操作的话，可以考虑回滚莫队。莫队是一个常用的方法，因为它可以用 \(\mathcal{O}(n\sqrt n)\) 的时间复杂度来处理两个自由度。

Day5（7.1）

今天主要讲了一些根号算法，比如子树补的莫队，半平面莫队。还重点讲了树上分块。具体做法为先将树分成几个大小为 \(\mathcal{O}(\sqrt n)\) 的块，然后将这些块中通向其它块的点构建虚树，这样每个块最多有 \(2\) 的度数。然后再具体做题中，一般需要维护每个块两个出点间的路径的信息。另外还讲了半平面莫队，半平面莫队做法是先随机撒 \(\mathcal{O}(\sqrt n)\) 个点，然后将每一条线平移到下方最近的点上，这之间会平均扫过 \(\mathcal{O}(\sqrt n)\) 个点。然后再按线的斜率排一遍序即可。另外，如果数据随机的话，可以尝试将平面均匀划分为 \(\sqrt n*\sqrt n\) 个块，每个块里就有 \(\mathcal{O}(1)\) 个点。那么对于一条直线，可以暴力求直线穿过的块，其它块预处理前缀和即可。

Day6（7.2）

今天主要讲了单侧递归和动态树问题，单侧递归主要用于解决前缀最大值的信息和括号问题。比如前缀最大值，每个区间维护前缀最大值的个数以及最大值，那么两个区间合并时，右区间会根据左区间最大值的情况递归下去，并满足每次递归都只向一边递归下去，这样就满足了 \(\mathcal{O}(n\log^2 n)\) 的复杂度。再比如括号的问题，询问一段区间的括号是否匹配，可以让每个区间维护括号匹配后的哈希值，两个区间合并时单侧递归下去来维护匹配的括号的哈希值即可。对于动态树问题，一般有集体将父亲换为另一个，处理这种问题可以用建虚点的方法，也可以将问题看成在 dfn 序列上操作，用 splay 维护序列上的各种操作即可。

Day7（7.3）

今天是考试。首先通读了一遍题，发现T1比较可做，然后就一直死磕T1。首先看到T1是一个区间子区间问题，就想到矩形加，矩形求和。具体的矩形加可以启发式合并，枚举哪些点的 LCA 是 \(x\)。然后就一直写，又调了一会儿。差不多用了 3h，后头看 T3 可能可做，就一直想，但是没想出来，最后只打了个暴力。得分100+0+20=120。

赛后听了讲题，T2 是一个分块题，T3就是直接用类似 dijkstra 的做法递推即可，要用到 meet in the middle 的 trick。

Day8（7.4）

今天主要讲了吉司机线段树和减半警报器。吉司机线段树主要用于处理 \(a_i \leftarrow \min(a_i,x)\) 这类的最值问题，具体就是记录最大值，次大值和最大值的个数，然后如果 \(x\) 小于次大值就直接暴力递归。我们用区间内不同数的个数作为势能，每次暴力递归都会让势能减少 \(1\)，所以复杂度是 \(\mathcal{O}(n\log n)\)。然后是减半警报器，这类问题一般是维护一个序列，当一些点的值大于某个数时就会发出警报，这样子的问题时多维度，多自由度的。具体解法是先将这个报警的值平均分在每个点上，然后如果一个点被减成负数了，就将其它点的值重新分配一下。通过分析得，每个数被减成负数得次数不超过 \(\mathcal{O}(\log n)\) 次，所以时间复杂度是对的，每个点可以用像堆之类得数据结构来维护。

Day9（7.5）

今天主要讲了倍增值域分块，这种问题主要操作形如：将 \(> x\) 的数减去 \(x\)，具体可以将值域按 \([2^i,2^{i+1})\) 分成 \(\mathcal{O}(\log n)\) 个块，每个块维护一个数据结构，存储区间的信息，当操作时，如果一个数操作后不在这个值域，就暴力操作。因为每个数最多发生 \(\mathcal{O}(\log n)\) 次跳跃，所以总的时间复杂度是 \(\mathcal{O}(n\log^2 n)\)。又比如神秘数这道题，它满足值域每次翻倍的性质，于是也可以暴力跳即可。维护的数据结构可以视情况而定，维护的东西有特殊性质的话可以直接用 RMQ，这样少一个 \(\log\)，总的来说运用非常灵活。