title: 贡献法解决子串问题
categories:

ICPC
tags:
null
abbrlink: ‘23933791’
date: 2024-11-28 00:00:00

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

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

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

贡献法：考虑当前这个字母可以在多少个子串中贡献，找到左边最近的相同字母，右边最近的相同字母，左右乘法原理计算可贡献子串数

会爆longlong，并且只开ans不够
##实现：用哈希表正序逆序扫一遍，注意对于左右边界的处理时假设0和n+1存在相同字母

// Problem: 子串分值
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2871/
// Memory Limit: 64 MB
// Time Limit: 1000 ms

int a[N];
int l[N],r[N];
map<char,int>mp;
void solve(){
	string s;cin>>s;ll ans=0;
	int len=s.size();
	string tmp=" ";
	tmp+=s;
	for(int i=1;i<=len;i++){
		if(mp[tmp[i]]){
			l[i]=mp[tmp[i]];
			mp[tmp[i]]=i;
		}
		else {
			l[i]=0;
			mp[tmp[i]]=i;
		}
	}
	mp.clear();
	for(int i=len;i>=1;i--){
		if(mp[tmp[i]]){
			r[i]=mp[tmp[i]];
			mp[tmp[i]]=i;
		}
		else {
			r[i]=len+1;;
			mp[tmp[i]]=i;
		}
	}
	for(int i=1;i<=len;i++){
		ans+=(i-l[i])*(r[i]-i);
	}
	cout<<ans<<endl;
}