[백준] 3392 - 화성 지도 (c++)

https://www.acmicpc.net/problem/3392

 

문제 요약

직사각형이 N개 구어진다. 직사각형끼리 서로 겹칠 수 있다고 할 때 직사각형들이 차지하는 전체 면적을 구해라.

 

풀이 (Nlog(3e4))

• 스위핑
• 세그먼트 트리

https://gkgkgkgkgkgkgk.tistory.com/21

[백준] 2672 - 여러 직사각형의 전체 면적 구하기 (c++)

면적을 구하는 아이디어는 이 문제와 같다. 하지만 제한이 커서 세그먼트 트리로 최적화를 해야 한다. 처음엔 단순히 lazyseg 쓰면 될 줄 알았는데 직사각형을 포함하는 y좌표만 세는 query가 필요해서 아이디어가 조금 더 필요했다. 일반세그를 두 개 쓰는 테크닉을 찾아서 풀었는데 스위핑 한정으로 쓸 수 있을 것 같다. 이 분 블로그에 자세히 설명 돼있다.

https://ps.mjstudio.net/0-1-segment-tree

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mid (st+en>>1)
const int N=30002;

ll seg[N*4], cnt[N*4];

void update(int st, int en, int n, int l, int r, ll x) {
    if (st > r || en < l)
        return;
    if (st >= l && en <= r) 
        seg[n] +=x;
    else  
        update(st,mid,n*2,l,r,x),update(mid+1,en,n*2+1,l,r,x);
    
    if(seg[n])
        cnt[n]=en-st+1;
    else {
        if(st==en)cnt[n]=0;
        else cnt[n]=cnt[n*2]+cnt[n*2+1];
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;cin>>n;
    vector<array<int,4>> v;
    for(int i=0,x1,x2,y1,y2;i<n;i++) 
        cin>>x1>>y1>>x2>>y2,v.push_back({x1,y1,y2,1}),v.push_back({x2,y1,y2,-1});
    
    sort(v.begin(),v.end());
    ll sum=0,l=0;
    for(auto [x,y1,y2,a]:v) {
        sum+=(x-l)*cnt[1];
        update(0,30000,1,y1,y2-1,a  );
        l=x;
    }
    cout<<sum;
}