Farmer John 最近购入了 NN 头新的奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。
奶牛目前排成一排，Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。
然而，他不想拍摄这样的照片，其中只有一头牛的品种是更赛牛，或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。
在为每个连续不少于三头奶牛的序列拍摄了一张照片后，他把所有「孤独的」照片，即其中只有一头更赛牛或荷斯坦奶牛的照片，都扔掉了。
给定奶牛的排列方式，请帮助 Farmer John 求出他会扔掉多少张孤独的照片。
如果两张照片以不同位置的奶牛开始或结束，则认为它们是不同的。
输入格式
输入的第一行包含 NN。
输入的第二行包含一个长为 NN 的字符串。如果队伍中的第 ii 头奶牛是更赛牛，则字符串的第 ii 个字符为 G。否则，第 ii 头奶牛是荷斯坦牛，该字符为 H。
输出格式
输出 Farmer John 会扔掉的孤独的照片数量。
数据范围
3≤N≤5×1053≤N≤5×105
输入样例：
5
GHGHG
输出样例：
3
样例解释
这个例子中的每一个长为 33 的子串均恰好包含一头更赛牛或荷斯坦牛——所以这些子串表示孤独的照片，并会被 Farmer John 扔掉。
所有更长的子串（GHGH、HGHG 和 GHGHG）都可以被接受。
题解：
统计有多少个长度大于等于3的字串满足G或H只出现一次。
思路：枚举一遍，对于每个字符G或者H，以串中某个G为例，满足在其左边有L个H，右边有R个H，分三种情况：
1.L和R都不为0，满足条件的子串数量为L*R（乘法定理）
2.L为0，数量为R
3.R为0，数量为L
完整代码如下：
#include <iostream>using namespace std;typedef long long LL;const int N = 5e5+10;int n;
int l[N], r[N];int main()
{scanf("%d", &n);scanf("%s", s);for (int i = 0, h = 0, g = 0; i < n; i ++ ){
//统计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 -- ){
//统计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);
//避免l[i]或r[i]为0时出现-1的情况printf("%lld\n", res);return 0;
}
