社区讨论
有人可以帮我看看为什么会超时两个点吗?
P2574XOR的艺术参与者 4已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mi6v3hdf
- 此快照首次捕获于
- 2025/11/20 11:18 4 个月前
- 此快照最后确认于
- 2025/11/20 11:18 4 个月前
CPP
#include <bits/stdc++.h>
#define ll(x) (x<<1)
#define rr(x) (x<<1|1)
using namespace std;
const int N=200010;
char s[N];
int sum[N<<2],laz[N<<2],aaa[N];
void pushup(int x)
{
sum[x]=sum[ll(x)]+sum[rr(x)];
}
void build(int x,int l,int r)
{
if (l==r) {sum[x]=aaa[l];return;}
int mid=l+r>>1;
build(ll(x),l,mid);
build(rr(x),mid+1,r);
pushup(x);
}
void pushdown(int x,int l,int r)
{
int mid=l+r>>1;
sum[ll(x)]=(mid-l+1)-sum[ll(x)];
sum[rr(x)]=(r-mid)-sum[rr(x)];
laz[ll(x)]=!laz[ll(x)];
laz[rr(x)]=!laz[rr(x)];laz[x]=!laz[x];
}
int ask(int x,int l,int r,int ls,int rs)
{
if (l>rs||r<ls) return 0;
if (l>=ls&&r<=rs) return sum[x];
if (laz[x]) pushdown(x,l,r);
int mid=l+r>>1;
return ask(ll(x),l,mid,ls,rs)+ask(rr(x),mid+1,r,ls,rs);
}
void change(int x,int l,int r,int ls,int rs)
{
if (l>rs||r<ls) return;
if (l>=ls&&r<=rs) {
sum[x]=(r-l+1)-sum[x];laz[x]=!laz[x];
return;
}
if (laz[x]&&l!=r) pushdown(x,l,r);
int mid=l+r>>1;
if (ls<=mid) change(ll(x),l,mid,ls,rs);
if (rs>mid) change(rr(x),mid+1,r,ls,rs);
pushup(x);
}
int main()
{
int n,m,c,a,b;
scanf("%d%d",&n,&m);
scanf("%s",s);
for (int i=0;i<strlen(s);++i)
aaa[i+1]=s[i]^48;
build(1,1,n);
while (m--) {
scanf("%d%d%d",&c,&a,&b);
if (c) printf("%d\n",ask(1,1,n,a,b));
else change(1,1,n,a,b);
}
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...