2023.10.2

2023.9.29

放假了哈哈。

然后下午去姥姥家，然后晚上看了一晚上视频，没干啥有意义事情。

2023.9.30

去姥姥家，和我表哥成功会面，然后打了会奥日，打到救猫头鹰了，看奥日和猫头鹰贴贴完了之后猫头鹰就寄了。恼了。我哥他同学亲切的送来了一份榴莲蛋糕，然后吃完了，感觉确实不太喜欢榴莲。

然后晚上回去和某只兔子（悠悠）玩了会密室逃脱模拟器，两个人网都巨卡，然后就放弃了，我就去打 CF 了。

然后成功以 1 分优势战胜了小粉兔（）

SoyTony：你比小粉兔高一分，小粉兔 51 名，那你就 50 名进集训队了

2023.10.1

上午睡觉。

然后开学了，哈哈，非常开心。

下午啥都没干，看了一道题然后也没写出来。然后写了个 To-do list，希望 10 月能做完吧。

由于高一高二都没开学，我们只能去西扩食堂吃饭，西扩食堂好高级。

2023.10.2

喜报：我起床了。

今天是 hzoi 参加的第一场 accoders 联测，希望同学们~~下分愉快~~。

CF526G Spiders Evil Plan

还挺有趣的题，但是我菜啊！昨天下午看了一下午不会做。（甚至一开始还看错题想了半天）

首先考虑这样一件事情：显然我们选的路径的端点都是叶子。如果我们选出了 \(2k\) 个叶子作为路径的端点，那么一定存在一种方案使得这 \(2k\) 个点形成的虚树中的边全部选择了。考虑如果不是一个连通块，那么可以将不相交的两条路径更改连边顺序，一定能够相交，且这个过程一定结束，因为每次未覆盖的边数一定减少，所以一定存在方案。

那么我们现在可以只考虑选 \(2k\) 个叶子，使得虚树边权和最大。首先我们有个最朴素的想法，每次询问以 \(x\) 为根，然后贪心的选 \(2k\) 个贡献最大的。发现这实际上是将树进行了一个长链剖分，每次选最长的一个长链。由于长链的性质，容易发现从大到小选一定不会出现不连通的情况。那么直接贪心选 \(2k\) 条即可。不过这样选完之后虚树不一定会包括 \(x\)，需要一定调整，我们先不考虑这么多，因为这毕竟是暴力做法。

问题在于，以每一个点为根做复杂度太高了，不能接受。发现，我们选的最长的刘静一定是到直径的某一个端点，那么也就是说直径的一个端点一定存在于最后的连通块中。那么我们以这两个端点为根做一遍上面的做法即可。注意到端点一定是叶子，所以问题变成了选 \(2k-1\) 条长链，这个是容易预处理出一个前缀和作为答案的。

但是意识到这样的方案不一定包括 \(x\) 了。考虑进行一些调整，发现我们肯定是加入包含 \(x\) 的最长链，然后删去某一条链。我们肯定要让删去的链长度最小，那么如果最后被删的这条链与我们要加的这条链没有交，那么肯定是选第 \(2k-1\) 长的这条链将其删去，而有可能我们要删的是某条与要加入的长链的下半部分，把这种情况也算一下就行了。这里并不需要判断是不是只有一条链，因为就算是有多条链，删了之后不连通了，也不重要，因为这不会影响到答案。

P3642 [APIO2016] 烟火表演

咕了太长时间了，slope trick 基础练习题。

首先容易写出一个 DP，设 \(f_{u, x}\) 表示 \(u\) 子树内所有叶子都等于 \(x\) 的最小代价，那么有：

\[f_{u, x} = \sum_{v \in s_u} \left(\min_{0 \le k \le x} f_{v, k} + |x - k - w_v|\right) \]

绝对值加 \(\min\)，直接猜 \(f_u(x)\) 为凹函数，那么考虑 slope trick。

首先考虑每个儿子的操作，每次将这个东西加一个绝对值函数再取 \(\min\)。注意到，如果 \([0, x]\) 范围内 \(f_v(k)\) 有斜率等于 \(0\) 的位置，那么加绝对值之后新的最小值一定是这段平坡的左端点或者右端点，如果不存在斜率为 \(0\) 的地方那么最小值一定在右端点上。那么我们就可以通过简单讨论，得出：

（设 \(g_u\) 为 \(\min f_u(x)\)，\(p_u, q_u\) 为斜率为 \(0\) 段的左右端点）

