求助,线段树,样例通过仅得10pts求调教
查看原帖
求助,线段树,样例通过仅得10pts求调教
568243
Windows_Update楼主2022/2/7 08:53

求大佬调教一下这个线段树的代码,自己排查了半天没发现哪里写错了qwq
源代码:

#include<bits/stdc++.h>
using namespace std;
long long arr[1000005],n,m,a,c,b;
struct node{
	long long l,r,sum,len,tag;
	node operator+(const node &x){
		return {l,x.r,sum+x.sum,len+x.len,0};
	}
}stree[4000020];
#define pushup(now) stree[now]=stree[now<<1]+stree[now<<1|1]
inline void givetag(int now){
	if(stree[now].l==stree[now].r){
		stree[now].sum=1-stree[now].sum;
		return;
	}
	stree[now].sum=stree[now].len-stree[now].sum;
	stree[now].tag=1;
}
inline void pushtag(int now){
	givetag(now<<1);
	givetag(now<<1|1);
	stree[now].tag=0;
}
void build(int l,int r,int now){
	if(l==r){
		stree[now]={l,l,arr[l],1,0};
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,now<<1);
	build(mid+1,r,now<<1|1);
	pushup(now);
}
void change(int now,int l,int r){
	if(stree[now].tag) pushtag(now);
//	cout<<l<<" "<<r<<" "<<stree[now].sum<<endl;
	if(stree[now].l>=l&&stree[now].r<=r){
		givetag(now);
		return;
	}else if(stree[now].l>r||stree[now].r<l){
		return;
	}else{
		change(now<<1,l,r);
		change(now<<1|1,l,r);	
	}
	pushup(now);
}
long long query(int l,int r,int now){
	if(stree[now].tag) pushtag(now);
	if(l<=stree[now].l&&r>=stree[now].r) return stree[now].sum;
	if(l>stree[now].r||r<stree[now].l)return 0;
	return query(l,r,now<<1)+query(l,r,now<<1|1);
}
inline long long read(){
	long long x=0;
	char ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}
int main(){
	n=read(),m=read();
	build(1,n,1);
	while(m--){
		c=read(),a=read(),b=read();
		if(c==0)change(1,a,b);else printf("%d\n",query(a,b,1));
	}
} 
2022/2/7 08:53
加载中...