思路

不同于普通的的扫描线，本题让我们求奇次和偶次覆盖区间，仔细想一下我们不能直接算得是奇次还是偶次，这就要求我们的线段树能够保存每一小块区间的奇偶长度。

CPP

struct segment_tree{
	int l,r;//表示区间范围
	int len1,len2,sum;//len1表示奇次，len2表示偶次
}

接下来我们考虑奇次和偶次的转换，完全覆盖父节点的区间一定覆盖子节点，而父节点的父节点（祖父节点）就不会影响子节点的

len1

，

len2

。显然：子节点的区间覆盖次数由且仅由自己和父节点决定。

在区间修改时：

父节点没有被完全覆盖时，区间长度由左右儿子节点决定。

CPP

if(!t[p].sum){
	t[p].len1=t[p<<1].len1+t[p<<1|1].len1;
	t[p].len2=t[p<<1].len2+t[p<<1|1].len2;
}

父节点被完全偶次覆盖时，父节点的真实奇次覆盖为子节点的奇次覆盖和，在通过区间总长减去奇次长度，即为偶次区间长度。

CPP

if(!(t[p].sum&1)){
	t[p].len1=t[p<<1].len1+t[p<<1|1].len1;
	t[p].len2=X[t[p].r]-X[t[p].l]-t[p].len1;
}

父节点被奇数次完全覆盖时，父节点的真实偶次覆盖为左右儿子子节点奇次覆盖和，后通过区间总长求得奇次覆盖长度。

CPP

else{
	t[p].len2=t[p<<1].len1+t[p<<1|1].len1;
	t[p].len1=X[t[p].r]-X[t[p].l]-t[p].len2;
}

Code

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
void read(int &a){
	char ch;int f=1,k=0;ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
	a=k*f;
}
struct Line{
	int l,r,h;
	int mark;
}line[N<<1];
struct segment_tree{
	int l,r;
	int len1,len2,sum;
}t[N<<2];
int n,ans1,ans2,X[N<<1];
bool cmp(Line x,Line y){
	return x.h<y.h;
}

inline void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	if(l+1==r) return ;
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid,r);
}

inline void push_up(int p){
	if(!t[p].sum){
		t[p].len1=t[p<<1].len1+t[p<<1|1].len1;
		t[p].len2=t[p<<1].len2+t[p<<1|1].len2;
	}
	else if(!(t[p].sum&1)){
		t[p].len1=t[p<<1].len1+t[p<<1|1].len1;
		t[p].len2=X[t[p].r]-X[t[p].l]-t[p].len1;
	}
	else{
		t[p].len2=t[p<<1].len1+t[p<<1|1].len1;
		t[p].len1=X[t[p].r]-X[t[p].l]-t[p].len2;
	}
}

inline void modify(int p,int l,int r,int w){
	if(X[t[p].r]<=l||X[t[p].l]>=r) return ;
	if(l<=X[t[p].l]&&X[t[p].r]<=r){
		t[p].sum+=w;
		push_up(p);
		return ;
	}
	modify(p<<1,l,r,w);
	modify(p<<1|1,l,r,w);
	push_up(p);
}

signed main(){
	read(n);
	int xa,xb,ya,yb;
	for(int i=1;i<=n;i++){
		read(xa),read(ya),read(xb),read(yb);
		X[i*2-1]=xa,X[i*2]=xb;
		line[2*i-1]=(Line){xa,xb,ya,1};
		line[2*i]=(Line){xa,xb,yb,-1};
	}
	n<<=1;
	sort(line+1,line+1+n,cmp);
	sort(X+1,X+1+n);
	int tot=unique(X+1,X+1+n)-X-1;
	build(1,1,tot);
	for(int i=1;i<n;i++){
		modify(1,line[i].l,line[i].r,line[i].mark);
		ans1+=t[1].len1*(line[i+1].h-line[i].h);
		ans2+=t[1].len2*(line[i+1].h-line[i].h);	
	}
	cout<<ans1<<"\n"<<ans2;
	return 0;
}

补：注意本题build(1,1,tot)，而非 P5490 【模板】扫描线 & 矩形面积并中的build(1,1,tot-1)。~~我才不会告诉你是我不太明白~~分析一下：

题目	区间表示方式	有效区间数	参数
P5490	左闭右开 [X [l], X [r])	tot-1	build(1,1,tot-1)
P8734	闭区间 [X [l], X [r]]	tot-1	build(1,1,tot)

求管理大大通过！！！到这里结束了，点个赞呗！

题解：P8734 [蓝桥杯 2020 国 A] 奇偶覆盖

文章操作

思路

Code

相关推荐

评论

题解：P8734 [蓝桥杯 2020 国 A] 奇偶覆盖