abc 375D
作者:
Air1222
,
2024-10-13 21:51:34
,
所有人可见
,
阅读 4
//当区间不断求和时,可以向拆开求和优化处理(比赛时没想到)
#include <iostream>
#include <vector>
#include <map>
using namespace std;
const int N = 2e5+10;
string s;
vector<int>c[N];
long long sum[N];
int main()
{
cin>>s;
int n=s.size();
long long ans=0;
for(int i=0;i<n;i++)
{
int k=c[s[i]-'A'].size();
ans+=1ll*i*(k)-sum[s[i]-'A']-k;
sum[s[i]-'A']+=i;
// for(int j=0;j<(int)c[s[i]-'A'].size();j++)
// ans+=(i-c[s[i]-'A'][j]-1);
//拆开考虑每一步的和是什么,即可优化
c[s[i]-'A'].push_back(i);
}
cout<<ans;
}
感觉 D 题比 ABCEFG 都水怎么办()
当时看了一下直接切了,这就是个下标和的形式啊。很好维护,
可是我写了七分钟。