CF1238D AB-String

Problem - 1238D - Codeforces

大致题意

定义“好的字符串”为：串中的所有字符都属于一个长度大于1的回文子串。（原题给出了数个样例）

给出一个仅包含字符‘A’，‘B’的字符串，求问有多少个子串是好的字符串。

解题思路

参考博客：[洛谷题解] CF1238D AB-string - yezhiyi9670's blog (ak-ioi.com)

观察字符串的性质。我们可以发现，对于任何一个子串\(S_{L...R} ,(3 \leq R - L + 1)\)，对于子串中的任意字符\(\in S_{L+1...R-1}\)，该字符都属于一个长度大于1的回文子串。原因如下。

对于\(S_{i} \in S_{L+1...R-1}\)，如果\(S_{i + 1} = S_{i - 1}\)，那么显然\(S_{i-1...i + 1}\)为一个回文串；如果\(S_{i-1}\neq S_{i+1}\)，那么\(S_{i-1} = S_{i}\)或\(S_{i+1} = S_{i}\)将满足一项，这样\(S_i\)也满足属于一个回文子串（长度为2）。

所以我们可以得到结论：对于一个子串\(S_{L...R}\)，如果\(S_L,S_R\)都分别属于一个回文子串，那么该子串合法。

假设当前位置为\(i\)，那么设上一次\(S_i\)出现的位置为\(pre[i]\)，那么可以证明\(S_{pre[i]...i}\)为一个右端点为\(c\)的最短回文子串。那么对于当前位置，我们就需要统计所有的位置\(j\)，满足\(\begin{equation} \begin{cases} y\leq x \\ pre[y] <= pre[x]\end{cases} \end{equation}\)。这是一个前缀求和的操作，我们可以用树状数组快速地实现。于是就可以愉快地完成这道题目

核心代码

/* Generated by powerful Codeforces Tool
 * You can download the binary file in here https://github.com/xalanq/cf-tool (Windows, macOS, Linux)
 * Author: icey_z
 * Time: 2022-07-04 10:16:54
 **/

#include <bits/stdc++.h>
#include <vector>
using namespace std;
using ll = long long;

const int maxn = 3e5;

struct BIT
{
    int  t[maxn + 10];
    void update(int i, int c)
    {
        for (; i <= maxn; i += i & -i)
            t[i] += c;
    }
    ll query(int i)
    {
        ll sum = 0;
        for (; i > 0; i -= i & -i)
            sum += t[i];
        return sum;
    }
} t1;

void solve()
{
    int    n;
    string s;
    cin >> n;
    cin >> s;
    s = " " + s;
    vector<int> pre(n + 10);
    int         posa = 0, posb = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'A') {
            pre[i] = posa;
            posa   = i;
        }
        else {
            pre[i] = posb;
            posb   = i;
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        if (pre[i]) {
            t1.update(pre[i], 1);
        }
        ans += t1.query(pre[i]);
    }
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}