WA的代码如下
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
struct e{
int left,right,height,flag;
};
e edge[10001];
int sum[80001],num[80001],len[80001],L[80001],R[80001];
int eCnt,n,xmax=-99999,xmin=99999,last,ans;
bool lp[80001],rp[80001];
void addEdge(int l,int r,int h,int f){
eCnt++;
edge[eCnt].left=l;
edge[eCnt].right=r;
edge[eCnt].height=h;
edge[eCnt].flag=f;
}
bool cmp(e x,e y){
if(x.height==y.height)
return x.flag<y.flag;
return x.height<y.height;
}
void pushup(int x){
if(sum[x]){
num[x]=1;
len[x]=R[x]-L[x]+1;
lp[x]=rp[x]=true;
}
else
if(L[x]==R[x]){
len[x]=0;
num[x]=0;
lp[x]=rp[x]=false;
}
else{
len[x]=len[x<<1]+len[x<<1|1];
num[x]=num[x<<1]+num[x<<1|1];
if(rp[x<<1]&&lp[x<<1|1])
num[x]--;
lp[x]=lp[x<<1];
rp[x]=rp[x<<1|1];
}
}
void build(int x,int l,int r){
L[x]=l;
R[x]=r;
if(l==r)
return;
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
}
void add(int x,int l,int r,int v){
if(L[x]>=l&&R[x]<=r){
sum[x]+=v;
pushup(x);
return;
}
int mid=(L[x]+R[x])>>1;
if(l<=mid)
add(x<<1,l,r,v);
if(r>mid)
add(x<<1|1,l,r,v);
pushup(x);
}
int main(){
scanf("%d",&n);
while(n--){
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
xmax=max(xmax,max(x1,x2));
xmin=min(xmin,min(x1,x2));
addEdge(x1,x2,y1,1);
addEdge(x1,x2,y2,-1);
}
for(int i=1;i<=eCnt;i++){
edge[i].left+=-xmin+1;
edge[i].right+=-xmin+1;
}
xmax-=xmin;
sort(edge+1,edge+eCnt+1,cmp);
build(1,1,xmax);
for(int i=1;i<=eCnt;i++){
add(1,edge[i].left,edge[i].right-1,edge[i].flag);
while(edge[i].height==edge[i+1].height&&edge[i].flag==edge[i+1].flag){
i++;
add(1,edge[i].left,edge[i].right-1,edge[i].flag);
}
ans+=abs(len[1]-last);
last=len[1];
ans+=2*num[1]*(edge[i+1].height-edge[i].height);
}
printf("%d",ans);
return 0;
}
```
by Cobalt @ 2018-09-06 19:48:58
貌似说反了,1是下边
by Cobalt @ 2018-09-06 20:32:14
@[Cobalt](/space/show?uid=57592)
考虑一个矩形的上边和另一个矩形的下边重合
若先处理下边,则该重合的边会记录进周长
by 青梧 @ 2018-09-07 16:05:05
@[GTX_TITAN](/space/show?uid=37534) 好有道理。。。
非常感谢
by Cobalt @ 2018-09-07 16:06:26