社区讨论
求救!!为毛本地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 条回复,欢迎继续交流。
正在加载回复...