代码如下
#include<iostream>
#include<cstdio>
#include<cstring>
const int N=2e5+10;
#define re register int
using namespace std;
int n,m;
string hurts;
struct Tree{
int l,r;
int ans;
bool lazy_tag;
}node[N<<2];
void build_tree(int k,int l,int r)
{
node[k].l=l;node[k].r=r;
if(l==r)
{
node[k].ans=hurts[l-1]-'0';
return;
}
int mid=(l+r)>>1;
build_tree(k<<1,l,mid);
build_tree(k<<1|1,mid+1,r);
node[k].ans=node[k<<1].ans+node[k<<1|1].ans;
}
inline void Add(int k,int l,int r)
{
node[k].lazy_tag^=1;
node[k].ans=r-l+1-node[k].ans;
}
inline void push_down(int k,int l,int r)
{
if(!node[k].lazy_tag)return;
int mid=(l+r)>>1;
Add(k>>1,l,mid);Add(k>>1|1,mid+1,r);
node[k].lazy_tag=false;
}
void add_data(int k,int l,int r,int l_now,int r_now)
{
if(l<=l_now&&r_now<=r)return Add(k,l_now,r_now);
push_down(k,l_now,r_now);
int mid=(l_now+r_now)>>1;
if(l<=mid)add_data(k<<1,l,r,l_now,mid);
if(mid<r)add_data(k<<1|1,l,r,mid+1,r_now);
node[k].ans=node[k<<1].ans+node[k<<1|1].ans;
}
int ask(int k,int l,int r,int l_now,int r_now)
{
if(l<=l_now&&r_now<=r)return node[k].ans;
push_down(k,l_now,r_now);
int mid=(l_now+r_now)>>1,res=0;
if(l<=mid)res+=ask(k<<1,l,r,l_now,mid);
if(mid<r)res+=ask(k<<1|1,l,r,mid+1,r_now);
return res;
}
int main()
{
std::ios::sync_with_stdio(false);
cin>>n>>m>>hurts;
build_tree(1,1,n);
for(re i=1;i<=m;++i)
{
bool a;
int b,c;
cin>>a>>b>>c;
if(!a)add_data(1,b,c,1,n);
else cout<<ask(1,b,c,1,n)<<'\n';
}
return 0;
}
好像建树的时候就没对诶...
线段树维护区间1~n的值始终为0