萌新刚学线段树,10pts求救
#include<bits/stdc++.h>
#define maxn 200000
using namespace std;
typedef long long ll;
string s;
ll n,m,a[maxn+5],OP,L,R;
struct Tree{
ll l,r,sum;
bool lazy;
Tree *left,*right;
};
inline Tree* newtree(){return new Tree();}
inline void build(Tree** cur,ll l,ll r){
(*cur)->sum=(*cur)->lazy=0;(*cur)->l=l,(*cur)->r=r;
if(l+1<r){
(*cur)->left=newtree(),(*cur)->right=newtree();
build(&((*cur)->left),l,(l+r)/2);
build(&((*cur)->right),(l+r)/2,r);
(*cur)->sum=(*cur)->left->sum+(*cur)->right->sum;
}else{
(*cur)->left=(*cur)->right=NULL;(*cur)->sum=a[l];
}
}
inline void update(Tree *cur){
cur->left->sum=cur->left->r-cur->left->l-cur->left->sum;
cur->right->sum=cur->right->r-cur->right->l-cur->right->sum;
cur->left->lazy=cur->right->lazy=1;
}
inline ll query(Tree* cur,ll l,ll r){
if(l<=cur->l&&r>=cur->r){
return cur->sum;
}
if(cur->lazy)update(cur);
ll ans=0;
if(l<(cur->l+cur->r)/2)ans+=query(cur->left,l,r);
if(r>(cur->l+cur->r)/2)ans+=query(cur->right,l,r);
return ans;
}
inline void modify(Tree* cur,ll l,ll r){
if(l<=cur->l&&r>=cur->r){
cur->sum=cur->r-cur->l-cur->sum;
cur->lazy=1;
return;
}
if(cur->lazy)update(cur);
if(l<(cur->l+cur->r)/2)modify(cur->left,l,r);
if(r>(cur->l+cur->r)/2)modify(cur->right,l,r);
cur->sum=cur->left->sum+cur->right->sum;
}
int main(){
Tree* root=newtree();
cin>>n>>m;
cin>>s;
for(int i=0;i<n;i++){
if(s[i]=='0')a[i+1]=0;
else a[i+1]=1;
}
build(&root,1,n+1);
for(int i=1;i<=m;i++){
cin>>OP>>L>>R;
if(OP==0)modify(root,L,R+1);
if(OP==1)cout<<query(root,L,R+1)<<endl;
}
return 0;
}