Rectangles（线段树，扫描线）

Rectangles

题意：给出n个矩形，求奇数个矩形覆盖的面积并。

思路：扫描线。

扫描线思路：扫描线中（假设我们顺着x轴平行的线进行扫描），我们把一个矩形分为上下两条线，其中下线的值为1，上线的值为−1。在我们扫描每一条线之后，我们会对当前这条扫描线所映射的区间（即区间[x1,x2]）进行区间更新（区间更新1或−1）。而每次扫描后，如果线段树维护的某个的映射区间的标记值大于1，则说明当前当前这个区间能够对答案有贡献，则就将改段区间对应的值累加，并向根部更新。最后树顶所表示的值即为在原图矩形中横坐标能贡献的大小size，最后我们将这个大小乘上前后两条扫描线所加的纵坐标的大小即为对于两条扫描线下的答案贡献。摘自：https://blog.csdn.net/weixin_39453270/article/details/89162105

在本题中因为只要判断奇数个矩形，则通过异或更新标记即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int s[maxn*2];
struct node{
	int sum,lazy;
}tr[maxn*4];
struct rec{
	int x1,x2,y,w;
	rec(){}
	rec(int _x1,int _x2,int _y,int _w){
		x1=_x1,x2=_x2,y=_y,w=_w;
	}
	bool operator <(const rec &b)const{
		return b.y>y;
	}
}q[maxn*2];

void push_down(int o,int l,int r){
	if(tr[o].lazy!=0){
		int m=(l+r)>>1;
		tr[o*2].sum=s[m]-s[l-1]-tr[o*2].sum;
		tr[o*2+1].sum=s[r]-s[m]-tr[o*2+1].sum;
		tr[o*2].lazy^=1;
		tr[o*2+1].lazy^=1;
		tr[o].lazy=0;
	}
}
void up(int o,int l,int r,int ql,int qr){
	if(ql<=l&&qr>=r){
		tr[o].sum=s[r]-s[l-1]-tr[o].sum;
		tr[o].lazy^=1;
		return ;
	}
	push_down(o,l,r);
	int m=(l+r)>>1;
	if(ql<=m)
		up(o*2,l,m,ql,qr);
	if(qr>m) up(o*2+1,m+1,r,ql,qr);
	tr[o].sum=tr[o*2].sum+tr[o*2+1].sum;
}
int main(){
	int n;
	scanf("%d",&n);
	int tot=0,cnt=0;
	for(int i=1;i<=n;i++){
		int x1,x2,y2,y1;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		if(x1>x2)
			swap(x1,x2);
		if(y1>y2)
			swap(y1,y2);
		q[++cnt]=rec(x1,x2,y1,1);
		q[++cnt]=rec(x1,x2,y2,-1);
		s[++tot]=x1;
		s[++tot]=x2;
	}
	sort(q+1,q+1+cnt);
	sort(s+1,s+1+tot);
	tot=unique(s+1,s+1+tot)-s-1;
	long long ans=0;
	for(int i=1;i<=cnt;i++){
		int l=lower_bound(s+1,s+1+tot,q[i].x1)-s;
		int r=lower_bound(s+1,s+1+tot,q[i].x2)-s;
		if(l<=r)
			up(1,1,tot,l+1,r);
		if(i!=cnt){
			ans+=1ll*tr[1].sum*(q[i+1].y-q[i].y);
		}
	}
	printf("%lld\n",ans);
}