HDU 1828 선분 트 리 의 스캐닝 라인 의 둘레 와

클릭 하여 링크 열기
제목: n 개의 사각형 을 주 고 겹 친 후의 둘레 를 구하 세 요.
사고: 선분 나무의 스캐닝 라인 으로 아래 에서 위로 한 번 훑 어 보 세 요. 면적 과 사상 이 비슷 한 면적 이 있 고 아래 의 무 거 운 변 의 처리 가 비슷 하지만 둘레 가 길 고 요구 하 는 것 은 세로 변 의 개 수 를 곱 한 다음 에 높이 를 곱 하 는 것 입 니 다. 면적 과 구 하 는 것 은 바닥 의 길이 곱 하기 높이 입 니 다. 여기 서 저 희 는 구간 이 합 쳐 질 때의 lnum 과 rnum 을 사 용 했 습 니 다. 구체 적 인 아래 에 주석 이 있 습 니 다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=50010;
int num[maxn*4],num1[maxn*4],X[maxn],numseg[maxn*4];//numseg            
bool lnum[maxn*4],rnum[maxn*4];//num         
//lsum                   ，rsum              ，           
struct edge{
    int l,r,h,s;//s 1   ， -1   
    edge(){}
    edge(int a,int b,int c,int d) : l(a),r(b),h(c),s(d) {}
    bool operator <(const edge &n) const{
        if(n.h==h) return s>n.s;
        return h<n.h;
    }
}ss[maxn];
void pushup(int le,int ri,int node){
    if(num1[node]){
        lnum[node]=rnum[node]=1;
        num[node]=ri-le+1;//            ，       
        numseg[node]=2;//      ，      
    }else if(le==ri) num[node]=lnum[node]=rnum[node]=numseg[node]=0;
    else{
        lnum[node]=lnum[node<<1];
        rnum[node]=rnum[node<<1|1];
        num[node]=num[node<<1]+num[node<<1|1];
        numseg[node]=numseg[node<<1]+numseg[node<<1|1];
        if(lnum[node<<1|1]&&rnum[node<<1]) numseg[node]-=2;
        //                    1  ，          ，    2
    }
}
void update(int l,int r,int add,int le,int ri,int node){
    if(l<=le&&ri<=r){
        num1[node]+=add;
        pushup(le,ri,node);
        return ;
    }
    int t=(le+ri)>>1;
    if(l<=t) update(l,r,add,le,t,node<<1);
    if(r>t) update(l,r,add,t+1,ri,node<<1|1);
    pushup(le,ri,node);
}
int main(){
    int n;
    while(scanf("%d",&n)!=-1){
        int k=0,lmax=999999,rmax=-999999;//       ，      ，                
        for(int i=0;i<n;i++){
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            lmax=min(lmax,a);
            rmax=max(rmax,c);
            ss[k++]=edge(a,c,b,1);
            ss[k++]=edge(a,c,d,-1);
        }
        sort(ss,ss+k);
        int ans=0,last=0;
        for(int i=0;i<k;i++){
            if(ss[i].l<ss[i].r) update(ss[i].l,ss[i].r-1,ss[i].s,lmax,rmax-1,1);
            ans+=numseg[1]*(ss[i+1].h-ss[i].h);//             
            ans+=abs(num[1]-last);//       ，       ，    ，              
            last=num[1];//     last       ，num[1]  last      ，       
        }               //    num[1]  last         ，     -1，          ，
                        //        ，            
        printf("%d
",ans);
    }
    return 0;
}