社区讨论

线段树哪错了啊,求助

P3870[TJOI2009] 开关参与者 2已保存回复 6

讨论操作

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

当前回复
6 条
当前快照
1 份
快照标识符
@lo7km7eh
此快照首次捕获于
2023/10/27 03:21
2 年前
此快照最后确认于
2023/10/27 03:21
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
    int l,r,sum,col;
    node(){
        l=r=sum=col=0;
    }
    void color(int v){
        col+=v;
        if(col&1) sum=(r-l+1)-sum;
        return;
    }
};
node z[800002];
const node operator+(const node&x,const node&y){
    node ans;
    ans.l=x.l;
    ans.r=y.r;
    ans.sum=x.sum+y.sum;
    return ans;
}
void upload(int rt){
    z[rt<<1].color(z[rt].col);
    z[rt<<1|1].color(z[rt].col);
    z[rt].col=0;
    return;
}
void update(int rt){
    z[rt]=z[rt<<1]+z[rt<<1|1];
    return;
}
void build(int l,int r,int rt){
    if(l==r){
        z[rt].l=z[rt].r=l;
        z[rt].sum=0;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    update(rt);
}
node query(int l,int r,int rt,int nowl,int nowr){
    if(l>=nowl&&r<=nowr) return z[rt];
    upload(rt);
    update(rt);
    int mid=(l+r)>>1;
    if(nowl<=mid){
        if(nowr<=mid) return query(l,mid,rt<<1,nowl,nowr);
        else return query(l,mid,rt<<1,nowl,nowr)+query(mid+1,r,rt<<1|1,nowl,nowr);
    }
    else return query(mid+1,r,rt<<1|1,nowl,nowr);
}
void modify(int l,int r,int rt,int nowl,int nowr){
    if(l>=nowl&&r<=nowr){
        z[rt].color(1);
        return;
    }
    upload(rt);
    update(rt);
    int mid=(l+r)>>1;
    if(nowl<=mid) modify(l,mid,rt<<1,nowl,nowr);
    if(nowr>mid) modify(mid+1,r,rt<<1|1,nowl,nowr);
    return;
}
int main(){
    cin>>n>>m;
    build(1,n,1);
    while(m--){
        int c,a,b;
        cin>>c>>a>>b;
        if(c==0) modify(1,n,1,a,b);
        else cout<<query(1,n,1,a,b).sum<<"\n";
    }
    return 0;
}

回复

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

正在加载回复...