题解 | #回文(version 3）#

部分参考了FZANOTFOUND的题解

• 对于 答案为   
• 对于 只需要统计区间内每个字母 的出现频次 ，该字母的贡献为    再累加求和即可。这里可以通过预处理 表示前 个字符中字符 的出现次数。最后答案 
    
  其中
• 对于 我们首先要找到一对相同的字符，他们的下标分别是 ，他们的贡献是 。 那么我们可以考虑和 一样，对于每一个字母 ,假设他在区间内出现频次为 ,下标为。我们要计算的就是：     
  当然这个既有 又有 是没法子用前缀和算的，我们要对 分别算贡献 ：
• 当右端点是 时， 可以取 ，共 次。   所以：  
• 当左端点是 时， 可以取 ，共 次。   所以：  
• 别忘了 ，求和后就是区间内相同字符对数，即 。  
• 三部分合并：变量统一用 来替代，即可得到：    
  然后接下来出现了个问题，我们这个 他是在 中第 个出现的字符 ，我们总不能每次询问都去把这个区间内 的出现位置去先遍历一遍吧？ 
  我们回过去看看 是怎么干的： 表示前 个字符中字符 的出现次数。  
  可以查到什么？区间 中该字符出现的总次数。如果我们知道字符 在原串中的全局排名，那我们就可以用全局排名减去前面出现的次数得到 了  
• 令 为该字符在原串中的全局排名， 为区间 中该字符出现的总次数。。 代入化简得到最终公式：     
• 最终这个题变成算三个前缀和了：  

1. 字符 在前 个位置出现次数  
2. 快速查询  
3. 快速查询   

• 每次查询对于每个字符 ：  

1.    
2.    
3.   
4.   
5.   
   最后求和即为答案。 这里再送一个初始化小技巧：

void init(string &s,int n){
    for(int i=1;i<=n;i++){
        int cur=s[i]-'a';
        for(int j=0;j<26;j++){
            cnt[j][i]=cnt[j][i-1];
            sump[j][i]=sump[j][i-1];
            sumrp[j][i]=sumrp[j][i-1];
          //先对26个字母的前一个下标进行继承
        }
            cnt[cur][i]++;
            sump[cur][i]+=i;
            sumrp[cur][i]+=(cnt[cur][i]*i);
          //再对当前字符进行处理
    }
}

这样代码是不是更简洁了呢awa。