线段树WA求调
查看原帖
线段树WA求调
672237
qinshi0308楼主2023/7/5 18:03

rt,只AC了第二个点,求大佬执教

# include <bits/stdc++.h>
using namespace std;
int tree[400010],tag[400010];
inline int ls(int x){
	return x*2;
}
inline int rs(int x){
	return x*2+1;
}
inline void push_up(int p){
	tree[p]=tree[ls(p)]+tree[rs(p)];
}
inline void addtag(int p,int pl,int pr){
	tag[p]++;
	tree[p]=(pr-pl+1)-tree[p];
}
inline void push_down(int p,int pl,int pr){
	if(tag[p]){
		int mid=(pl+pr)/2;
		addtag(ls(p),pl,mid);
		addtag(rs(p),mid+1,pr);
		tag[p]=0;
	}
}
inline int query(int l,int r,int pl,int pr,int p){
	if(l<=pl&&pr<=r){
		return tree[p];
	}
	push_down(p,pl,pr);
	int mid=(pl+pr)/2;
	long long sum=0;
	if(l<=mid){
		sum+=query(l,r,pl,mid,p*2);
	}
	if(mid<r){
		sum+=query(l,r,mid+1,pr,p*2+1);
	}
	return sum;
}
inline void updata(int l,int r,int pl,int pr,int p){
	if(l<=pl&&pr<=r){
		addtag(pl,pl,pr);
		return;
	}
	push_down(p,pl,pr);
	int mid=(pl+pr)/2;
	if(l<=mid){
		updata(l,r,pl,mid,p*2);
	}
	if(mid<r){
		updata(l,r,mid+1,pr,p*2+1);
	}
	push_up(p);
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,x,y;
		cin>>a>>x>>y;
		if(a==0){
			updata(x,y,1,n,1);
		}else{
			cout<<query(x,y,1,n,1)<<endl;
		}
	}
	return 0;
}
2023/7/5 18:03
加载中...