2026 ABC 452

（本题解按照题目难度排序，仅用作补题记录）

A - Gothec

解题思路

B - Draw Frame

解题思路

C - Fishbones

解题思路

初步思路: 对于每个字符串 ，枚举它的每个起始位置 ，检查长度为 的子串的每个位置 上的字符是否与 相同。复杂度 ，会 TLE。

优化： 预先对每个 进行处理：
设 的长度为 ，
用三维标记数组 表示：

  • 长度为 len 的字符串，在位置 pos 上的字符是 （0-based 索引转换）。

后续判断时，只需遍历 个位置，直接检查对应标记是否为 1 即可。
预处理将匹配判断降至 ，避免 TLE。

D - No-Subsequence Substring

解题思路

正难则反思想：
对于每一个左端点，求出最近的包含 字符串的右端点 。
该左端点能找到的所有包含 的区间的右端点个数为 。

所有左端点的贡献和即为“不合法”的区间总数（即不包含 的区间数）。
用总区间数减去它，得到包含 的区间数：

实现方法：
对于每一个左端点，使用 lower_bound 二分查找 中下一个字符的位置，直到查找完 即可。

该时间复杂度可以通过。
但若使用预处理——记录每一个位置后面 个字母的最近出现位置，会比二分查找更快。

E - You WILL Like Sigma Problem

解题思路

求解

如果你学过整除分块，你也许会知道

前面的式子代入得

式 (2) 的前半部分
预处理 ，然后 直接求和即可。

式 (2) 的后半部分
预处理 的前缀和。
对于 ，考虑 的范围：
令 ，则 在 内取值相同（ 为整数）。
因此，对每个 计算 时，可以按照整除结果的一致性，逐个区间求解。

复杂度为 。

F - Interval Inversion Count

解题思路

已知，单纯求逆序对数为 的区间需要考虑的情况比较多，
所以我们可以求（逆序对数 ）的区间数，然后减去（逆序对数 ）的区间数，得到逆序对数恰好为 的区间数。
使用树状数组计算逆序对数，滑动窗口添加右端点和删除左端点都可以在树状数组中操作，
复杂度为 。