4261. 孤独的照片

数据范围为500,000，所以应该控制在O(nlogn)或O(n)

我们发现要枚举的子串它其中有一个字母只出现一次，所以，我们可以去枚举只出现一次的字母是哪个，假设在第i个位置的字母为G，我们要枚举包含这个字母的，且只包含一个G的，且长度大于等于3的子串的数量，依次统计每个位置，然后累加起来就是答案。

每个字符串只出现一次的字母有且只有一个，因此，这样统计出的答案是不重不漏的。

每一个满足要求的字符串它一定只包含一个只出现一次的字母，所以，我们枚举只出现一次的字母就可以不重不漏的涵盖每一个要统计的答案。

当我们只出现一次的字母确定后，如何快速统计出来包含这个字母的，满足要求的子串的个数？

为了方便统计，我们可以预处理出来G左边有多少个连续的H，右边有多少个连续的H，然后分情况计数，

① 假设左右两边至少包含一个H，左边可以包含1-L个H，右边可以包含1-R个H，根据乘法原理，共L * R个

② 左边没有H，则右边至少包含两个H，即2. 3. .... R，共R - 1个

③ 右边没有H，则左边至少包含两个H，即2. 3. .... L，共L - 1个

答案即为三种情况相加，时间复杂度为O(n)

注意：由于中间涉及到乘法，所以答案可能会爆int，所以开个long long(^_^)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 5e5 + 10;

int n;
int l[N], r[N];
char s[N];

int main()
{
    scanf("%d", &n);
    scanf("%s", s);
    
    for (int i = 0, h = 0, g = 0; i < n; ++ i)
    {
        if (s[i] == 'G') l[i] = h, h = 0, g ++;
        else l[i] = g, g = 0, h ++;
    }
    
    for (int i = n - 1, h = 0, g = 0; i >= 0; -- i)
    {
        if (s[i] == 'G') r[i] = h, h = 0, g ++;
        else r[i] = g, g = 0, h ++;
    }
    
    LL res = 0;
    for (int i = 0; i < n; ++ i)
    {
        res += (LL) l[i] * r[i] + max(l[i] - 1, 0) + max(r[i] - 1, 0);
    }
    
    printf("%lld\n", res);
    
    return 0;
}