@[Steve_braveman](/space/show?uid=96570)
```
#include <cstdio>
using namespace std;
const int maxn = 200010;
int n, m, SegTree[maxn << 2], lazy[maxn << 2], size[maxn << 2];
int lson(int x)
{
return x << 1;
}
int rson(int x)
{
return x << 1 | 1;
}
void pushup(int x)
{
SegTree[x] = SegTree[lson(x)] + SegTree[rson(x)];
}
void pushdown(int x)
{
if(lazy[x])
{
lazy[lson(x)] ^= 1;
lazy[rson(x)] ^= 1;
SegTree[lson(x)] = size[lson(x)] - SegTree[lson(x)];
SegTree[rson(x)] = size[rson(x)] - SegTree[rson(x)];
lazy[x] = 0;
}
}
void build(int l, int r, int p)
{
size[p] = r - l + 1;
if(l > r)return ;
if(l == r)
{
scanf("%1d", &SegTree[p]);
return ;
}
int mid = (l + r) >> 1;
build(l, mid, lson(p));
build(mid + 1, r, rson(p));
pushup(p);
}
void update(int ul, int ur, int l, int r, int p)
{
if(l >= ul && r <= ur)
{
lazy[p] ^= 1;
SegTree[p] = size[p] - SegTree[p];
return ;
}
pushdown(p);
int mid = (l + r) >> 1;
if(ul <= mid)update(ul, ur, l, mid, lson(p));
if(ur > mid)update(ul, ur, mid + 1, r, rson(p));
pushup(p);
}
int query(int ql, int qr, int l, int r, int p)
{
if(ql <= l && r <= qr)
{
return SegTree[p];
}
pushdown(p);
int mid = (l + r) >> 1;
int sum = 0;
if(ql <= mid)sum += query(ql, qr, l, mid, lson(p));
if(qr > mid) sum += query(ql, qr,mid+1,r, rson(p));
return sum;
}
int main()
{
scanf("%d%d\n", &n, &m);
build(1, n, 1);
while(m--)
{
int p, l, r;
scanf("%d%d%d", &p, &l, &r);
if(p)
{
printf("%d\n", query(l, r, 1, n, 1));
} else {
update(l, r, 1, n, 1);
}
}
return 0;
}
```
by Le_temps_des_fleurs @ 2018-10-22 18:56:39
所以说......分块大法吼啊!
by Juan_feng @ 2018-10-22 18:57:09
跑的贼快而且代码量还小qwqwq
by Juan_feng @ 2018-10-22 18:58:09
@[Neptune_Disaster](/space/show?uid=108185) 这是我的RE代码(个人喜欢用`struct`封装起来)
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstring>
#define ll long long
#define MAXN 200005
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
struct Segtree {
ll a[MAXN] , b[MAXN << 2] , lazy[MAXN << 2];
inline void pd(ll p) {
b[p] = b[ls(p)] + b[rs(p)];
}
void build(ll l , ll r , ll p) {
if (l == r) {
b[p] = a[l];
return;
}
ll m = (l + r) >> 1;
build(l , m , ls(p));
build(m + 1 , r , rs(p));
pd(p);
}
inline void pushd(ll p , ll l) {
if (lazy[p]) {
lazy[ls(p)] ^= 1;
lazy[rs(p)] ^= 1;
b[ls(p)] = (l - (l >> 1)) - b[ls(p)];
b[rs(p)] = (l >> 1) - b[rs(p)];
lazy[p] = 0;
}
}
void up(ll x , ll y , ll l , ll r , ll p) {
pushd(p , r - l + 1);
if (x <= l && y >= r) {
lazy[p] ^= 1;
b[p] = r - l + 1 - b[p];
return;
}
ll m = (l + r) >> 1;
if (x <= m) up(x , y , l , m , ls(p));
if (y > m) up(x , y , m + 1 , r , rs(p));
pd(p);
}
ll sum(ll x , ll y , ll l , ll r , ll p) {
ll s = 0;
if (x <= l && y >= r) {
return b[p];
}
pushd(p , r - l + 1);
ll m = (l + r) >> 1;
if (x <= m) s += sum(x , y , l , m , ls(p));
if (y > m) s += sum(x , y , m + 1 , r , rs(p));
return s;
}
}tree;
ll n , m , l , r , k;
char s;
int main() {
scanf("%lld%lld" , &n , &m);
for (ll i = 1 ; i <= n ; i++) {
std::cin >> s;
tree.a[i] = s - '0';
}
tree.build(1 , n , 1);
while (m--) {
scanf("%lld%lld%lld" , &k , &l , &r);
if (k == 0) {
tree.up(l , r , 1 , n , 1);
}
else {
printf("%lld\n" , tree.sum(l , r , 1 , n , 1));
}
}
}
```
by RiverFun @ 2018-10-22 18:58:26
@[Steve_braveman](/space/show?uid=96570) ~~没准struct出锅~~
by Le_temps_des_fleurs @ 2018-10-22 18:58:54
@[Neptune_Disaster](/space/show?uid=108185) ~~那海星~~
by RiverFun @ 2018-10-22 18:59:31
哪里用开ll了,开4倍空间不就够了
by ComplexPug @ 2018-10-30 10:50:54
@[Steve_braveman](/space/show?uid=96570) @[Juan_feng](/space/show?uid=66965) 指针或动态开点了解一下
by MrNullbody @ 2019-02-02 14:11:13
@[lyonlu](/space/show?uid=82854) 时隔三个多月突然被at......
by Juan_feng @ 2019-02-02 14:46:33
@[lyonlu](/space/show?uid=82854) ???????
by RiverFun @ 2019-02-02 16:47:12