添加lb[],rb[]数组，来标记竖边。添加num，来计算竖边的个数，因为计算周长的时候，未覆盖的竖边都要加。
#include<stdio.h> #include<stdlib.h> #include<algorithm> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 10010 struct seg { int l,r,h; int f; }s[maxn<<2]; struct node { int cnt; int num; int len; }tree[maxn<<2]; int lb[maxn<<2],rb[maxn<<2]; int mark[maxn]; bool cmp(seg a,seg b) { return a.h < b.h; } void build(int l,int r,int rt) { tree[rt].cnt=0; tree[rt].len=0; tree[rt].num=0; if(l==r) return ; int m=(l+r)/2; build(lson); build(rson); } void getlen(int l,int r,int rt) { if(tree[rt].cnt)//如果这一段被全部覆盖 { tree[rt].len=mark[r+1]-mark[l]; tree[rt].num=2;//整段覆盖，那就有2条竖直的边 lb[rt]=rb[rt]=1;//标记左右的竖直线段 } else if(l==r) { tree[rt].num=tree[rt].len=0; lb[rt]=rb[rt]=0; } else //未整段覆盖; { tree[rt].num=tree[rt<<1].num+tree[rt<<1|1].num; tree[rt].len=tree[rt<<1].len+tree[rt<<1|1].len; lb[rt]=lb[rt<<1];rb[rt]=rb[rt<<1|1]; if(lb[rt<<1|1]&&rb[rt<<1])//此线段已相连 tree[rt].num-=2; } } void updata(int L,int R,int c,int l,int r,int rt) { if(l>=L&&R>=r) { tree[rt].cnt+=c; getlen(l,r,rt); return ; } int m=(l+r)/2; if(m>=L) updata(L,R,c,lson); if(R>m) updata(L,R,c,rson); getlen(l,r,rt); } int find(int val,int len) { int l,r,m; l=0; r=len; while(l<=r) { m=(l+r)/2; if(val==mark[m]) return m; else if(val>mark[m]) l=m+1; else r=m-1; } return -1; } int main() { int i,n,m; while(scanf("%d",&n)!=EOF) { int x1,y1,x2,y2; m = 0; for(i=0;i<n;i++) { scanf("%d %d %d %d",&x1,&y1,&x2,&y2); s[m].l = x1; s[m].r = x2; s[m].h = y1; s[m].f = 1; mark[m++] = x1; s[m].l = x1; s[m].r = x2; s[m].h = y2; s[m].f = -1; mark[m++] = x2; } sort(mark,mark+m); sort(s,s+m,cmp); int k = 1; for(i=1;i < m;i++) { if(mark[i]!=mark[i-1]) mark[k++]=mark[i]; } build(0,k-1,1); int ans=0; int past=0; for(i=0;i<m;i++) { int l=find(s[i].l,k-1); int r=find(s[i].r,k-1)-1; updata(l,r,s[i].f,0,k-1,1); ans+=(tree[1].num*(s[i+1].h-s[i].h)); ans+=abs(tree[1].len-past); past=tree[1].len; } printf("%d ",ans); } }