社区讨论

求救!!为毛本地AC交上去全 蛙~?!

P2574XOR的艺术参与者 5已保存回复 8

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@mi85yuuj
此快照首次捕获于
2025/11/21 09:10
4 个月前
此快照最后确认于
2025/11/21 09:10
4 个月前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;
int a[200010];
struct node{
	int l,r;
	int he;
}xds[800040];
int lazy_tag[800040];
int read()
{
	int fh=1,zs=0;
	char x;
	x=getchar();
	while((x<'0'||x>'9')&&(x!='-'))	x=getchar();
	if(x=='-')
	{
		fh=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9')
	{
		zs=zs*10+x-'0';
		x=getchar();
	}
	return zs*fh;
}
void build(int l_,int r_,int bh)
{
	xds[bh].l=l_;
	xds[bh].r=r_;
	if(l_==r_)	xds[bh].he=a[l_];
	else
	{
		build(l_,((l_+r_)>>1),(bh<<1));
		build(((l_+r_)>>1)+1,r_,(bh<<1)+1);
		xds[bh].he=xds[bh<<1].he+xds[(bh<<1)+1].he;
	}
}
long long again(int bh)
{
	if(lazy_tag[bh]%2==1)
	{
		xds[bh<<1].he=xds[bh<<1].r-xds[bh<<1].l+1-xds[bh<<1].he;
		xds[(bh<<1)+1].he=xds[(bh<<1)+1].r-xds[(bh<<1)+1].l+1-xds[(bh<<1)+1].he;
		lazy_tag[bh<<1]+=lazy_tag[bh];
		lazy_tag[(bh<<1)+1]+=lazy_tag[bh];
	}
	lazy_tag[bh]=0;
}
void do1(int l_,int r_,int bh)
{
	if(l_<=xds[bh].l&&xds[bh].r<=r_)
	{
		xds[bh].he=(xds[bh].r-xds[bh].l+1)-xds[bh].he;
		lazy_tag[bh]+=1;
		return;
	}
	again(bh);
	int mid=(xds[bh].l+xds[bh].r)>>1;
	if(l_<=mid) do1(l_,r_,bh<<1);
	if(r_>mid) do1(l_,r_,(bh<<1)+1);
	xds[bh].he=xds[bh<<1].he+xds[(bh<<1)+1].he;
}
int ask(int l_,int r_,int bh)
{
	if(l_<=xds[bh].l&&xds[bh].r<=r_)
	{
		return xds[bh].he;
	}
	again(bh);
	int ans=0;
	int mid=(xds[bh].l+xds[bh].r)>>1;
	if(l_<=mid) ans+=ask(l_,r_,bh<<1);
	if(r_>mid) ans+=ask(l_,r_,(bh<<1)+1);
	return ans;
}
int main()
{
	freopen("testdata.in","r",stdin);
	freopen("1.out","w",stdout);
	int n,m;
	n=read();
	m=read();
	memset(lazy_tag,0,sizeof(lazy_tag));
	for(int i=1;i<=n;i++)
	{
		a[i]=getchar()-'0';
	}
	build(1,n,1);
	int way,x,y;
	for(int i=1;i<=m;i++)
	{
		way=read();x=read();y=read();
		if(way==0)
		{
			do1(x,y,1);
		}
		else
		{
			printf("%d\n",ask(x,y,1));
		}
	}
	return 0;
}

回复

8 条回复,欢迎继续交流。

正在加载回复...