虚树浅谈 我们就直接进入主题了，毕竟还有 $1 \tt h$ 就要准备去考场了，可能是我退役前的最后一篇学术类的吧。 树上的题目中可能会给出 $\sum k_i \le 5 \times 10^5$ 之类的限制，那么我们常常会考虑到两种东西： 自然根号，也就是本质不同的 $k_i$ 只有 $\sqrt V$ 种。 虚树。 对于给定的一个点集，我们往往不希望这个是一个森林，所以我们钦定加上根节点特判即可。 我们考虑将点集按照 $\tt dfs$ 序进行排序，之后从前向后往栈中加点。我们设 $lc$ 表示当前点和最后加入栈的点的 $\tt Lca$。 如果 $lc = stack(ed)$ 那么意味着还是同样一个子树的链，我们直接加入即可。 不然意味着更换了子树，我们考虑将当前子树的树全部建出，那么因为更换了子树，也就是意味着 $dfn_{lc} \le stack(ed)$ 的，我们考虑退栈直到合法为止。 1while(ed > 1 && dfn[lc] <= dfn[st[ed - 1]]) G.add(st[ed - 1], ...

CF1396C Monster Invaders CF1396C Monster Invaders 建议不要看中文，直接看英文题面，里面有很重要的一句话：一开始都没有装弹，一次只能装一把枪。 这个东西决定了我们贪心的方案，不然的话可能像我以前或者一开始一样当成同时开始冷却 /qd 这边再吐槽一下，之前已知不会订正，现在想想还是挺简单的。 因为 $r_1 \le r_2 \le r_3$。 首先考虑总共只有 $3$ 种打的方案： $a_i \times r_1 + r_3$。 $a_i \times r_1 + r_1 + r_1$。 $r_2 + r_1$。 而且考虑走的方法，我们会考虑一开始直接走到头，之后一次回来，发现距离是 $2d$。 我们考虑相邻两个一起搞定，那么乍一看是 $3d$ 但是每两个相邻之间本质上只有 $d$，均摊一下还是 $2d$。 所以我们只需要考虑相邻的部分，直接考虑当前是否打死，设 $f(i, 0/1)$ 表示当前考虑到位置 $i$，$\tt boss$ 还有血量 $0/1$ 的最小代价。 直接分类讨论暴力转移即可。 ...

#514. 【UR #19】通用测评号 #514. 【UR #19】通用测评号 一个小 $\tt trick$： 对于这样的 $a$ 限制，我们可以无视它，但是代价是无穷项。 感觉感性证明更好理解：对于一个位置多的操作，我们直接不做即可，直接去考虑下一个操作，显然答案是不变的。 考虑填充的结束条件，就是恰好有一个燃料舱是 $b$ 单位的。 而且因为期望是线性的，我们直接对于每个燃料舱进行计算概率即可。最终的答案就是 $(n - 1) \times P$。 我们将 $z = 1$ 带入即可。 那么我们考虑一下这个 $P$ 是怎么计算的，我们不妨考虑拿出最后一个是 $b$ 的燃料舱，那么就是 $n$。为了方便我们设 $f(x)$ 表示进行了 $x$ 次操作的概率函数，也就是 $\dfrac{z^x}{x!n^x}$。 显然最后一个仓就是 $f(B - 1) \times \frac{1}{n} \times n = f(B - 1)$。 之后对于其他仓我们只要保证至少一个是符合条件即可，那么就是 $(e^x - f(A - 1)) \times (e ...

CF1349F1 Slime and Sequences (Easy Version) CF1349F1 Slime and Sequences (Easy Version) 题目中最明显的限制就是： 如果 $i$ 出现，那么必定有 $1 \sim i - 1$ 从小到大出现。 也就是说如果将 $1 \sim i - 1$ 和 $i$ 的位置写出来是一个严格递增的形式。 我们不妨考虑对于每个位置 $i$ 计算数字 $x$ 的答案。 也就是说对于前面的位置我们必须有 $i - 1$ 个上升的数字，来保证其可以出现，当然对于后面都没有影响。 具体来说如果后面出现了，我们不计算贡献。 如果没有出现，显然没算。 我们发现对于一个排列和一个合法的序列是一一对应的，可以考虑对于一个合法的排列，倒着写出 $1$，倒着写出 $2$。 之后有几个上升的肯定就是有多少个合法的当前位置。 后面的位置随便填即可。 答案就是$$ans_x = \sum_{i = 1} ^ n n^{\underline{i}} \times \left<\begin{matrix}i \ ...

CF1404C Fixed Point Removal直接考虑每个数是否可能满足条件，显然对于 $a_i \le i$ 的情况才是可能的。而且发现对于 $\forall j > i$ 是不影响当前状态的。 我们考虑对于每个 $i$ 维护一下其距离条件还有多少位置，也就是 $i - a_i$。我们每一次将前面一个数删去，也就意味着后缀全部 $-1$。这个东西可以拿线段树简单维护。 发现对于 $r$ 只不过是对合法数范围的限制，我们直接维护一下区间合法的数的和即可。 之后我们只需要对于询问离线一下，从大到小按照 $l$ 加点即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211 ...

Splay 入门 其实 $Splay$ 不能算作高速平衡树，但是事实上其代码非常好些只要记住一些细节。而且是平衡树中可以维护动态树的存在的，当然你也可以用 $FHQ-Treap$ 维护 $ETT$。 时间复杂度 我们必须了解一下每个平衡树维护平衡的方式，$Splay$ 是通过旋转，注意是双旋才可以保证复杂度。 我们将一个节点旋转到固定位置的操作称为 $splay$。 当然我们可能存在一次 $splay$ 是 $O(n)$ 的情况，根据势能分析可以得到复杂度是 $O(n \log n)$ 的。 因为是均摊而不是期望，所以我们不能对其进行可持久化操作。 splay 操作 我们需要先知道对于一条链我们会旋转成什么样子： 最终会变成： 我们直接对于当前操作进行模拟即可： 12345678void Rotate(int p) { int f = t[p].fa, ff = t[f].fa, k = pd(p); t[p].fa = ff; if(ff) t[ff].ch[pd(f)] = p; t[f].ch[k] = t[p].ch[!k], t[t ...

浅谈线段树合并 观前提示：本文主要介绍线段树合并的浅层应用和较为简单的写法。 权值线段树 我们线段树的很多操作都是基于动态开点权值线段树进行实现的，空间是 $O(n \log n \times K)$ 其中 $K$ 是每次询问进行线段树操作的个数。当然我们有优化到 $O(n)$ 空间的做法，这个我们后面再谈。 维护方式 我们通常将其用来维护一些可以通过全局表示的信息，最显然的就是一段值域，或者是深度等。 线段树合并也可以在线进行维护信息的，也就是我们对于每个线段树都要保留下来，我们像可持久化一样，每次进行操作的时候就复制一份节点，这个空间就是 $O(n\text{ polylog(n)})$。 具体做法 考虑合并的时候贪心一下，如果说两棵树其中有一个是空的，那么我们直接接到另外一个树上即可。 这里推荐一种写法： 123456789101112131415int merge(int u,int v) { if(!u || !v) return u | v; if(isleaf(u)) { Add(v, val[u]); ...

CF1453E Dog Snacks CF1453E Dog Snacks 可能一开始会简单地考虑将深度最大的作为 $k$，但是样例已经很显然得告诉可以通过跳到一个稍微浅一点的位置。 那么显然有一个很明显的贪心，就是我们设 $f(i)$ 表示子树 $i$ 的结尾叶子，也就是深度最浅的叶子节点和 $i$ 的距离。那么我们显然肯定最终是选择到一个深度最浅的点。 我们具体跳的过程肯定是优先跳深度大的，之后逐渐向小的跳跃。我们考虑这里不可避免的贡献，也就是如果是深度最大的需要跳到别的子树，就是其深度 $+1$。 我们特殊考虑一下根节点，也就是我们跳完时候还要回到根节点，那么我们可以考虑在根节点的时候最后到深度最大的子树，这样我们的贡献就只有最大深度了，显然更优秀。 我们总结一下： 不是根节点： 不是一条链：$mxdep + 1$。 是一条链：不更新，因为我们会在根节点的时候同一计算。 根节点： 是一条链：直接就是最大深度。 不是一条链：$\max($最大深度，次大深度 $+1)$。 123456789101112131415161718192021222324252627 ...