BOJ 7626 직사각형

문제

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

직사각형 여러개가 주어졌을 때, 그 합집합의 넓이를 구하는 문제이다.

 

풀이

이 문제에 대한 풀이는 https://codedoc.tistory.com/421 에 매우 자세히 나와 있다.

 

직사각형들의 x좌표에 대해 직사각형의 왼쪽 변은 +1, 오른쪽 변은 -1을 해주는 이벤트로 생각할 수 있다.

따라서 그러한 이벤트들을 모두 x좌표에 대해 정리한 후 오른쪽으로 쭉 한번 훑어주면서 넓이를 구할 수 있다.

 

이제 잘 나눈 x좌표들에 대한 구간으로 그 구간 사이의 넓이만 구해주면 된다.

x좌표들에 대한 이벤트로 정렬을 때린 후 구간을 나눴으니, 하나의 구간 내에선 구해야 하는 영역의 넓이는 변하지 않는다.

 

따라서 이벤트들을 잘 관리해주는 자료구조가 필요하다. 쿼리는

1. 구간에 대한 증감 연산

2. 겹쳐진 부분들을 중복해서 세지 않음

 

이러한 자료구조는 변형된 세그먼트 트리로 풀 수 있다.

세그의 각 노드가 해당 y좌표들의 구간 값 sum, 그 구간 자체가 호출된 횟수 cnt 로 나눠진다.

 

이 세그트리는 다른 세그트리와는 다르게 각 노드의 sum 값이 실제 값들을 저장하고 있지 않는다. 예를 들어 노드V 가 이벤트에서 ++ 되었을때, 실제로는 그 자식들의 값도 ++ 해야하지만, 하지 않는다.

 

세그먼트 트리는

1. 구간에 대한 이벤트가 들어오면 그 구간을 덮는 구간들을 찾아 cnt 를 증감시켜준다.

2. cnt가 0이면, 그 구간 자체에 대해서는 아직 색칠되지 않은 것이기 때문에, 자식노드들의 합을 sum 에 적는다.

3. cnt가 0이 아니라면, 그 구간이 적어도 한번은 호출되었다는 뜻이기 때문에 자식노드들의 합이 아닌, 그 구간 자체의 길이를 더해준다.

 

이렇게 처리한 y좌표 구간의 길이에, x좌표 구간의 x축길이를 곱해주면 된다.

 

주의할 점은, 

x좌표들이 같은 쿼리를 따로 처리해 줄 필요가 없다. 왜냐하면 어짜피 x좌표가 같으면, 0을 곱하는 것과 마찬가지이다.

또한, 세그트리에서 자식들의 값들을 더해줄 때, 그 노드가 이미 리프 노드일 때 예외처리 해주는 것을 잊지 말아야 한다.

 

시간 복잡도 : $O(NlogN)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

struct Line
{
    ll x, y1, y2, val;
    bool operator < (const Line& p) { return x<p.x; }
};

int n;
Line arr[2*MAXN+10];
vector<ll> comp;
ll ans;

int getcomp(ll x)
{
    return lower_bound(comp.begin(), comp.end(), x)-comp.begin();
}

struct SEG
{
    int n; vector<ll> sum, cnt;
    SEG(int n) : n(n), sum(4*n+10), cnt(4*n+10) {}

    void update(int node, int tl, int tr, int l, int r, ll val)
    {
        if(tr<l || r<tl) return;
        if(l<=tl && tr<=r)
        {
            cnt[node]+=val;
            if(cnt[node]!=0) sum[node]=comp[tr]-comp[tl-1];
            else
            {
                if(tl!=tr) sum[node]=sum[node*2]+sum[node*2+1];
                else sum[node]=0;
            }
            return;
        }
        int mid=tl+tr>>1;
        update(node*2, tl, mid, l, r, val);
        update(node*2+1, mid+1, tr, l, r, val);

        if(cnt[node]!=0) sum[node]=comp[tr]-comp[tl-1];
        else
        {
            if(tl!=tr) sum[node]=sum[node*2]+sum[node*2+1];
            else sum[node]=0;
        }
    }

    ll query() { return sum[1]; }
};

int main()
{
    int i, j;
    scanf("%d", &n);
    for(i=0; i<n; i++)
    {
        ll x1, x2, y1, y2;
        scanf("%lld%lld%lld%lld", &x1, &x2, &y1, &y2);
        arr[i*2]={x1, y1, y2, 1};
        arr[i*2+1]={x2, y1, y2, -1};
        comp.push_back(y1); comp.push_back(y2);
    }

    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    sort(arr, arr+n*2);

    SEG seg(comp.size()-1);

    ll bef=arr[0].x;
    for(i=0; i<n*2; i++)
    {
        ans+=(arr[i].x-bef)*seg.query();
        bef=arr[i].x;

        seg.update(1, 1, comp.size()-1, getcomp(arr[i].y1)+1, getcomp(arr[i].y2), arr[i].val);
    }
    printf("%lld", ans);
}