矩形面积并
luogu P5490
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int N=3e5+5;struct rectangle{int x1,y1,x2,y2;
}rec[N/2];
struct lines{int x,y1,y2,k;
}L[N];
int Ysort[N];
int total[N<<2];
int cover[N<<2];
int cnt[N<<2];void up(int x){if(cnt[x]>0)cover[x]=total[x];else cover[x]=cover[x<<1]+cover[x<<1|1];
}
void built(int x,int l,int r){if(l<r){int mid=(l+r)>>1;built(x<<1,l,mid);built(x<<1|1,mid+1,r);}total[x]=Ysort[r+1]-Ysort[l];cover[x]=0;cnt[x]=0;
}
void change(int x,int l,int r,int ql,int qr,int k){if(ql<=l&&r<=qr){cnt[x]+=k;}else{int mid=(l+r)>>1;if(ql<=mid)change(x<<1,l,mid,ql,qr,k);if(qr>mid)change(x<<1|1,mid+1,r,ql,qr,k);}up(x);
}
int init(int n){for(int i=1,j=i+n;i<=n;++i,++j){L[i]={rec[i].x1,rec[i].y1,rec[i].y2,1};L[j]={rec[i].x2,rec[i].y1,rec[i].y2,-1};Ysort[i]=rec[i].y1;Ysort[j]=rec[i].y2;}int siz=n<<1;sort(L+1,L+siz+1,[&](auto a,auto b){return a.x<b.x;});sort(Ysort+1,Ysort+siz+1);int m=unique(Ysort+1,Ysort+siz+1)-(Ysort+1);Ysort[m+1]=Ysort[m];return m;
}
ll merge_S(int n){int m=init(n);built(1,1,m);ll ans=0;int pre=0;int siz=n<<1;for(int i=1;i<=siz;i++){ans+=1LL*cover[1]*(L[i].x-pre);pre=L[i].x;int l=lower_bound(Ysort+1,Ysort+m+1,L[i].y1)-Ysort;int r=lower_bound(Ysort+1,Ysort+m+1,L[i].y2)-Ysort-1;change(1,1,m,l,r,L[i].k);}return ans;
}void solve(){int n;cin>>n;for(int i=1;i<=n;++i){cin>>rec[i].x1>>rec[i].y1>>rec[i].x2>>rec[i].y2;}cout<<merge_S(n);
}
int main(void){cin.tie(0)->sync_with_stdio(0);int T=1;//cin>>T;while(T--)solve();
}
矩形周长并
Luogu P1856
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int N=1e5+5;struct rectangle{int x1,y1,x2,y2;
}rec[N/2];
struct lines_y{int x,y1,y2,k;
}Ly[N];
struct lines_x{int y,x1,x2,k;
}Lx[N];
int Ysort[N],Xsort[N];
int total[N<<2];
int cover[N<<2];
int cnt[N<<2];void up(int x){if(cnt[x]>0)cover[x]=total[x];else cover[x]=cover[x<<1]+cover[x<<1|1];
}
void change(int x,int l,int r,int ql,int qr,int k){if(ql<=l&&r<=qr){cnt[x]+=k;}else{int mid=(l+r)>>1;if(ql<=mid)change(x<<1,l,mid,ql,qr,k);if(qr>mid)change(x<<1|1,mid+1,r,ql,qr,k);}up(x);
}
void built_y(int x,int l,int r){if(l<r){int mid=(l+r)>>1;built_y(x<<1,l,mid);built_y(x<<1|1,mid+1,r);}total[x]=Ysort[r+1]-Ysort[l];cover[x]=0;cnt[x]=0;
}
int init_y(int n){for(int i=1,j=i+n;i<=n;++i,++j){Ly[i]={rec[i].x1,rec[i].y1,rec[i].y2,1};Ly[j]={rec[i].x2,rec[i].y1,rec[i].y2,-1};Ysort[i]=rec[i].y1;Ysort[j]=rec[i].y2;}int siz=n<<1;sort(Ly+1,Ly+siz+1,[&](auto a,auto b){return a.x<b.x;});sort(Ysort+1,Ysort+siz+1);int m=unique(Ysort+1,Ysort+siz+1)-(Ysort+1);Ysort[m+1]=Ysort[m];return m;
}
ll scan_y(int n){int m=init_y(n);built_y(1,1,m);ll ans=0;int pre;int siz=n<<1;for(int i=1;i<=siz;i++){pre=cover[1];int l=lower_bound(Ysort+1,Ysort+m+1,Ly[i].y1)-Ysort;int r=lower_bound(Ysort+1,Ysort+m+1,Ly[i].y2)-Ysort-1;change(1,1,m,l,r,Ly[i].k);ans+=abs(pre-cover[1]);}return ans;
}
void built_x(int x,int l,int r){if(l<r){int mid=(l+r)>>1;built_x(x<<1,l,mid);built_x(x<<1|1,mid+1,r);}total[x]=Xsort[r+1]-Xsort[l];cover[x]=0;cnt[x]=0;
}
int init_x(int n){for(int i=1,j=i+n;i<=n;++i,++j){Lx[i]={rec[i].y1,rec[i].x1,rec[i].x2,1};Lx[j]={rec[i].y2,rec[i].x1,rec[i].x2,-1};Xsort[i]=rec[i].x1;Xsort[j]=rec[i].x2;}int siz=n<<1;sort(Lx+1,Lx+siz+1,[&](auto a,auto b){return a.y<b.y;});sort(Xsort+1,Xsort+siz+1);int m=unique(Xsort+1,Xsort+siz+1)-(Xsort+1);Xsort[m+1]=Xsort[m];return m;
}
ll scan_x(int n){int m=init_x(n);built_x(1,1,m);ll ans=0;int pre;int siz=n<<1;for(int i=1;i<=siz;i++){pre=cover[1];int l=lower_bound(Xsort+1,Xsort+m+1,Lx[i].x1)-Xsort;int r=lower_bound(Xsort+1,Xsort+m+1,Lx[i].x2)-Xsort-1;change(1,1,m,l,r,Lx[i].k);ans+=abs(pre-cover[1]);}return ans;
}
ll merge_C(int n){return scan_x(n)+scan_y(n);
}
void solve(){int n;cin>>n;for(int i=1;i<=n;++i){cin>>rec[i].x1>>rec[i].y1>>rec[i].x2>>rec[i].y2;}cout<<merge_C(n);
}
int main(void){cin.tie(0)->sync_with_stdio(0);int T=1;//cin>>T;while(T--)solve();
}
矩形面积并
leetcode 850
const int N=1000;
const int P=1000000007;
struct lines{int x,y1,y2,k;}L[N];int Y[N];int total[N<<2];int cover[N<<2];int cnt[N<<2];
class Solution {void up(int x){if(cnt[x])cover[x]=total[x];else cover[x]=cover[x<<1]+cover[x<<1|1];}void change(int x,int l,int r,int ql,int qr,int k){if(ql<=l&&r<=qr){cnt[x]+=k;}else{int mid=(l+r)>>1;if(ql<=mid)change(x<<1,l,mid,ql,qr,k);if(qr>mid)change(x<<1|1,mid+1,r,ql,qr,k);}up(x);}void built(int x,int l,int r){if(l<r){int mid=(l+r)>>1;built(x<<1,l,mid);built(x<<1|1,mid+1,r);}total[x]=Y[r+1]-Y[l];cover[x]=0;cnt[x]=0;}public:int rectangleArea(vector<vector<int>>& rectangles) {int n=rectangles.size();if(n==1){int x1=rectangles[0][0];int y1=rectangles[0][1];int x2=rectangles[0][2];int y2=rectangles[0][3];return 1LL*(x2-x1)*(y2-y1)%P;}for(int i=1,j=i+n;i<=n;++i,++j){int x1=rectangles[i-1][0];int y1=rectangles[i-1][1];int x2=rectangles[i-1][2];int y2=rectangles[i-1][3];L[i]={x1,y1,y2,1};L[j]={x2,y1,y2,-1};Y[i]=y1;Y[j]=y2;}int siz=n<<1;sort(Y+1,Y+siz+1);sort(L+1,L+siz+1,[&](auto a,auto b){return a.x<b.x;});int m=unique(Y+1,Y+siz+1)-(Y+1);Y[m+1]=Y[m];built(1,1,m);long long ans=0;int pre=0;for(int i=1;i<=siz;++i){ans=(ans+1LL*cover[1]*(L[i].x-pre)%P)%P;pre=L[i].x;int l=lower_bound(Y+1,Y+m+1,L[i].y1)-Y;int r=lower_bound(Y+1,Y+m+1,L[i].y2)-Y-1;change(1,1,m,l,r,L[i].k);}return ans;}
};
分割面积
leetcode 3454
const int N=200000;
class Solution {struct lines{int y,x1,x2,k;}L[N];int X[N];int total[N<<2];int cnt[N<<2];int cover[N<<2];void up(int x){cover[x]=cnt[x]==0?cover[x<<1]+cover[x<<1|1]:total[x];}void built(int x,int l,int r){if(l<r){int mid=(l+r)>>1;built(x<<1,l,mid);built(x<<1|1,mid+1,r);}total[x]=X[r+1]-X[l];cover[x]=cnt[x]=0;}void change(int x,int l,int r,int ql,int qr,int k){if(ql<=l&&r<=qr){cnt[x]+=k;}else{int mid=(l+r)>>1;if(ql<=mid)change(x<<1,l,mid,ql,qr,k);if(qr>mid)change(x<<1|1,mid+1,r,ql,qr,k);}up(x);}
public:double separateSquares(vector<vector<int>>& squares) {int n=squares.size();for(int i=1,j=i+n;i<=n;++i,++j){int x1=squares[i-1][0];int y1=squares[i-1][1];int a=squares[i-1][2];int x2=x1+a;int y2=y1+a;X[i]=x1;X[j]=x2;L[i]={y1,x1,x2,1};L[j]={y2,x1,x2,-1};}int siz=n<<1;sort(X+1,X+siz+1);sort(L+1,L+siz+1,[&](auto a,auto b){return a.y<b.y;});int m=unique(X+1,X+siz+1)-(X+1);X[m+1]=X[m];built(1,1,m);long long sum=0;int pre=0;for(int i=1;i<=siz;++i){long long len=L[i].y-pre;sum+=cover[1]*len;pre=L[i].y;int l=lower_bound(X+1,X+m+1,L[i].x1)-X;int r=lower_bound(X+1,X+m+1,L[i].x2)-X-1;change(1,1,m,l,r,L[i].k);}built(1,1,m);long long cur=0;pre=0;for(int i=1;i<=siz;++i){long long len=L[i].y-pre;cur+=cover[1]*len;long long need=cur-(sum-cur);if(need>=0&&cover[1]>0){return L[i].y - 0.5*need/cover[1];}pre=L[i].y;int l=lower_bound(X+1,X+m+1,L[i].x1)-X;int r=lower_bound(X+1,X+m+1,L[i].x2)-X-1;change(1,1,m,l,r,L[i].k);}return -1;}
};