部分参考了FZANOTFOUND的题解 对于 答案为 对于 只需要统计区间内每个字母 的出现频次 ,该字母的贡献为 再累加求和即可。这里可以通过预处理 表示前 个字符中字符 的出现次数。最后答案 其中 对于 我们首先要找到一对相同的字符,他们的下标分别是 ,他们的贡献是 。 那么我们可以考虑和 一样,对于每一个字母 ,假设他在区间内出现频次为 ,下标为。我们要计算的就是: 当然这个既有 又有 是没法子用前缀和算的,我们要对 ...