矩形面积并（扫描线法）求助

#include<bits/stdc++.h>
using namespace std;
int const N=3e6+5;
#define mid (l+r>>1)
#define lc x<<1
#define rc x<<1|1
int xbin[N],ybin[N];
int xcnt,ycnt,n;
int cnt[N],minn[N],tag[N];
struct rect{
	int x1,y1,x2,y2;
}r[N];
struct node{
	int x1,x2,v;
};
vector<node> g[N];
void pushup(int k){
	if(minn[lc]=minn[rc]){
		minn[k]=minn[lc];
		cnt[k]=cnt[lc]+cnt[rc];
	}
	else{
		int f=(minn[lc]<minn[rc])?lc:rc;
		minn[k]=f;
		cnt[k]=cnt[f];
	}
}
void pushdown(int k){
	if(tag[k]!=0){
		minn[lc]+=tag[k],minn[rc]+=tag[k];
		tag[lc]+=tag[k],tag[rc]+=tag[k];
		tag[k]=0;
	}
}
void change(int k,int l,int r,int from,int to,int v){
	if(frpm<=l&&r<=to){
		tag[k]+=v,minn[k]+=v;
		return;
	}
	pushdown(k);
	if(from<=mid) change(lc,l,mid,from,to,v);
	if(mid<to) change(rc,mid+1,r,from,to,v);
	pushup(k);
}
void build(int k,int l,int r){
	minn[k]=tag[k]=0;
	if(l==r){
		cnt[k]=xbin[l]=xbin[l-1];
		return;
	}
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(k);
}
int main(){
	n=read();
	for(inti=1;i<=n;i++){
		r[i],x1=read,r[i].y1=read(),r[i].x2=read(),r[i].y2=read();
		xbin[++xcnt]=r[1].x1,xbin[++xcnt]=r[i].x2;
		ybin[++ycnt]=r[i].y1,ybin[++ycnt]=r[i].y2;
	}
	sort(xbin+1,xbin+xcnt+1);
	sort(ybin+1,ybin+ycnt+1);
	xcnt=unique(xbin+1,xbin+xcnt+1)-xbin-1;
	ycnt=unique(ybin+1,ybin+ycnt+1)-ybin-1;
	for(int i=1;i<=n;i++){
		int x1=lower_bound(xbin+1,xbin+xcnt+1,r[i].x1)-xbin;
		int x2=lower_bound(xbin+1,xbin+xcnt+1,r[i].x2)-xbin;
		int y1=lower_bound(ybin+1,ybin+ycnt+1,r[i].y1)-ybin;
		int y2=lower_bound(ybin+1,ybin+ycnt+1,r[i].y2)-ybin;
		if(x1<x2){
			g[y1].push_back((node){x1+1,x2,1});
			g[y2].push_back((node){x1+1,x2,-1});
		}
	}
	xbin[0]=xbin[1];
	ybin[0]=ybin[1];
	build(1,1,xcnt);
	int ans=0;
	for(int i=1;i<=ycnt;i++){
		int tmp=cnt[1];
		if(minn[1]>0) tmp=0;
		ans+=(ybin[i]=ybin[i-1])*(xbin[xcnt]-xbin[1]-tmp);
		for(int j=0;j<g[i].size();j++){
			change(1,1,xcnt,g[i][j].x1,g[i][j].x2,g[i][j].v);
		}
	}
	return 0;
}