Codeforces Round #587 (Div. 3) F. Wi-Fi - 线段树维护DP

有n个房子在x轴，房子的状态可以用0，1表示：
0：不可以安装路由器
1：可以安装路由器
每个房子可以直接连接到互联网。第i个房子代价为i。也可以安装路由器第i个房子代价为i。但是路由器可以使[i-k, i+k]都连上网，求出所有房子全部连上网需要的最小代价。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=2e5+7;
const LL INF=1e18;

LL a[N], f[N][2];
struct SegTree {
    LL T[N<<2];
    SegTree () { memset(T,0x3f,sizeof(T)); }
    inline void pushup(int o) { T[o]=min(T[o<<1],T[o<<1|1]); }
    void add(int o,int l,int r,int pos,LL v){//修改 T[o]=v
        if(l==r) { T[o]=v; return; }
        int mid=l+r>>1;
        pos<=mid ? add(o<<1,l,mid,pos,v) : add(o<<1|1,mid+1,r,pos,v);
        pushup(o);
    }
    LL query(int o,int l,int r,int ql,int qr){//查询区间最大值

        if(l>qr||r<ql) return INF;
        if(l>=ql&&r<=qr) return T[o];
        int mid=l+r>>1; return min(query(o<<1,l,mid,ql,qr),query(o<<1|1,mid+1,r,ql,qr));
    }

}T1, T2;

int main(){

    memset(f, 0x3f, sizeof(f));
    int n, k; scanf("%d%d", &n, &k);
    for(int i=2; i<=n+1; i++){
        scanf("%1d", &a[i]);
    }

    f[1][1]=0; T2.add(1, 1, n+1, 1, min(f[1][0], f[1][1]));
    for(int i=2; i<=n+1; i++){
        f[i][0]=T1.query(1, 1, n+1, max(1, i-k), max(i-1, 1));
        if(a[i]==1){
            f[i][1]=T2.query(1, 1, n+1, max(1, i-k-1), max(i-1, 1))+i-1;
            T1.add(1, 1, n+1, i, f[i][1]);
        }
        else{
            f[i][1]=min(f[i-1][0], f[i-1][1])+i-1;
        }
        T2.add(1, 1, n+1, i, min(f[i][0], f[i][1]));
    }
    printf("%lld\n", min(f[n+1][0], f[n+1][1]));

    return 0;
}