9 WA求助
查看原帖
9 WA求助
205782
R浩轩泽Anmicius楼主2020/8/10 09:45

代码如下

#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

2020/8/10 09:45
加载中...