cf C. Inna and Candy Boxes

题意：给你一个长度为n的只含有1和0的字符串，w个询问，每次询问输入l,r；在[l,r]中在l+k-1、l+2*k-1、......r的位置都必须为1，如果不为1的，变成1，记为一次操作，其它的地方的都必须为0，不为0的地方要变成1，也记为一次操作，最后问在区间[l,r]最少几次操作。

思路：可以用树状数组记录在某个地方的右方有多少个1，然后在 预处理出从1，2，..k的为开头的在i+c*k-1的位置上前面有多少个1，最后的答案是拿走的1+添加的1，拿走的1的个数等于现有的1的个数-位置正确的1的个数。 添加的1的个数等于需要添加的个数的总数-位置正确的1的个数。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define maxn 100010

 using namespace std;

 int n,k,w;

 char str[maxn];

 int a[maxn];

 int c[maxn];

 int dp[maxn];

 int sum[maxn];

 int lowbit(int x)

 {

     return x&-x;

 }

 void insert(int x,int d)

 {

     while(x<maxn)

     {

        c[x]+=d;

        x+=lowbit(x);

     }

 }

 int Getsum(int x)

 {

     int ans=;

     while(x>)

     {

         ans+=c[x];

         x-=lowbit(x);

     }

     return ans;

 }

 int main()

 {

     while(scanf("%d%d%d",&n,&k,&w)!=EOF)

     {

          scanf("%s",str+);

          memset(sum,,sizeof(sum));

          memset(a,,sizeof(a));

          memset(c,,sizeof(c));

          for(int i=; i<=n; i++)

          {

             if(str[i]=='')

             {

                 insert(i,);

             }

          }

          for(int i=; i<=k; i++)

          {

              int cnt=;

              for(int c=; i+c*k-<=n; c++)

              {

                   cnt+=(str[i+c*k-]-'');

                   dp[i+c*k-]=cnt;

              }

          }

          for(int i=; i<=w; i++)

          {

              int l,r;

              int ans=;

              scanf("%d%d",&l,&r);

              int num=(r-l+)/k;

              ans+=Getsum(r)-Getsum(l-);

              ans-=dp[r]-dp[l-];

              ans+=num;

              ans-=dp[r]-dp[l-];

              printf("%d\n",ans);

          }

     }

     return ;

 }