题意：
给你一个长度为\(n，n \leq 1e5\)的字符串\(s\),设区间\([l,r]\)内，\(cnt_{a..z}\)表示字符\(a...z\)在这个区间内出现的次数。
让你求$$\sum_{ch=a}^{z} \sum_{i=1}^{n} \sum_{j=i}^n cnt_{ch}$$，其中\(i,j\)代表的是区间\([i,j]\)。
思路：
很明显我们需要优化这个\(n^2\)的过程，那么就相当计算每个字符在每个位置对答案的贡献，然后把他们相加，是什么贡献呢。
我们考虑用\(x[r]\)来表示区间\([i,r]\)内，字符\(s_r\)出现的次数，其中\(i\)应该是不断变动的左端点，\(r\)就是我们当前枚举位置。
用\(y[r]\)，来表示区间\([i,r-1]\)到\([i,r-1]\)对于当前字符\(s_r\)对于答案的增量，这里\(i,r\)的意义同上。
从\(1 - n\)枚举每个位置当做区间右端点计算对答案的贡献。
那么当前位置的字符\(s_r\)就会对自己对应的这个字符产生一个贡献，即\(2 * x[r-1] + 1\)，但这里的左端点我们未确定。
考虑用一个\(tim_i\)数组来维护某个字符前\(i\)个位置出现次数的对区间的总和，例如字符\(a\)共出现\(3\)次，分别在字符串对应\(3,6,9\)下标，遇到一个\(a\)左端点\([1,3]\)都会和这个右端点产生贡献，而遇到第二个\(a\),左端点\([1,6]\)都会和右端点产生贡献，而对于第三个\(a\)，左端点[1,9]都会和右端点产生共献，而贡献总和为 \((3-1+1) * 3 + (6-4+1) * 2 + (9-7+1) * 1 = 3 + 6 + 9\)，可以看到次数总贡献其实就是每个字符\(a\)的下标\(i\)的和。
所以我们可以用一个\(tim_i\)的表示前\(i\)个总的出现次数的贡献。
然后我们可以发现既然用\(tie\)表示\(x\)的和，那么其实\(2 * x_{r-1} + 1\)就可以优化成对于\(tim\)的一个式子，即\(2 * tim_{r-1} + i\)，即当前端点\(r\)和\([1,r]\)的每个点组成一个区间去计算出现次数多出来当前位置这一次的贡献，即每个左端点\(x\)求和就变成了\(tim\)。
还是好好理解这个计数过程的一步步简化。
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
const int N = 1e5 + 10;
const ll MOD = 998244353;
char s[N];
ll tim[30],add[30],sum[30];
//tim代表当前字符ch在当前位置出现次数的贡献,add代表当前字符对答案的新增贡献，sum代表当前每种字符对答案的总贡献
//一下过程应该是加和起来的一种情况
void solve() {
for(int i = 0;i < 30;i ++) tim[i] = add[i] = sum[i] = 0;
scanf("%s",s + 1);
int n = strlen(s + 1);
for(int i = 1;i <= n;i ++) {
for(int j = 0;j < 26;j ++) {
if(s[i] - ‘a‘ == j) {
add[j] = (add[j] + 2 * tim[j] + i) % MOD;
tim[j] = (tim[j] + i) % MOD;
}
sum[j] = (sum[j] + add[j]) % MOD;
}
}
ll ans = 0;
for(int i = 0;i < 26;i ++) ans = (ans + sum[i]) % MOD;
printf("%lld\n",ans);
}
int main() {
int T;scanf("%d",&T);
while(T--) {
solve();
}
return 0;
}
2021“MINIEYE杯”中国大学生算法设计超级联赛（7）1012 Yiwen with Sqc （计数 + 思维）
原文：https://www.cnblogs.com/forward77/p/15130461.html