HDU 3275 Light

题意很简单 给你一串长度为n只有0,1的字符串，每次操作固定操作m长度的子串 问至少多少次才能使字符串全为 1

一开始没啥思路 后来发现每次找到第一个 0 的位置再以他为起点进行更新，重复操作要么全为 1 要么无法更新（别问我为什么，这是我队友跟我说的，我负责码线段树

这题我觉得有两个坑点

1.当m==0 的时候 这还能玩？？一个字符都不让动 出题的人也是脑残，，，总是动一些小条件 总之这时候就输出他的其实状态 ，即如果全为 1 输出0 否则 输出-1

2.延迟更新的时候，这个就需要对线段树有一定的理解了 因为是延迟更新，在还未更新的时候可能存在对某一个区间多次标记 标记奇数次次就是0,1反转，偶数次就是不变咯 这里我对lazy标记进行异或，一切迎刃而解

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define root tree[id]
#define lson tree[id<<1]
#define rson tree[id<<1|1]

using namespace std;
const int maxn=100005;
int st,en;
struct segtree
{
    int le,ri;
    int sum,len,d;
} tree[maxn*4];
char ch[maxn];

void pushdown(int id)
{
    if(root.d&&root.le!=root.ri)
    {
        lson.sum=lson.len-lson.sum;
        rson.sum=rson.len-rson.sum;
        lson.d^=1;
        rson.d^=1;
        root.d=0;
    }
}

void build_tree(int id,int le,int ri)
{
    root.le=le,root.ri=ri,root.len=ri-le+1,root.d=0;
    if(le==ri)
    {
        root.sum=ch[le]-'0';
        return ;
    }
    int mid=(le+ri)>>1;
    build_tree(id<<1,le,mid);
    build_tree(id<<1|1,mid+1,ri);
    root.sum=lson.sum+rson.sum;
}

int query(int id,int le,int ri)
{
    int ans;
    if(root.len==root.sum) return 0;
    if(le==ri) return le;
    pushdown(id);
    int mid=(le+ri)>>1;
    if(ans=query(id<<1,le,mid)) return ans;
    if(ans=query(id<<1|1,mid+1,ri)) return ans;
    root.sum=lson.sum+rson.sum;
    return 0;
}

void update(int id,int le,int ri)
{
    if(st<=le&&ri<=en)
    {
        root.sum=root.len-root.sum;
        root.d^=1;
        return ;
    }
    pushdown(id);
    int mid=(le+ri)>>1;
    if(st<=mid) update(id<<1,le,mid);
    if(en>mid) update(id<<1|1,mid+1,ri);
    root.sum=lson.sum+rson.sum;
}

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(m==0&&n==0) break;
        getchar();
        scanf("%s",ch+1);
        build_tree(1,1,n);
        if(m==0)
        {
            if(tree[1].sum==tree[1].len) printf("0\n");
            else printf("-1\n");
            continue;
        }
        bool flag=true;
        int step=0;
        while(st=query(1,1,n))
        {
            en=st+m-1;
            if(en>n)
            {
                flag=false;
                break;
            }
            step++;
            update(1,1,n);
        }
        if(flag) printf("%d\n",step);
        else printf("-1\n");
    }
    return 0;
}