线段树10pts求调,玄关
查看原帖
线段树10pts求调,玄关
749175
114514xxx楼主2024/8/22 22:23
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+25;
int n,m,a[N];
int ls(int p){return 2*p;}
int rs(int p){return 2*p+1;}
struct node{
	int l,r,sum,tag;
}t[N];
inline void build(int l,int r,int p){
	t[p].l=l,t[p].r=r;
	if(l==r){
		t[p].sum=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,ls(p));
	build(mid+1,r,rs(p));
	t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
}
inline void spread(int p){
	if(t[p].tag){
		t[ls(p)].sum=t[ls(p)].r-t[ls(p)].l+1-t[ls(p)].sum;
		t[rs(p)].sum=t[rs(p)].r-t[rs(p)].l+1-t[rs(p)].sum;
		t[ls(p)].tag=1;
		t[rs(p)].tag=1;
		t[p].tag=0;
	}

}
inline void modify(int l,int r,int p){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].tag=1;
		t[p].sum=(t[p].r-t[p].l+1)-t[p].sum;
		return;
	}
	spread(p);
	int mid=(t[p].l+t[p].r)/2;
	if(l<=mid)modify(l,r,ls(p));
	if(r>mid)modify(l,r,rs(p));
	t[p].sum=t[ls(p)].sum+t[rs(p)].sum;
}
inline int query(int l,int r,int p){
	int ans=0;
	if(t[p].l>=l&&t[p].r<=r){
		return t[p].sum; 		
	}
	spread(p);
	int mid=(t[p].l+t[p].r)/2;
	if(l<=mid)ans+=query(l,r,ls(p));
	if(r>mid)ans+=query(l,r,rs(p));
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		a[i]=1;
	int c,l,r;
	build(1,n,1);
	for(int i=1;i<=m;i++){
		cin>>c>>l>>r;
		if(!c)modify(l,r,1);
		else cout<<query(l,r,1)<<"\n";
	}
	return 0;
}//cout<<"l:"<<t[p].l<<" r:"<<t[p].r<<" sum:"<<t[p].sum<<endl;
2024/8/22 22:23
加载中...