您好,10分线段树求调
查看原帖
您好,10分线段树求调
912997
00001A楼主2024/7/29 16:58

和我的朋友一起调了很久都没有调出来

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,c,a,b,len[500005],rr[500005],ll[500005],ans[500005];
bool ly[500005];
void build(int p,int l,int r){
	rr[p]=r,ll[p]=l,len[p]=r-l+1;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void zhan(int p){
	if(ly[p]==1&&ll[p]!=rr[p]){
		ly[p]=0;
		ly[p*2]^=1;
		ans[p*2]=len[p*2]-ans[p*2];
		ly[p*2+1]^=1;
		ans[p*2+1]=len[p*2+1]-ans[p*2+1];
	}
}
void chg(int p,int l,int r){
	if(l<=ll[p]&&rr[p]<=r){
		ans[p]=len[p]-ans[p];
		ly[p]^=1;
		return; 
	}
	else{
		zhan(p); 
		int mid=(ll[p]+rr[p])>>1;
		if(l<=mid)chg(p*2,l,mid);
		if(mid<r)chg(p*2+1,mid+1,r);
		ans[p]=ans[p*2]+ans[p*2+1];
	}
}
int ask(int p,int l,int r){
	if(l<=ll[p]&&rr[p]<=r){
		return ans[p];
	}
	else{
		zhan(p);
		int mid=(ll[p]+rr[p])>>1,re=0;
		if(l<=mid)re+=ask(p*2,l,mid);
		if(mid<r)re+=ask(p*2+1,mid+1,r);
		return re;
	}
}
signed main()
{
	cin>>n>>m;
	build(1,1,n);
	while(m--){
		cin>>c>>a>>b;
		if(c==0)chg(1,a,b);
		if(c==1)cout<<ask(1,a,b)<<endl;
	}
	return 0;
}
2024/7/29 16:58
加载中...