zlxFTH's Blog

一些观察

首先考虑 tarjan 缩点，如果存在一二类点当且仅当这个 DAG 只有一个入度为 $0$ 的点且一二类点必定在其中。（假设这个块是 $S$）

如果不存在一类点，$S$ 里面的点就全是二类点。

横叉边、前向边很烦，但是如果确定一个一类点之后以它为根就只有树边和返祖边了。

所以大致做法可以分成两部分，找出一个一类点和确定剩下的一二类点。

注意到只要存在一类点，$S$ 以外的点和边都可以不考虑（如果 $O(n)$ 判断一个点是否是一类点的代价能接受）。

讨论范围缩小到 $S$​，因为是一个强连通分量，所以任选一个点作为根所有点都可以走到它。

Upsolved：A-G

我一来就想二分，然后发现 consider it backwards 可以把二分去掉，发现需要找到 $h_{cur}\le x + cur$ 最大的 $cur$，这个东西是单调的，于是得到了 $O(qn)$​ 的做法。

剩下的时间一直在尝试离线下来一起操作，用尽力气得到了一个很多细节的平衡树维护 id 的做法。

最后的最后，重新 consider it forwards 发现一个树状数组就搞定了。

首先最大值处一定是直接停下来的，所以可以断环成链，$a_1, a_{n + 1}$ 处为最大值。

设 $f(i)$ 表示当前在 $i$ 的答案，$f(1) = f(n + 1) = a_1$。

$$f(i) = \max(a_i, \frac{f(i - 1) + f(i + 1)}{2} - b_i)$$

手玩 $l_i = r_i, k = 0$ 的情况，如果不存在 $a_i = 1$ 的情况直接用操作 $1$ 就行了，否则一定是用若干段不交操作 $2$ cover 掉了所有 $a_i = 1$​ 的段。称这样的操作为“一层操作”。

在这样一层操作之后可能会使得 $a_i = 2$ 的位置变成新的 $a_i = 1$，继续进行若干层操作。

Barrett 取模优化，通常在模数为输入的情况下使用。

多项式 $\text{inv} + \exp + \ln$

Ubuntu Typora 默认字体很难看，需要改一下配置文件，注意更新之后又会失效，需要重新添加。

用 bash 实现类似 SelfEval 的工具。

新一轮的模板整理采用分模块的方式，同时只保留重要内容，删去简短能够在赛场直接写出来并且不是每个题都要用的东西。

upd：圆相关的很多东西我都是现推的，所以该部分内容不完整。其他东西都是验证过正确性的。由于 SCOI2024 打完了，所以本篇不再维护。