传送门
只需要对懒标记做文章，每次xor1，并且我们可以发现，一个区间xor1后权值和变为了l-r+1-sum，知道这两个这道题就可做了。
#include<bits/stdc++.h> #define N 200005 using namespace std; int n,m,a[N]; struct node { int l,r,v,lazy; }tree[4*N]; inline void build(int l,int r,int now) { tree[now].l=l,tree[now].r=r,tree[now].lazy=0; if(l==r) { tree[now].v=a[l]; return; } int m=(l+r)>>1; build(l,m,2*now); build(m+1,r,2*now+1); tree[now].v=tree[2*now].v+tree[2*now+1].v; } inline void push_down(int now) { if(tree[now].lazy==1) { tree[2*now].v=(tree[2*now].r-tree[2*now].l+1)-tree[2*now].v; tree[2*now+1].v=(tree[2*now+1].r-tree[2*now+1].l+1)-tree[2*now+1].v; tree[2*now].lazy^=1; tree[2*now+1].lazy^=1; tree[now].lazy=0; } } inline void modify(int l,int r,int now) { if(tree[now].l>=l&&tree[now].r<=r) { tree[now].v=(tree[now].r-tree[now].l+1)-tree[now].v; tree[now].lazy^=1; return; } push_down(now); int m=(tree[now].l+tree[now].r)>>1; if(l<=m) modify(l,r,2*now); if(r>m) modify(l,r,2*now+1); tree[now].v=tree[2*now].v+tree[2*now+1].v; } int ans=0; inline void query(int l,int r,int now) { if(tree[now].l>=l&&tree[now].r<=r) { //cout<<now<<" "<<tree[now].l<<" "<<tree[now].r<<endl; ans+=tree[now].v; return; } push_down(now); int m=(tree[now].l+tree[now].r)>>1; if(l<=m) query(l,r,2*now); if(r>m) query(l,r,2*now+1); } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m; for(int i=1;i<=n;i++) { char ch; cin>>ch; a[i]=int(ch-'0'); } build(1,n,1); for(int i=1;i<=m;i++) { int opt,l,r; cin>>opt>>l>>r; if(opt==0) { modify(l,r,1); } if(opt==1) { query(l,r,1); cout<<ans<<endl; ans=0; } } return 0; }