题意：
求n个矩阵并后形成的图形的周长
分析：
这题大体思路和求矩阵面积并差不多，但是有所不同
我们可以把所有的线段分为x方向的y方向
首先我们如何求得x方向的线段呢？
和求面积的时候一样我们从下往上扫描那么对于当前扫描的线
我们可以求得这一水平线长度= 目前线段树中覆盖总和-上一次线段树覆盖的总和
我们记上一次覆盖的长度为last
那么第一次插入时候ans+=红色的线
第二次插入的时候ans+=（红色的线+黄色的线）（目前覆盖）-红色的线（之前覆盖）
。。。。。
所以每次ans+=abs（目前覆盖-之前覆盖）
为什么是abs呢？
我们观察到第4次插入的时候目前覆盖的线为（黄色的线加棕色的线加红色的线-绿色的线）上次的覆盖为（黄色的线加棕色的线加红色的线）
相减则是-绿色的线，显然我们需要对之取绝对值
如何计算y方向的线呢
如果我们知道当前线段树中有几段线段，那么我们就可以另△h*numseg*2就好了
那么在更新线段树的时候我们要考虑到线段合并的情况
用rc和lc存储是否覆盖端点即可
ACcode：
#include <iostream> #include <cstdio> #include <algorithm> #define tmp (st<<1) #define mid ((l+r)>>1) #define lson l,mid,tmp #define rson mid+1,r,tmp|1 #define maxn 20002 #define inf 0x3f3f3f3f using namespace std; int sum[maxn<<2]; int cnt[maxn<<2]; int numseg[maxn<<2]; bool lc[maxn<<2],rc[maxn<<2]; 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 &cmp)const{ if(h==cmp.h)return s>cmp.s; return h<cmp.h; } }ss[maxn]; void push_up(int st,int l,int r){ if(cnt[st]){ sum[st]=r-l+1; numseg[st]=2; lc[st]=rc[st]=1; } else if(l==r)sum[st]=numseg[st]=lc[st]=rc[st]=0; else { sum[st]=sum[tmp]+sum[tmp|1]; numseg[st]=numseg[tmp]+numseg[tmp|1]; lc[st]=lc[tmp]; rc[st]=rc[tmp|1]; if(lc[tmp|1]&&rc[tmp])numseg[st]-=2; } } void update(int L,int R,int c,int l,int r,int st){ if(L<=l&&r<=R){ cnt[st]+=c; push_up(st,l,r); return ; } if(L<=mid)update(L,R,c,lson); if(R>mid)update(L,R,c,rson); push_up(st,l,r); } int main(){ int n,m,a,b,c,d,ans,last,l=inf,r=-inf; while(scanf("%d",&n)!=EOF){ m=0;l=inf;r=-inf; for(int i=0;i<n;++i){ scanf("%d%d%d%d",&a,&b,&c,&d); ss[m++]=Seg(a,c,b,1); ss[m++]=Seg(a,c,d,-1); l=min(l,a); r=max(r,c); } sort(ss,ss+m); ans=last=0; for(int i=0;i<m;++i){ update(ss[i].l,ss[i].r-1,ss[i].s,l,r,1); ans+=numseg[1]*(ss[i+1].h-ss[i].h); ans+=abs(sum[1]-last); last=sum[1]; } printf("%d\n",ans); } return 0; }