\[\begin{aligned} f'_u(x) &= \min_{0 \le k \le x} f_{u}(k) + |x - k - w_u|\\ &= \begin{cases} f_u(x) + w_u & 0 \le x \le p_u\\ g_u + p_u - (x - w_u) & p_u < x \le p_u + w_v\\ g_u & p_u + w_u < x \le q_u + w\\ g_u + (x - w_u) - q_u & x > q_u + w \end{cases} \end{aligned} \]

简单分类讨论即可得出，不再赘述。

然后把这个图像画出来，发现这个操作实际上是将这个凸函数的左半部分上移 \(w_u\)，将平坡向右移 \(w_u\)，然后用斜率为 \(-1\) 的直线连接两部分，右半部分全部删除，并且在右端点的位置变为斜率为 \(1\) 的直线。

考虑怎么用 slope trick 维护。首先发现右半部分的点永远不超过 \(1\) 个，且斜率并不重要，所以我们并不需要维护右边的点，我们只需要维护左边的点与平坡的两个端点即可。然后上述过程用 slope trick 简单维护一下就行了，大致就是将第一个点向右移动 \(w\) 位，然后令 \(p_u, q_u\) 加 \(w\)。

然后考虑合并，由于右边的点均只有一个，我们考虑先合并左边再依次插入右边，合并直接可并堆或者启发式合并即可，插入右边时分类讨论一下插入的点在平坡还是在左边，如果在平坡就更新平坡右端点，如果在左边那么就是将斜率 \(-1\) 的部分变为平坡了。同样容易维护。然后就做完了。

P9623 [ICPC2020 Nanjing R] Baby's First Suffix Array Problem

考虑先用整个后缀的排名来表示这个子串的排名，然后再考虑删除一个后缀后排名的变化。这样初始值就是区间内有多少点 \(rk_i\) 小于 \(rk_{k_i}\)，直接做就行。

然后考虑什么情况下删除一个后缀后大小关系会发生改变。设 \(rk_i < rk_j\)，那么考虑两个串的 \(\mathrm{lcp}\) 后的一个字符，一定有前者小于后者，那么如果大小关系发生改变，只能是因为后者的最后一个字符被删除，那么就一定需要满足 \(i < j, \mathrm{lcp}(i, j) \ge r_i - j + 1\)。

那么我们现在把问题分成两部分：求有多少原来 \(rk_x < rk_{k_i}\) 的 \(x\) 删除后缀后大于了它，与多少 \(rk_x > rk_{k_i}\) 的 \(x\) 删除后缀后小于了它。

第一部分相当于要求满足下面条件的 \(x\) 的个数：

\[\begin{cases} rk_x < rk_{k_i}\\ l_i \le x < k_i\\ \mathrm{lcp}(x, k_i) \ge r_i - k_i + 1 \end{cases} \]

考虑到 \(\mathrm{lcp}(x, y) = \min_{i \in (rk_x, rk_y]} h_i\)，那么说明这个东西是存在单调性的，我们可以直接 ST 表二分找到满足条件的最小的 \(rk_x\) 的值 \(L\)，那么上述条件就改写为：

\[\begin{cases} L \le rk_x < rk_{k_i}\\ l_i \le x < k_i\\ \end{cases} \]

然后这就是一个很直接的二维数点问题了，直接做即可。

第一部分相当于要求满足下面条件的 \(x\) 的个数：

\[\begin{cases} rk_{k_i} < rk_x\\ k_i < x \le r_i\\ \mathrm{lcp}(k_i, x) \ge r_i - x + 1 \end{cases} \]

这个条件就没有很好的单调性了，没有很简单的做法。同样注意到 \(\mathrm{lcp}\) 是在 \(rk_i\) 上的一个区间最小值，区间最小值启发我们想分治。

具体的，我们对 \(rk_i\) 进行分治，这样我们可以将上述询问拆成若干个形如，求有多少数 \(x\) 满足：

\[\begin{cases} rk_{k_i} \in [L, mid], x \in (mid, R]\\ k_i < sa_x \le r_i\\ \min\{v_{rk_{k_i}}, v_{x}\} \ge r_i - sa_x + 1 \end{cases} \]

（\(v_i\) 表示 \((i, mid] / (mid, i]\) 的 \(h_i\) 最小值）

即：

\[\begin{cases} rk_{k_i} \in [L, mid], x \in (mid, R]\\ \max\{k_i+1, r_i - v_{rk_{k_i}} + 1\} \le sa_x \le r_i\\ sa_x + v_{x} \ge r_i + 1\\ \end{cases} \]

发现这就是一个二维数点的形式了，那么我们直接树状数组维护就能跑了，这样套上一个分治，复杂度就是 \(O(n \log^2 n)\)，可以通过此题。