题意

给出一个字符串,求出每次反转后字符串中 $kky$ 子串的数量

模拟

遇到字符串类型的题目我们都可以先通过模拟寻找解题思路.我们可以把每次反转后的字符串看作一个新的字符串,想要找出全部 $kky$ 子串的数量,可以通过字符串匹配,代码如下:

for(int i = 1 ; i <= n ; i ++ ) 
        if(s[i] == 'k') for(int j = i + 1 ; j <= n ; j ++ ) 
            if(s[j] == 'k') for(int k = j + 1 ; k <= n ; k ++ ) 
                if(s[k] == 'y') ans ++ ;

代码虽然写起来简单,但是他的时间复杂度却是 $O(q \times n ^ 3)$ ,显而易见的远远超过了我们预想中的时间复杂度.那么如何对其进行优化呢?

对 $kky$ 子串简单的分析可以发现,想要找到所有的 $kky$ 我们只需要找到字符串中所有 $y$ 前面的 $k$ 的个数,就可以通过组合数轻松求出每个 $y$ 所能匹配的 $kky$ 的数量.

这样的优化让我们很容易就想到了刚学的新算法 前缀和 :

前缀和优化

主要代码如下:

int cnt_k[100005] ;
int ans = 0 ;
for(int i = 1 ; i <= n ; i ++ ) {
    //前缀和求出前i字符中k的个数
    if(s[i] == 'k') cnt_k[i] = cnt_k[i-1] + 1 ;
    else cnt_k[i] = cnt_k[i-1] ;
    
    //组合数求出当前可匹配的kky数量
    if(s[i] == 'y') ans += ((cnt_k[i]-1) * cnt_k[i] / 2);
}

借用前缀和我们将时间复杂度优化到了$O(q \times n)$ ,但是我们发现题目给出的数据范围仅仅优化到这一步还是会超时.但是我们发现 $l$ ~ $r$ 的范围只有 $10 ^ 3$ ,再加上每次反转字符串并不会影响原字符串.可以很容易的想到先求出原字符串每个 $y$ 所能匹配的 $kky$ 数量, 再讨论 $l$ ~ $r$ 中的情况;

于是我们可以进一步优化

前缀和+前缀和优化

int cnt_k[100005] ;
int cnt_y[100005] ;
int ans = 0 ;
for(int i = 1 ; i <= n ; i ++ ) {
    //前缀和求出前i字符中k的个数
    if(s[i] == 'k') cnt_k[i] = cnt_k[i-1] + 1 ;
    else cnt_k[i] = cnt_k[i-1] ;
    
    //组合数求出当前i字符中存在的kky数量
    if(s[i] == 'y') cnt_y[i] = cnt_y[i-1] + ((cnt_k[i]-1) * cnt_k[i] / 2);
    else cnt_y[i] = cnt[i-1] ;
}

这样以来我们通过前缀和预处理找到了所有 $kky$ 的数量.

在进行$l$ ~ $r$ 的讨论:

while (q --) {
        //求出l~r范围外kky的数量
        ans = cnt_y[l-1] + cnt_y[n] - cnt_y[r] ;
        //求反转后每个y所能匹配的kky数量
        cnt = cnt_k[l - 1] ;
        for(int i = r ; i >= l ; i -- ) {
            if(s == k) cnt ++ ;
            if(s == y) ans += ((cnt - 1) * cnt / 2) ;
        }
    }

如此一来我们的时间复杂度可以缩减到 $O(q \times (r-l) )$ .

本题考查同学们的字符串处理能力和思维,以及对前缀和的运用.