和扫描线计算面积差不多，新加了lbd，rbd线段树来标记区间的左右两侧是否被填充(左右边界是否存在)，numbd线段树统计区间有多少边
/*数据弱不用离散化,但是要处理一下坐标*/ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define maxn 20005 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 struct Seg{ int l,r,h,s; Seg(){} Seg(int a,int b,int c,int d):l(a),r(b),h(c),s(d){} bool operator<(const Seg& a)const{ if(h==a.h) return s>a.s; return h<a.h; } }ss[maxn]; bool lbd[maxn<<2],rbd[maxn<<2];//该区间是否存在左边界，右边界,仅仅是用来判断 int numseg[maxn<<2];//该区间竖边的数量(0,2) int cnt[maxn<<2];//覆盖了这一整个区间的入边-出边 int len[maxn<<2];//这个区间被覆盖的长度 void pushup(int rt,int l,int r){ if(cnt[rt]){ lbd[rt]=rbd[rt]=1; len[rt]=r-l+1; numseg[rt]=2; } else if(l==r) len[rt]=numseg[rt]=rbd[rt]=lbd[rt]=0; else { lbd[rt]=lbd[rt<<1]; rbd[rt]=rbd[rt<<1|1]; len[rt]=len[rt<<1]+len[rt<<1|1]； numseg[rt]=numseg[rt<<1]+numseg[rt<<1|1]; if(lbd[rt<<1|1] && rbd[rt<<1]) numseg[rt]-=2; } } void update(int L,int R,int c,int l,int r,int rt){ if(L<=l && R>=r){ cnt[rt]+=c; pushup(rt,l,r); return; } int m=l+r>>1; if(L<=m) update(L,R,c,lson); if(R>m) update(L,R,c,rson); pushup(rt,l,r); } int main(){ int n; while(scanf("%d",&n)==1){ int m=0; int lbd=10000,rbd=-10000; for(int i=0;i<n;i++){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); lbd=min(lbd,a); rbd=max(rbd,c); ss[m++]=Seg(a,c,b,1); ss[m++]=Seg(a,c,d,-1); } sort(ss,ss+m); int ret=0,last=0; for(int i=0;i<m;i++){ if(ss[i].l<ss[i].r) update(ss[i].l,ss[i].r-1，ss[i].s,lbd,rbd,1); ret+=numseg[1]*(ss[i+1].h-ss[i].h);//竖边数量*区间高度 ret+=abs(len[1]-last); last=len[1]; } printf("%d ",ret); } return 0; }