[洛谷题解] CF1238D AB-string • KMnO4y

题目链接：CF1238D AB-string ↗

题目描述#

一个好的字符串 $t$ （下标从1开始）满足：对于其中任意一个字符，都属于一个或多个长度大于 $1$ 的回文子串。

回文串是从前向后或从后向前读都一样的字符串。比如A，BAB，ABBA，BAABBBAAB都是回文串，而AB，ABBBAA，BBBA都不是。

下面是好的字符串的例子：

$t$ = AABBB（其中 $t_1$ 和 $t_2$ 属于子串 $t_{1..2}$ ， $t_3$ ， $t_4$ 和 $t_5$ 属于子串 $t_{3..5}$ ）
$t$ = ABAA（其中 $t_1$ ， $t_2$ 和 $t_3$ 属于 $t_{1..3}$ ， $t_4$ 属于子串 $t_{3..4}$ ）
$t$ = AAAAA（所有字符属于回文子串 $t_{1..5}$ ）

给你一个长度 $n$ 的字符串 $s$ ，请计算其好的子串的数量。

输入格式#

第一行一个整数 $n\ (1 \leq n \leq 3\cdot 10^5)$ ，表示 $s$ 的长度。

第二行一个仅由字符’A’和’B’构成的字符串 $s$ 。

输出格式#

一个整数， $s$ 中好的子串的数量。

样例解释#

样例1：有 $s_{1..2}$ ， $s_{1..4}$ ， $s_{1..5}$ ， $s_{3..4}$ ， $s_{3..5}$ ， $s_{4..5}$

样例2：有 $s_{1..2}$ ， $s_{2..3}$ ， $s_{1..3}$

解题思路#

注意：字符串只由’A’和’B’构成。字符下标从 $1$ 开始。

我们考虑一个字符串中不在两端的字符。容易发现，这个字符一定属于一个长度大于 $1$ 的回文子串。设这个字符为 $t_i$

如果 $t_{i-1} =\not t_{i+1}$ ，那么 $t_{i-1}$ 和 $t_{i+1}$ 中必有一个和 $t_i$ 相等。不妨令 $t_i = t_{i+1}$ ，那么 $t_i$ 就属于 $t_{i..i+1}$ 这个回文子串。
如果 $t_{i-1} = t_{i+1}$ ，那么 $t_i$ 属于 $t_{i-1..i+1}$ 这个回文子串。

因此只需考虑两端的字符是否属于一个长度大于 $1$ 的回文子串（换句话说，是否同时有一个回文前缀和回文后缀，前缀和后缀包含本身），就可以判断一个字符串是不是好的了。

接下来我们考虑在字符串 $s$ 上统计。

假设当前考虑的子串从 $s_i$ 开始。那么，可能存在一个字符 $s_j$ （ $j$ 尽可能小， $j>i$ ），使得如果当前子串结束点在 $s_j$ 之后，那么这个字符串就有一个回文前缀。

如果存在一个 $j$ ，那么定义 $next[i] = j$ 。
否则， $next[i] = 0$

很显然， $s_{i..next[i]}$ 是以 $s_i$ 开头的，最短的回文子串。

相应地，我们定义 $prev[]$ ，使 $s_{prev[i]..i}$ 是 $s_i$ 结尾的，最短的回文子串。很显然：

如果存在 $j$ 使 $next[j]=i$ ，那么 $prev[i] = j$
否则， $prev[i] = 0$

那么如何求 $next$ 数组呢？

由于字符串中只存在’A’和’B’， $next[i]$ 等于满足 $s_j = s_i$ 和 $j>i$ 的最小 $j$ 。

有了 $prev$ 和 $next$ 之后，我们就可以知道符合要求的子串 $s_{x..y}$ 满足下面的条件：

$x \leq prev[y]$
$next[x] \leq y$

于是我们可以用树状数组1 ↗实现统计（树状数组是一种维护序列的 $log(n)$ 数据结构，功能是：单点修改，求前缀和）。细节见代码。

// status: [Accepted]
// oj:     [luogu]

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll

const int MAXN = 300002;
// next数组
int nextMatch[MAXN];
// prev数组
int prevMatch[MAXN];
int n;
char s[MAXN];

// 树状数组1
struct WxwAkIoi {
    int data[MAXN];
    static inline int lowbit(int x) {return x&-x;}
    void update(int p,int v) {
        for(int i=p;i<MAXN;i+=lowbit(i)) {
            data[i] += v;
        }
    }
    int query(int p) {
        int ret = 0;
        for(int i=p;i;i-=lowbit(i)) {
            ret += data[i];
        }
        return ret;
    }
}tr;

// 预处理next数组
void pre() {
    int prevA = -1;
    int prevB = -1;
    for(int i=1;i<=n;i++) {
        if(s[i] == 'A') {
            if(prevA != -1) nextMatch[prevA] = i;
            prevA = i;
        }
        else if(s[i] == 'B') {
            if(prevB != -1) nextMatch[prevB] = i;
            prevB = i;
        }
        else {
            cerr<<"DDoSForces AK IOI";
            exit(28403);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin>>n;
    cin>>(s+1);
    n = strlen(s+1);

    pre();

    // 计算prev数组
    for(int i=1;i<=n;i++) {
        if(nextMatch[i] != 0) {
            prevMatch[nextMatch[i]] = i;
        }
    }

    // 统计
    int ans = 0;
    for(int i=1;i<=n;i++) {
        if(prevMatch[i]) {
            // next[prev[i]] = i，而对于之后的i，有next[prev[i]] < new_i。
            // 这就满足了 next[x] <= y 的性质
            tr.update(prevMatch[i],1);
        }
        // 求树状数组从1到prev[i]的和。
        // 这就满足了 x <= prev[y] 的性质
        ans += tr.query(prevMatch[i]);
    }

    cout<<ans<<endl;
}

cpp

评测记录：R25031139 ↗