1，题目描述：

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

即对于一个字符串s来说，它的每一个顺序连续字串中所出现不同的字符的个数

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

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

输入格式

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

输出格式

输出一个整数表示答案。

数据范围

对于 20%20% 的评测用例，1≤n≤10； 对于 40%40% 的评测用例，1≤n≤100； 对于 50%50% 的评测用例，1≤n≤1000； 对于 60%60% 的评测用例，1≤n≤10000； 对于所有评测用例， 1≤n≤100000。

输入样例：

ababc

输出样例：

28

样例分析：

我们先对样例分析，对于ababc而言，我们把他的每一个连续子字符串画出，然后相加：

很简单让我们想到用暴力的方法做，遍历出每一个子字符串，然后再计算每一个子字符串中不同字符的数量，最后求和：

样例代码如下：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;

int a[26],ans;

int main()
{
	string s;
	cin >> s;
	int cnt = 0;
	for(int i = 0;i < s.size();i ++ )
	{
		for(int j = i ;j < s.size();j ++ )
		{
			memset(a,0,sizeof(a));
			cnt++;
			cout<<"第"<<cnt<<"个字符串为："<<"\"";
			for(int k = i;k <= j;k ++ )
			{
				
				cout<<s[k];
				a[s[k]-'a']++;
			} 
		 	cout<<"\"";
			int sum=0;
			for(int t = 0;t < 26;t ++ )
			{
				if(a[t] != 0) sum++;
			}
			cout<<"该子字符串不同字符数量为："<<sum<<endl;
			ans+=sum;
		}
			
	}
	
	cout<<"最终为："<<ans;
	
	return 0;
	
}

运行结果为：

但毕竟是蓝桥杯省赛题，怎么可能暴力这么简单呢？

不出意外的会超时，那么我们就得出现思考一遍：

不如让我们简化样例，改成最简单的情况（无重复元素时）---“abc”序列

abc 根据暴力思想，我们可以拆分成：

a----------1个
a b--------2个
a b c------3个
  b -------1个
  b c------2个
    c------1个

这时我们看到每一行对应一个数字，我们是否可以用每一个数字代表每一行呢，当然可以，比如：

1----a-----1个
1----a b---2个
1----a b c-3个
1------b---1个
1------b c-2个
1--------c-1个

我们看到每一行可以看作是一个数“1”，再对比后面的个数，不难想到其实每一个数都是重复再一行中出现

比如第三行的a b c可以看成是3个a b c 叠加态

那么我们就可以实现将**“每一行对应一个数字”与“每一个数字代表每一行”**关联起来，也就是把叠加态拆分成原状态

1----a
2----a b 
3----a b
4----a b c
5----a b c
6----a b c
7------b 
8------b c
9------b c
10-------c

如果理解了我上面的那句话就可以明白我们为什么要这么写。

写完了不难看出，其实每一个字符对应的行数实际上是它往两边扩展的乘积。

//比如字符“b”
//它往两边的扩展为：
----b----
--a b----
----b c--
--a b c--
//一共四个扩展，是以自己为中心的扩展

那么我们不难推出“abcdefg”这个类型也是这样的：

//运算公式为：
int sum = 0;
for(int i = 0;i < len;i ++ )
{
	sum+=(i+1)*(len-i)
}

但是，生活总不是一帆风顺，比如万一出现了重复的元素

不一般情况，有重复元素,如“aba"

我们重复上面的操作，把**“每一行对应一个数字”**写出来

a b a
a------1
a b----2
a b a--2
  b----1
  b a--2
    a--1
//和为9

我们再把叠加态找出，要注意的是：我们两个相同的元素再同时出现时，我们应该减去一个

这个也很好理解比如两个圆重叠时，我们一般算总面积是两圆面积相加再减去中间的重复面积：

我们可以让左边重复的减一，也可以让右边重复减一，当然，为了好理解，我在这里让右边重复的减一

所以我们可以把叠加态解析为：

a b a
1--a
2--a b
3--a b
4--a b a
5--a b a
6--a b a
7----b
8----b a//这里不需要重复分解的原因上面已经说过了，重复元素再算时要减一
9------a

现在我们把题目给定叠加态解析：

1------a
2------a b//重复2次
3------a b
4------a b a//因为是向左不减，所以是正常解析
5------a b a
6------a b a
7------a b a b//b也是左边不减，正常解析
8------a b a b
9------a b a b
10-----a b a b
11-----a b a b c //重复5次
12-----a b a b c 
13-----a b a b c 
14-----a b a b c
15-----a b a b c 
16-------b    
17-------b a//正常我们要重复两次的，但是由于左边a的重复性，我们减一次重复，2-1=1
18-------b a b //a,b又向左重复，所以是3-1-1=1
19-------b a b c //a,b向左重复，所以是4-1-1=2
20-------b a b c 
21---------a 		//这里不减一的原因是，a开始做排头，也就是重新更新
22---------a b		//这里重复2次，但是b的向左重复，所以是2-1=1
23---------a b c    //重复3-1=2次
24---------a b c
25-----------b		//同样，b排头更新
26-----------b c    //重复2次
27-----------b c  
28-------------c

再给出规律之前，我们对“b”字符再分析一边遍：

//本来没有重复的时候运算公式为：
int sum = 0;
for(int i = 0;i < len;i ++ )
{
	sum+=(i+1)*(len-i)
}

但是当出现重复时----->
/*
	本来拿第一次出现b和第二次出现b举例子：
	第一次b: f(b)=(i+1)*(len-i)=(1+1)*(5-1)=8
	第二次b: f(b)=(i+1)*(len-i)=(3+1)*(5-3)=8
	如果按照这个公式计算，很容易看出b多计数了
------------------------------------------------------
	我们来对第一次出现的b来看：
	a b a b c
	<-*----->看出第一个b应该是两边扩展2*4=8
	
	我们来对第二次出现的b来看：
	a b a b c
	<-----*->但是由于左边有重复的元素
	所以正确的应该是：
	a b a b c
	    <-*->第二个b向两边扩展应该是2*2=4
-------------------------------------------------------
*/

写完之后我们可以看出一个规律:

1.如果在没有重复之前，则和上面的无重复元素一样公式：sum+=(i+1)*(len-i)

2.如果重复，那么左看齐，再重复公式：sum+=(i + 1 - last[s[i]]) * (len - i );

这里的last[]是上一次出现该元素（也就是左边出现该元素）存的下标

那么最终的ac代码为：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int last[200];

int main()
{
    string s;
    cin >> s;

    int n = s.size();

    ll sum = 0;
    for (int i = 0; i < n; i ++)
    {
        sum += (ll)(i + 1 - last[s[i]]) * (n - i );  //数据大，防止越界，开long long
        last[s[i]] = i+1;
    }

    cout << sum << endl;
    return 0;
}