社区讨论

有人可以帮我看看为什么会超时两个点吗?

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 条回复,欢迎继续交流。

正在加载回复...