bzoj 1230: [Usaco2008 Nov]lites 开关灯

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid int m = (l + r) >> 1
const int M = 1e5 + 10;
int lazy[M<<2],sum[M<<2];
void pushup(int rt){
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}

void pushdown(int l,int r,int rt){
    if(lazy[rt]){
        mid;
        sum[rt<<1] = (m-l+1)-sum[rt<<1];
        sum[rt<<1|1] = (r-m)-sum[rt<<1|1];
        lazy[rt<<1] ^= 1;
        lazy[rt<<1|1] ^= 1;
        lazy[rt] = 0;
    }
}

void update(int L,int R,int l,int r,int rt){
    if(L <= l&&R >= r){
        sum[rt] = (r-l+1)-sum[rt];
        lazy[rt]^=1;
        return ;
    }
    pushdown(l,r,rt);
    mid;
    if(L <= m) update(L,R,lson);
    if(R > m) update(L,R,rson);
    pushup(rt);
}

int query(int L,int R,int l,int r,int rt){
    if(L <= l&&R >= r){
        return sum[rt];
    }
    mid;
    pushdown(l,r,rt);
    int ret = 0;
    if(L <= m) ret += query(L,R,lson);
    if(R > m) ret += query(L,R,rson);
    return ret;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,m,op,x,y;
    cin>>n>>m;
    for(int i = 1;i <= m;i ++){
        cin>>op>>x>>y;
        if(op == 0){
            update(x,y,1,n,1);
        }
        else {
            cout<<query(x,y,1,n,1)<<endl;
        }
    }
    return 0;
}