子串分值和

对于一个字符串 S，我们定义 S 的分值 f(S) 为 S 中出现的不同的字符个数。

例如 f(“aba”)=2，f(“abc”)=3,f(“aaa”)=1。

现在给定一个字符串 S[0..n−1]（长度为 n），请你计算对于所有 S 的非空子串 Si..j，f(S[i..j]) 的和是多少。

输入格式

输入一行包含一个由小写字母组成的字符串 S。

输出格式

输出一个整数表示答案。

数据范围

对于 20% 的评测用例，1≤n≤10；

对于 40% 的评测用例，1≤n≤100；

对于 50% 的评测用例，1≤n≤1000；

对于 60% 的评测用例，1≤n≤10000；

对于所有评测用例，1≤n≤100000。

样例解释

子串 f值
a     1
ab    2
aba   2
abab  2
ababc 3
 b    1
 ba   2
 bab  2
 babc 3
  a   1
  ab  2
  abc 3
   b  1
   bc 2
    c 1

解题分析

1. 通过数据范围我们可以得到结论，本题允许的时间复杂度应该是O（n * logn）或者 O（n),而我们如果用两重循环，遍历所有区间，是O（n * n）的复杂度，毫无疑问是会超时的，于是得到结论最多可以扫描一遍
2. 根据上面的样例分析，我们可以令函数g(x,y)表示下标x到y当中的所有的分值和，例如 g(0,4) 就是 1 + 2 + 2 + 2 + 3 = 10 。我们可以发现去掉首字母a以后g(1,4) = 10 - 2 = 8 ,问题就是为什么我们减掉的是2 而不是其它的数? 给出解释：这个减掉的2 是在去掉a之后的区间当中，第一次出现a之前的所有的区间都会少掉a这个字母，分值和都会 - 1, 我们需要算出第一次出现a的位置和去掉a的位置之间的差值减掉，就可以得到g(1,4)
3. 如何实现？ 每一个字母一个队列，将出现的位置全部放入队列，去掉一个字母后就从队头弹出一个，这时候队头存的那个索引就是后面第一次出现这个字母的位置了

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>

using namespace std;
typedef long long LL;
const int N = 27;
queue<int> cnt[N]; // 用一个队列数组来统计每个字母出现的位置的相关信息

int main (){

    // 记录下每个区间内有多少
    // 需要记录从某个位置后面字母出现第一次出现的位置
    string str;
    getline(cin,str);
    bool st[27];
    memset(st,false,sizeof st);
    LL cur = 0;
    LL res = 0;
    for (int i = 0;i < str.length();i++){
        // 遍历字符串的所有位置
        // 用队列统计
        // 同时记录下总的值
        if (cnt[str[i] - 'a'].size() == 0) {
            // 这个字符没有出现过
            cur ++;
            st[str[i] - 'a'] = true;
        }
        cnt[str[i] - 'a'].push(i);
        res += cur;
    }
    cur = res; // 将cur变成所有的这个区间的f函数的和

    // 然后一侧慢慢收缩
    for (int i =0;i < str.length();i++){
        char a = str[i]; // 这个位置上的字符
        // 弹出以后需要修改cur
        cnt[a - 'a'].pop();  //弹出一个看看
        if (cnt[a - 'a'].size()) {
            // 说明后面还有这个字符
            // 我们看看这个字符出现的位置
            int index = cnt[a - 'a'].front();
            int mid = index - i; // 这个是需要减一的数量
            cur -= mid;
        }else {
            // 剩下的位置都要减掉1
            cur -= str.length() - i;
        }
        res += cur;
    }

    cout << res << endl;


    return 0;
}