线段树求调
查看原帖
线段树求调
928975
little_grass_sage楼主2024/1/12 15:28

我用了v1存有多少个树苗,v2表示有多少个树

#include<bits/stdc++.h>
using namespace std;
struct tree{
	long long l,r,v1,v2,tag;
}a[1000009];
long long b,c;
void js(long long p,long long l,long long r){
	a[p].l=l,a[p].r=r,a[p].v1=0,a[p].v2=r-l+1;
	if(r>l){
		js(p*2,l,(l+r)/2),js(p*2+1,(l+r)/2+1,r);
	}
}
void pt(long long p){
	a[p*2].tag=a[p].tag,a[p*2+1].tag=a[p].tag;
	if(a[p].tag==1) a[p*2].v1=a[p*2].r-a[p*2].l+1-a[p*2].v2,
			a[p*2+1].v1=a[p*2+1].r-a[p*2+1].l+1-a[p*2+1].v2;
	if(a[p].tag==-1) a[p*2].v1=a[p*2].v2=a[p*2+1].v1=a[p*2+1].v2=0;
	a[p].tag=0;
}
void zj(long long p,long long l,long long r){
	if(a[p].l>r||a[p].r<l) return;
	if(a[p].tag) pt(p);
	if(a[p].l>=l&&a[p].r<=r){
		a[p].v1=a[p].r-a[p].l+1-a[p].v2;
		a[p].tag=1;
		return;
	} 
	zj(p*2,l,r),zj(p*2+1,l,r);
	a[p].v1=a[p*2].v1+a[p*2+1].v1;
	a[p].v2=a[p*2].v2+a[p*2+1].v2;
}
void ji(long long p,long long l,long long r){
	if(a[p].l>r||a[p].r<l) return;
	if(a[p].tag) pt(p);
	if(a[p].l>=l&&a[p].r<=r){
		a[p].v1=0,a[p].v2=0;
		a[p].tag=-1;
		return;
	}
	ji(p*2,l,r),ji(p*2+1,l,r);
	a[p].v1=a[p*2].v1+a[p*2+1].v1;
	a[p].v2=a[p*2].v2+a[p*2+1].v2;
}
int cz(int p,int l,int r){
	if(a[p].tag) pt(p);
	if(a[p].l>r||a[p].r<l) return 0;
	if(a[p].l>=l&&a[p].r<=r) return a[p].v1;
	return cz(p*2,l,r)+cz(p*2+1,l,r);
}
int main(){
	cin>>b>>c;
	int ans=0;
	js(1,0,b);
	for(long long i=1;i<=c;i++){
		long long x,y,z;
		cin>>x>>y>>z;
		if(x==1) zj(1,y,z);
		else{
			ans+=cz(1,y,z);
			ji(1,y,z);
		}
	}
	cout<<a[1].v1<<endl<<ans;
	return 0;
}
2024/1/12 15:28
加载中...