[洛谷题解] CF1238D AB-string

发布于 2019-10-11  520 次阅读


题目链接:CF1238D AB-string


题目描述

一个好的字符串t(下标从1开始)满足:对于其中任意一个字符,都属于一个或多个长度大于1的回文子串。

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

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

  • t = AABBB(其中t_1t_2属于子串t_{1..2}t_3t_4t_5属于子串t_{3..5}

  • t = ABAA(其中t_1t_2t_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_jj尽可能小,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_ij>i的最小j

有了prevnext之后,我们就可以知道符合要求的子串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;
}

评测记录:R25031139


undefined