社区讨论
线段树哪错了啊,求助
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 条回复,欢迎继续交流。
正在加载回复...