实际上本文涵盖了 \(2023.12.30 \sim 2024.1.1\) 之间的题目。
[Ynoi2006] rldcot
考虑如下两个点对：
-
\(\operatorname{lca}(x, y) = \operatorname{lca}(a, b) = u\)
-
\(x \le a \le b \le y\)
容易发现，若 \(\left(x, y\right)\) 被选中，则 \(\left(a, b\right)\) 也一定被选中，称之为 \(\left(a, b\right)\) 支配了 \(\left(x, y\right)\)。
因此只需要统计出所有未被支配的点对即可。
考虑什么样的点对是未被支配的。
- 若 \(\operatorname{lca}(x, y) = u\)，则 \(\left(x, y\right)\) 未被支配当且仅当不存在 \(x < z < y\) 且 \(\operatorname{lca}(x, z) = \operatorname{lca}(y, z) = u\)。
因此我们可以在固定 \(u\) 的情况下枚举 \(x\)，在其他兄弟子树的点集中寻找前驱和后继，即可得到所有未被支配的点对。
这一过程可以通过树上启发式合并实现。具体的，维护一个按标号排序的有序点集，每次保留重儿子的点集，将其他点集合并到重儿子的点集中，在合并其他儿子的点集时统计点对。
每个点会被合并 \(\mathcal{O}(\log n)\) 次，每次会贡献 \(\mathcal{O}(1)\) 个点对，因此有效点对数量为 \(\mathcal{O}(n \log n)\)，这部分的时间复杂度为 \(\mathcal{O}(n \log^2 n)\)。
接下来问题转化为如何统计答案。
首先我们将数对按最近公共祖先的深度值分组，那么询问 \(\left(l, r\right)\) 可以转化为询问有多少组点对存在点对 \(\left(x, y\right)\)，满足 \(1 \le l \le x\) 且 \(y \le r \le n\)。
因此我们可以将点对 \(\left(x, y\right)\) 按 \(x\) 的值降序排序，然后维护一个树状数组和一个数组，树状数组用于维护答案，数组用于维护某个颜色 \(c\) 对应的出现过的最小 \(y\) 值，记为 \(last_c\)。那么每次插入一个点对 \(\left(x, y\right)\) 时，若 \(y < last_c\)，那么就在树状数组上对区间 \(\left[y, last_c\right)\) 进行区间加操作，然后将 \(last_x\) 更新为 \(y\)。处理询问时单点查询即可。
总复杂度为 \(\mathcal{O}(n \log^2 n)\)。
「雅礼集训 2017 Day7」事情的相似度
首先可以通过对字符串建出后缀自动机后将问题放到 \(\tt{parent}\) 树上。这样问题就转化为了给定一个区间，求标号在这个区间内的点对的最近公共祖先的点权最大值。
类似与 [Ynoi2006] rldcot，统计出有效点对后扫描线使用线段树维护最大值即可。
谢特
首先对字符串建出后缀自动机后将问题放到 \(\tt{parent}\) 树上。
接下来问题便为点对贡献问题，对于点对间异或值的最大值可以使用 \(\tt{0-1 \, Trie}\) 解决。而最近公共祖先的权值贡献使用树上启发式合并即可。
也可以使用 \(\tt{Trie}\) 合并来在遍历树的过程中维护答案。
「Cfz Round 3」Circle
首先可以发现给出的函数实质上是在连边 \(i \rightarrow p_i\) 的图中走 \(k\) 步到达的点的标号。
由于 \(p\) 是一个排列，所以这个图是由若干个环组成的。
考虑有解的充要条件，即对于所有 \(S_i = 1\) 的 \(i\)，其所在的环的长度 \(k\) 都满足 \(k \mid l\)。由于对于 \(S_i = 0\) 的 \(i\) 无限制，所以我们统计出所有 \(S_i = 1\) 的 \(i\) 的个数 \(C\)，这样我们的问题就转化为了：
给定 \(l, C, n\)，构造一个可重集，使得其元素均为 \(l\) 的因子，且元素和在 \(\left[C, n\right]\) 之间。
可以发现，若其元素为合数，那么一定可以通过若干质因子构造出来，因此我们可以枚举质因子，然后判断其是否可以存在在集合中。那么可以发现可以在集合中的数只有 \(\mathcal{O}(\log l)\) 种，因此我们可以进行完全背包，进而可以得到方案，时间复杂度为 \(\mathcal{O}(n \log l)\)，可以通过。
[LNOI2022] 串
可以发现，将 \(T_0\) 设为空串，\(T_1\) 为 \(S_{1 \dots 1}\)，之后每次将左右端点 \(l, r\) 执行 \(l \leftarrow l + 1, r \leftarrow r + 2\) 便可以得到一个 \(\left\lfloor\dfrac{N}{2}\right\rfloor\) 的构造，进而确定了答案下界。
考虑如何优化答案，发现若一个子串在 \(S\) 中出现两次，设其第一次出现右端点为 \(r\)，长度为 \(len\)，那么可以得到一个 \(len + \left\lfloor\dfrac{N - r}{2}\right\rfloor\) 的构造，对所有出现多次的子串求出最大值即可。
还有四道，明天再写。