根据题意容易列出 \(O(n^2)\) DP.

设 \(f_i\) 表示前 \(i\) 个位置最少要划分多少段，则有：

\(f_i = \displaystyle \min_{(A or B) and C} \{ f_{j-1} + 1 \}\).

其中，条件 A 为 区间 \([i,j]\) 中全都是同一种数字。

条件 B 为 区间中两种数字个数之差不超过 \(k\).

条件 C 为 \(i-m \le j < i \).

条件 A,C 都是平凡的，同时满足这两种条件的转移可以直接用单调队列维护。对于条件 B ，考虑使用 \(+1,-1\) 前缀和的套路进行刻化。

设 '0' 为 +1，'1' 为 -1，做前缀和，那么条件 B 就等价于 \(-k \le (pre_i-pre_{j-1}) \le k\),化简得到 \(pre_{j-1} \in [pre_i-k,pre_i+k]\).

这样，同时满足条件 B 就也相当于限制了一个关于 pre 的区间，同时满足条件 B,C 的点集是一个二维平面上的矩形，可以直接 扫描线 并用 线段树+multiset 维护单点插入，单点删除和求区间最小值进行转移，multiset 只需要挂在线段树的叶子节点上，复杂度为 \(O(nlogn)\).

线段树对于普及组来说有些超纲，但利用一些性质，可以省去线段树并将这题的复杂度优化到 \(O(n)\).

首先可以发现：如果我们让每个 multiset 保持单调性，即插入一个节点时删除所有在它之前插入比它劣的值，那么在任意时刻，同一个 \(pre\) 对应的 multiset 里面的两个位置 \(j \le i\) ,一定满足 \(0 \le f_i - f_j \le 1\).

证明很显然，因为 \(f_i\) 一定可以从 \(pre\) 值相同的位置 \(j\) 转移过来，也就是有 \(f_i = min(f_i,f_j+1)\).

于是我们可以不再使用 multiset ，而是直接维护一个 \(pre\) 对应的 dp 值的最小值，最小值最晚出现时间和次小值最晚出现时间，消去了动态维护单点最小值的 \(\log\).

另外的 \(\log\) 来源于线段树维护关于 \(pre\) 的区间最小值。朴素的带修区间最小值并没有线性做法，但这题有很强的性质。

性质1：由于前缀和是 \(+1,-1\) 的形式，相邻两次询问最小值的区间左右端点一定相差不超过 1.

性质2：\(\forall 0 \le i \le n,0 \le f_i \le n\).

性质3：\(f_{i+1} - f_i \le 1\).(第 \(i+1\) 个位置单独划分一段，可以直接转移过来)。

性质 1 提示我们可以根据上一次询问暴力移动指针来得到下一次询问的结果。但这还不够，因为维护的最小值信息并不能在有删除操作的情况下直接维护。

但是根据性质 2 ，我们可以利用桶来维护最小值的个数，每次向桶中放入一个更优的元素时，将答案指针指向新的最小值。当最小值被删除后，若当前最小值的桶中剩余为 0 ，则直接将最小值的指针 +1.

指针 +1 后桶中元素依然为 0 怎么办？

根据性质 3 ，\(f_i\) 可以通过另一种转移被 \(f_{i-1}\) 更新到，所以 +1 以后如果为 0 也不管了，毕竟答案不会比 +1 更劣。

根据这 3 条性质，我们将区间最小值也优化到了 \(O(n)\) 时间复杂度。

至此，总复杂度被降为了 \(O(n)\).

#include<bits/stdc++.h>
using namespace std;
const int INF=1e7,N=2e7+10;
int n,m,k,pre[N],f[N];
int fs0[N],fs1[N],tim0[N],tim1[N];
int que[N],l=1,r=1;
string s;
void insert(int x){
    if(s[x]!=s[x-1]){
        l=1,r=0;
    }
    while(l<=r&&f[que[r]]>=f[x]){
        r--;
    }
    que[++r]=x;
    while(que[l]<=x-m){
        l++;
    }
    return;
}
int t[N],prel=1,prer,minf=INF;
void upd(int x,int y,int tim){
    if(prel<=x&&x<=prer){
        t[fs0[x]]--;
    }
    if(y<=fs0[x]){
        fs0[x]=y,tim0[x]=tim;
        fs1[x]=INF;
    }else if(y<=fs1[x]){
        fs1[x]=y,tim1[x]=tim;
    }
    if(prel<=x&&x<=prer){
        t[fs0[x]]++;
    }
    return;
}
void del(int x,int y,int tim){
    if(prel<=x&&x<=prer){
        t[fs0[x]]--;
    }
    if(y==fs0[x]&&tim==tim0[x]){
        fs0[x]=fs1[x],tim0[x]=tim1[x];
        fs1[x]=INF;
    }else if(y==fs1[x]&&tim==tim1[x]){
        fs1[x]=INF;
    }
    if(prel<=x&&x<=prer){
        t[fs0[x]]++;
    }
    return;
}
inline int calc(int L,int R){
    while(prel<L){
        t[fs0[prel]]--,prel++;
    }
    while(prer>R){
        t[fs0[prer]]--,prer--;
    }
    while(prel>L){
        prel--,t[fs0[prel]]++;
        if(fs0[prel]<minf&&t[fs0[prel]]>0){
            minf=fs0[prel];
        }
    }
    while(prer<R){
        prer++,t[fs0[prer]]++;
        if(fs0[prer]<minf&&t[fs0[prer]]>0){
            minf=fs0[prer];
        }
    }
    if(t[minf]==0){
        minf++;
    }
    return minf;
}
int main(){
    freopen("strand.in","r",stdin); 
    freopen("strand.out","w",stdout); 
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k>>s;
    pre[0]=n;
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+((s[i-1]=='1')?1:-1);
    }
    for(int i=0;i<=(n<<1);i++){
        fs0[i]=fs1[i]=INF;
    }
    t[INF]=INF;
    upd(n,0,0);
    for(int i=1;i<=n;i++){
        f[i]=(l<=r)?f[que[l]]:INF;
        f[i]=min(f[i],calc(max(0,pre[i]-k),min(n<<1,pre[i]+k)))+1;
        insert(i),upd(pre[i],f[i],i);
        if(i>=m){
            del(pre[i-m],f[i-m],i-m);
        }
    }
    cout<<f[n]<<'\n';
    return 0;
}