线段树扫描线矩形周长并

 

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define MAXN 22222using namespace std;int len[MAXN<<2];bool lbd[MAXN<<2],rbd[MAXN<<2];int numseg[MAXN<<2];int cnt[MAXN<<2];struct line{    int s,e,h,type;}L[MAXN];bool cmp(line a,line b){    if(a.h==b.h)return a.type>b.type;    return a.h
        
         =e)    {        cnt[num]+=val;        pushup(num,s,e);        return;    }    int mid=(s+e)>>1;    if(l<=mid)update(num<<1,s,mid,l,r,val);    if(r>mid)update(num<<1|1,mid+1,e,l,r,val);    pushup(num,s,e);}int main(){    int n;    while(scanf("%d",&n)!=EOF)    {        int lmost=10000,rmost=-10000;        int m=0;        for(int i=1;i<=n;i++)        {            int a,b,c,d;            scanf("%d%d%d%d",&a,&b,&c,&d);            lmost=min(lmost,a);            rmost=max(rmost,c);            L[m].s=a;L[m].e=c;L[m].h=b;L[m++].type=1;            L[m].s=a;L[m].e=c;L[m].h=d;L[m++].type=-1;        }        sort(L,L+m,cmp);        int ans=0;        int last=0;//记录更新之前的X周的覆盖区域        for(int i=0;i