子串简写 树状数组 O(nlogn)复杂度 43ms

解题思路:

题目规定了，需要用找出以c1开头和c2开头并且长度需要超过k的子串数目，

考虑当结尾加入一个c2结尾的字符时,他会和所有开头为c1的,并且长度不超过k的字符形成子串，那么可以这样考虑每当扫描到一个c2字符就对位置i-k+1前面的c1字符数量求和，那么可以维护动态求和的数据结构就可以想到树状数组，

这就设计树状数组维护的是这个位置前的所有c1字符,遇到c1字符就在当前位置+1，每当遇到c2字符则求树状数组i-n+1位置的和

注意事项:

参考代码:

#include <iostream>

#include<vector>

#include<algorithm>

#include<string>

#include<queue>

#include<cstring>

#include<stack>

#include<math.h>

#define LL long long int

#define ll long long

#define ull unsigned long long

using namespace std;

ll n, m, k; int T, ncase = 0; const int N = 7e5 + 3;

ll a[N]; string str; char c1, c2;

#define lowbit(x)x&-x

void update(ll x, ll k)

{

    while (x <= str.size())

    {

        a[x] += k; 

        x += lowbit(x);

    }

}

ll get(ll x)

{

    ll ans = 0;

    while (x>0) {

        ans += a[x];

        x -= lowbit(x);

    }

    return ans;

}

int main()

{

    ios_base::sync_with_stdio(0);

    cin >> n;

    cin >> str;

    cin >> c1 >> c2;

    str = '0' + str;

     ll sum = 0;

    for (ll i = 1; i <= str.size(); i++)

    {

        if (str[i-1] == c1) {

            update(i, 1);

        }

        if (str[i-1] == c2) {

            sum += get(i-n+1);

        }

    }

    cout << sum;

    return 0;

}