用树莓派做网站/个人网站网页首页

$Description$

给定一个$50000\times 50000$的矩阵，取反$n$个子矩阵，求最终黑色矩阵的周长

$n\le 50000$

$Solution$

将每个子矩阵拆成四条边，每条边拆成两个点，将这八个点分为横纵排序，做完差分统计答案即可（因为只有覆盖奇数次的线段才可以作为周长）

时间复杂度：$O(nlogn)$

$Code$

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
using namespace std;int n,tot1,tot2,ans;
struct node
{int i,d;bool operator <(const node &x)const{return i<x.i;}
};
vector<node>a[50001],b[50001];
inline int read()
{int f=0,d=1;char c;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
signed main()
{n=read();for(register int i=1;i<=n;i++){int x1=read(),y1=read(),x2=read(),y2=read();x1--;y1--;a[x1].push_back((node){y1,1});a[x1].push_back((node){y2,-1});a[x2].push_back((node){y1,1});a[x2].push_back((node){y2,-1});b[y1].push_back((node){x1,1});b[y1].push_back((node){x2,-1});b[y2].push_back((node){x1,1});b[y2].push_back((node){x2,-1});}for(register int i=0;i<=50000;i++) {sort(a[i].begin(),a[i].end());sort(b[i].begin(),b[i].end());int k=a[i].size();for(register int j=0,p=0;j<k-1;j++){p+=a[i][j].d;if(p&1) ans+=a[i][j+1].i-a[i][j].i;}k=b[i].size();for(register int j=0,p=0;j<k-1;j++){p+=b[i][j].d;if(p&1) ans+=b[i][j+1].i-b[i][j].i;}}printf("%d\n",ans);
}