TeamsCode 2021. P. ABC (Hard Version)

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define pb push_back
#define int long long
#define uint __int128
#define mp make_pair
#define left left_compile
#define right right_compile

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

const int INF = (int)1e18;
const int md = (int)1e9 + 7;
const int MAXN = (int)100;
const int N = (int)2e5 + 111;
//const int L = 20;
const int debug = 0;
const long double eps = 1e-7;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

struct DSU{
    int n;
    vector<int> parent;
    vector<int> sz;
    vector<int> deep;
    DSU(int nn){
        n = nn;
        parent.resize(n+1);
        sz.resize(n+1,1);
        deep.resize(n+1,1);
        for(int i = 0; i <= n; i++)
            parent[i] = i, sz[i] = 1, deep[i] = 1;
    }
    int find_parent(int x){
        if(parent[x] == x)
            return x;
        return parent[x] = find_parent(parent[x]);
    }
    void union_sets(int a,int b){
        a = find_parent(a);
        b = find_parent(b);
        if(a == b)
            return;
        if(deep[a] <= deep[b])
            parent[a] = b, sz[b] += sz[a], deep[b] = max(deep[b],deep[a]+1);
        else
            parent[b] = a, sz[a] += sz[b], deep[a] = max(deep[a],deep[b]+1);
    }
    bool connected(int a,int b){
        return find_parent(a) == find_parent(b);
    }
};

//typedef tree<
//int,
//null_type,
//less_equal<int>,
//rb_tree_tag,
//tree_order_statistics_node_update>
//ordered_set;

int bpow(int a,int b){
    if(b == 0)
        return 1ll;
    if(b % 2 == 0){
        int t = bpow(a,b/2) % md;
        return (t * t) % md;
    }
    return (a * bpow(a,b-1)) % md;
}

int inv(int a){ /// return 1/a by PRIME modulo md
    return bpow(a,md-2);
}

//void myerase(ordered_set& st, int t){
//    int r = st.order_of_key(t);
//    ordered_set::iterator it = st.find_by_order(r);
//    st.erase(it);
//    return;
//}

void init(){
    return;
}

void add(int& a,int b){
    a = (a + b >= md ? a + b - md : a + b);
}

void sub(int& a,int b){
    a = (a < b ? a - b + md : a - b);
}

int pref[3][N];
int cnt[3];

int t[3][4*N];
int dp[N];

void build(int v,int l,int r){
    if(l == r){
        t[0][v] = t[1][v] = t[2][v] = -INF;
        return;
    }
    if(l > r)
        return;
    int m = (l + r) / 2;
    build(v<<1,l,m);
    build(v<<1|1,m+1,r);
    t[0][v] = t[1][v] = t[2][v] = -INF;
    return;
}

int get(int v,int l,int r,int tl,int tr,int id){
    if(l > r || tl > tr)
        return -INF;
    if(l == tl && r == tr)
        return t[id][v];
    int m = (l + r) / 2;
    return max(get(v<<1,l,m,tl,min(tr,m),id),get(v<<1|1,m+1,r,max(tl,m+1),tr,id));
}

void upd(int v,int l,int r,int pos,int nw,int id){
    if(l == r){
        t[id][v] = nw;
        return;
    }
    if(l > r)
        return;
    int m = (l + r) / 2;
    if(pos <= m)
        upd(v<<1,l,m,pos,nw,id);
    else
        upd(v<<1|1,m+1,r,pos,nw,id);
    t[id][v] = max(t[id][v<<1],t[id][v<<1|1]);
    return;
}

void solve_case(){
    int n,k;
    cin >> n >> k;

    string s;
    cin >> s;

    for(int i = 1; i <= n; i++){
        cnt[s[i-1]-'A']++;
        for(int j = 0; j < 3; j++){
            if(cnt[j] == max({cnt[0],cnt[1],cnt[2]})){
                pref[j][i] = 1;
            }
        }
    }

    for(int i = 1; i < N; i++){
        for(int j = 0; j < 3; j++){
            pref[j][i] += pref[j][i-1];
        }
    }

    build(1,0,N-1);

    upd(1,0,N-1,0,0,0);
    upd(1,0,N-1,0,0,1);
    upd(1,0,N-1,0,0,2);

    int ans = 0;

    for(int i = k; i <= 2 * n; i++){
        for(int j = 0; j < 3; j++){
            int t = get(1,0,N-1,0,i-k,j) + pref[j][i];
            dp[i] = max(dp[i],t);
            ans = max(ans,dp[i]);
        }
        for(int j = 0; j < 3; j++){
            upd(1,0,N-1,i,dp[i]-pref[j][i],j);
        }
    }

    cout << ans;

    return;
}

signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//    freopen("internship.in","r",stdin);
//    freopen("internship.out","w",stdout);

//    init();

    int tests = 1;
//    cin >> tests;

    for(int _ = 1; _ <= tests; _++){
        solve_case();
    }

    return 0;
}

/*

4 <=> 100
7 <=> 111
3 <=> 011


0100
0111

0100
0101

111100111100

*/