题解 P2574 【XOR的艺术】
遇事不决先分块
分块，即可感受暴力的美感，也可感受AC的快感
用分块维护区间和，当然在维护区间的lazy标志，用0表该区间未有标志，1表该区间有标志。
接下来就可以大力分块啦：
我的分块打的比较暴力，在处理残块是直接下放标记，复杂度不是很优但还是可以接受(2.01s)
再不懂代码里有注释：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 300500
using namespace std;
int n,m;
char s[N];//将01字符串读入
int a[N],sum[N],lz[N];//区间和与lazy标志数组
int tag[N],L[N],R[N];
//分块 tag[i]表i所在的块的编号，L[i]和R[i]为第i块的左右端点在原数组的位置
//下放标记的函数，此处为暴力修改
inline void Update(int k) {
if(lz[tag[k]]) {
sum[tag[k]] = R[tag[k]] - L[tag[k]] + 1 - sum[tag[k]];
//异或的下放，把区间和中1变0，直接减去即可
for(int i = L[tag[k]];i <= R[tag[k]];i ++) a[i] ^= 1;
lz[tag[k]] = 0;//下放后标志消失
}
}
//修改函数
inline void Change(int l,int r) {
if(tag[l] == tag[r]) { //对于残块暴力即可
Update(l);
for(int i = l;i <= r;i ++)
sum[tag[l]] -= a[i],
a[i] ^= 1,
sum[tag[l]] += a[i];
return ;
}
Update(l);
for(int i = l;i <= R[tag[l]];i ++)
sum[tag[l]] -= a[i], a[i] ^= 1, sum[tag[l]] += a[i];
for(int i = tag[l] + 1;i < tag[r];i ++) {
if(lz[i]) lz[i] = 0;
else lz[i] = 1;
//根据异或的性质之前有标记的取消，没有的加上
}
Update(r);
for(int i = L[tag[r]];i <= r;i ++)
sum[tag[r]] -= a[i], a[i] ^= 1, sum[tag[r]] += a[i];
}
//求和函数
inline int Ask(int l,int r) {
int res = 0;
if(tag[l] == tag[r]) {//暴力统计
Update(l);
for(int i = l;i <= r;i ++) res += a[i];
return res;
}
Update(l);
for(int i = l;i <= R[tag[l]];i ++) res += a[i];
for(int i = tag[l] + 1;i < tag[r];i ++) {
if(lz[i]) res += R[i] - L[i] + 1 - sum[i];
else res += sum[i];
//对于整块，要考虑是否有标记
}
Update(r);
for(int i = L[tag[r]];i <= r;i ++) res += a[i];
return res;
}
int main() {
scanf("%d%d%s",&n,&m,s + 1); int len = sqrt(n);
for(int i = 1;i <= n;i ++) a[i] = (s[i] == '1');
//对于分块的预处理
for(int i = 1;i <= n;i ++) tag[i] = (i - 1) / len + 1;
for(int i = 1;i <= tag[n];i ++)
L[i] = R[i - 1] + 1,R[i] = min(n,L[i] + len - 1);
for(int i = 1;i <= tag[n];i ++)
for(int j = L[i];j <= R[i];j ++)
sum[i] += a[j];
//求区间和
for(int i = 1;i <= m;i ++) {
int opt,l,r; scanf("%d%d%d",&opt,&l,&r);
if(opt == 0) Change(l,r);
else printf("%d\n",Ask(l,r));
}
return 0;
}