题意：给你一个长度为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的个数。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 100010 5 using namespace std; 6 7 int n,k,w; 8 char str[maxn]; 9 int a[maxn]; 10 int c[maxn]; 11 int dp[maxn]; 12 int sum[maxn]; 13 14 int lowbit(int x) 15 { 16 return x&-x; 17 } 18 19 void insert(int x,int d) 20 { 21 while(x<maxn) 22 { 23 c[x]+=d; 24 x+=lowbit(x); 25 } 26 } 27 28 int Getsum(int x) 29 { 30 int ans=0; 31 while(x>0) 32 { 33 ans+=c[x]; 34 x-=lowbit(x); 35 } 36 return ans; 37 } 38 39 40 int main() 41 { 42 while(scanf("%d%d%d",&n,&k,&w)!=EOF) 43 { 44 scanf("%s",str+1); 45 memset(sum,0,sizeof(sum)); 46 memset(a,0,sizeof(a)); 47 memset(c,0,sizeof(c)); 48 for(int i=1; i<=n; i++) 49 { 50 if(str[i]=='1') 51 { 52 insert(i,1); 53 } 54 } 55 for(int i=1; i<=k; i++) 56 { 57 int cnt=0; 58 for(int c=1; i+c*k-1<=n; c++) 59 { 60 cnt+=(str[i+c*k-1]-'0'); 61 dp[i+c*k-1]=cnt; 62 } 63 } 64 for(int i=1; i<=w; i++) 65 { 66 int l,r; 67 int ans=0; 68 scanf("%d%d",&l,&r); 69 int num=(r-l+1)/k; 70 ans+=Getsum(r)-Getsum(l-1); 71 ans-=dp[r]-dp[l-1]; 72 ans+=num; 73 ans-=dp[r]-dp[l-1]; 74 printf("%d ",ans); 75 } 76 } 77 return 0; 78 }