题目描述
求 (n) 个矩形的面积并。
输入格式
第一行一个正整数 (n)。
接下来 (n) 行每行四个非负整数 (x_1, y_1, x_2, y_2)，表示一个矩形的左下角坐标为 ((x_1, y_1))，右上角坐标为 ((x_2, y_2))。
输出格式
一行一个正整数，表示 (n) 个矩形的并集覆盖的总面积。
其实老早以前就会了
不过现在才来写板子
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std;
inline int read(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); }
while(ch<='9'&&ch>='0'){ x=(x<<3)+(x<<1)+ch-'0'; ch=getchar();}
return x*f;
}
const int N=4e5+5;
#define mid ((l+r)>>1)
int n;ll b[N<<4],num;
int root,ls[N<<2],rs[N<<2],val[N<<2],len[N<<2],cnt;
inline void pushup(int p,int l,int r){
if(val[p])len[p]=b[r+1]-b[l];
else len[p]=len[ls[p]]+len[rs[p]];
}
void update(int &p,int l,int r,int L,int R,int d){
if(!p)p=++cnt;
if(L<=l&&r<=R){ val[p]+=d; pushup(p,l,r); return; }
if(L<=mid)update(ls[p],l,mid,L,R,d);
if(R>mid)update(rs[p],mid+1,r,L,R,d);
pushup(p,l,r);
}
struct node{
int x1,y1,x2,y2;
}e[N];
vector<pair<int,int> >p[N],q[N];
signed main(){
n=read();
for(int i=1;i<=n;i++){
b[++num]=e[i].x1=read(),b[++num]=e[i].y1=read();
b[++num]=e[i].x2=read(),b[++num]=e[i].y2=read();
}
sort(b+1,b+1+num);
num=unique(b+1,b+1+num)-b-1;
for(int i=1;i<=n;i++){
int x1=e[i].x1,y1=e[i].y1,x2=e[i].x2,y2=e[i].y2;
x1=lower_bound(b+1,b+1+num,x1)-b;
y1=lower_bound(b+1,b+1+num,y1)-b;
x2=lower_bound(b+1,b+1+num,x2)-b;
y2=lower_bound(b+1,b+1+num,y2)-b;
p[x1].pb(mp(y1,y2-1));
q[x2].pb(mp(y1,y2-1));
}
ll ans=0;
for(int i=1;i<num;i++){
for(int j=0;j<p[i].size();j++)
update(root,1,num,p[i][j].fi,p[i][j].se,1);
for(int j=0;j<q[i].size();j++)
update(root,1,num,q[i][j].fi,q[i][j].se,-1);
ans+=(b[i+1]-b[i])*len[root];
}
cout<<ans<<endl;
}