Li Yuanzhuo's Blog

Part 0. 引子 很多时候，我们一下想到的DP是 Θ(n2)\Theta(n^2)Θ(n2) 级别的，但是题目的数据范围不允许。这个时候，我们就需要一定的方式来优化DP。 常见的DP优化很多，这里介绍单调队列优化和斜率优化。 Part 1. 单调队列优化 考虑形如下面形式的方程： dp[i]=min⁡i−k≤j≤i{c[j]}+a[i]dp[i]=\min_{i-k \le j \le i}\{c[j]\}+a[i] dp[i]=i−k≤j≤imin​{c[j]}+a[i] 这里，请把 c[j] 当作一个关于 jjj 的函数，比如 c[j]=dp[j]+a[j] 如果按照朴素算法进行计算，就是要两层循环，外层枚举 iii，内层枚举 jjj，总复杂度为 Θ(n2)\Theta(n^2)Θ(n2)。 怎么优化呢？其实也很显然，就是如果在前面的计算中，发现有一个数，既比当前的值靠后，又比当前值小，那么当前值肯定不是最优的答案。也就是说我们完全可以搞一个单调队列，如果加入了一个值以后，破坏了其单调性，那么这个值肯定要优于前面的值，于是把队尾的元素弹出，直到满足单调性为止。代码也很简单。 这 ...

Part 0. 引言 区间第kkk小问题是一个很经典的问题。很明显，区间最值问题应该用线段树解决，但是问题是这里并不是最大值/最小值，而是第kkk个值。这样就意味着，如果我们要对他进行普通线段树的合并，那么就会导致你需要把左右两个区间前kkk个值都找出来，如果 k=nk=nk=n，那么这个问题的合并复杂度就是O(nlog⁡n)O(n\log n)O(nlogn)，再加上本身的查找复杂度，这个复杂度就变成了O(n2log⁡2n)O(n^2\log^2 n)O(n2log2n)，还不如暴力呢。 那么，这个问题应该如何解决？他和可持久化线段树又有什么关系？ Part 1. 换个思路 如果普通的线段树行不通的话，我们完全可以另行其道。比如说……我们可以先想一个简单的问题：如果现在不是让你求一个区间，而是从1到某个位置的第kkk小值，你会怎么做？ 如果你能想到桶，那么这个问题就好办多了。从1到rrr的区间里，我们给每一个数都做一个桶，这样如果我们要找第 kkk 小值，就只需要在这个桶上面二分。也就是说，如果左区间那一部分有大于等于kkk个数（注意这里用的是桶，所以这里的区间是桶的区间，而不是原始 ...

Part 0. 引子 Tarjan，是图的连通性的一类算法们。没错，这个算法如果你到洛谷上面查的话，会有5个模板题。他们分别是：点双连通分量，边双连通分量，缩点（强连通分量），割点，割边。 没错，就是这么多。他们的基本思路都一样，就是一个 dfn 和一个 low。如果让一个学过Tarjan的人评价一下这个算法的话，那就是四个字，又臭又长！ 不过虽然他的代码很长也很难理解，但是他的作用是巨大的，很多图论相关的题目都可以用Tarjan进行化简，让他变成可做题。 Part 1. DFN与LOW——Tarjan的核心思想 DFN是DFS序，也就是说，对于一棵树，我们在进行DFS的时候，DFN就是搜索到当前节点的时间戳。那么，在一个图中呢？ 如果我们的图是存在环的，那么我们的一个显然思路就是一个 vis 数组标记是否已经到达过。虽然这样有些时候会发生问题，平时我们不这么干，但是对于 Tarjan，他是有用的。 请想象一下，我们对一个图（不管是有向还是无向），跑一遍 DFS，如果 vis 过了就跳过，否则 DFS这个点，这样最终会形成什么样的数据结构？树！没错，这个方式跑出来的树，叫做 DFS 生 ...

Part 1. RMQ的种类 这个不用多说，RMQ是一类非常常见的问题。以下是一些常用的数据结构，以及他们所能胜任的问题（这里只讨论基本情况，不关心可持久化之类的其他问题）： 前缀和：静态区间求和 ST表：静态区间最值（也可以是与最值有关的，比如 gcd⁡\gcdgcd） 树状数组：区间单点修改，区间查询 线段树：通吃 那么，我们有没有想过，为什么这些数据结构就有所区别，能胜任的问题形式也不同呢？ Part 2. 静态 RMQ 的区别 其实，RMQ的区别就是这个数据结构存储信息的区别。区别在那里呢？我们先要明白一个问题，那就是 RMQ 相关的数据结构肯定是通过某种预处理，使得在最终处理实际问题的时候，能够压缩复杂度。 两种典型的RMQ问题就是最值问题和加和问题，两种问题在暴力的复杂度下，都是 O(n)O(n)O(n) 的单次查询。 接下来，我们从静态入手，来看看这两种问题的简便求解策略： 对于加和问题，我们可以利用前缀和，利用“一大块减去一小块就是剩下的”的思路，把从前往后的和求出来，这样在最终进行计算的时候，我们就只关心最前面和最后面的值。 对于最值问题，我们会发现，虽然 ...

SDSC2024 游记 怀着激动的心情，我报名了SDSC2024。 Day 0 报道日，我12点就到了宿舍（要求是3点到），然后就对着空无一人的房间发呆，等了半天才等到了Taoran_01来，然后就是好多人都来了。 简单了解了一下，宿舍共6人，2个新高一，2个新初三，2个新初二，全部是SDFZ学生。其中lalaji老师不在这住，只是来这里报道，往后他也只是在这里午休。于是我们就把离空调最近的上铺给了他（反正他也用不到），剩下的人各自选了一张床。 Day 1 第一天打模拟赛，四道题目三道是原·题，只有T1是原创的（模板）题。结果就只做出来了那个最小生成树的模板，然后后面就一直在打暴力。 下午讲题，只能听懂前两道题，后面两道题根本听不懂，因为自己根本没学过字符串。讲完赛题开始讲课，结果这位老师直接就把我给整蒙了——您老到底是在讲数论，还是在念天书啊？从第30分钟开始，我就发现我应该放弃理解这将是。很遗憾，一整天啥也没听懂。不过大家都是一样，于是那一天我们就集体去听讲座了，也没补题，也没复习。 Day 2 第二天的模拟赛题目，好了，没有原创了。然而题不是原创题，出题人总是能在其中找到一些可以 ...