原题
//codevs1690 开关灯 #include<iostream> #include<cstdio> #include<cstring> #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 using namespace std; int n,m; int sum[500100],col[500100]; void pushup(int pos){sum[pos]=sum[pos<<1]+sum[pos<<1|1];} void pushdown(int pos,int len) { if (col[pos]) { col[pos<<1]+=col[pos];col[pos<<1|1]+=col[pos]; if(col[pos]&1) sum[pos<<1]=len-(len>>1)-sum[pos<<1],sum[pos<<1|1]=(len>>1)-sum[pos<<1|1]; col[pos]=0; } } void update(int LL,int RR,int l,int r,int pos) { if (LL<=l&&r<=RR) { col[pos]+=1;sum[pos]=(r-l+1)-sum[pos]; return; } pushdown(pos,r-l+1); int m=(l+r)>>1; if (LL<=m) update(LL,RR,lson); if (RR>m) update(LL,RR,rson); pushup(pos); } int query(int LL,int RR,int l,int r,int pos) { if (!sum[pos])return 0; if (LL<=l&&r<=RR) return sum[pos]; pushdown(pos,r-l+1);//更新的时候也要加！更新的时候也要加！更新的时候也要加！ int m=(l+r)>>1,ret=0; if (LL<=m) ret+=query(LL,RR,lson); if (RR>m) ret+=query(LL,RR,rson); return ret; } int main() { memset(sum,0,sizeof(sum));memset(col,0,sizeof(col)); scanf("%d%d",&n,&m); while(m--) { int order,a,b; scanf("%d%d%d",&order,&a,&b); if (!order) update(a,b,1,n,1); else printf("%d\n",query(a,b,1,n,1)); } return 0; }
