본문 바로가기

알고리즘 관련/BOJ

BOJ)3392 화성 지도

문제: icpc.me/3392


지도가 주어졌을 때 전체 지도의 면적을 출력하는 문제이다.


X,Y좌표가 최대 3만까지 들어오기 때문에 O(X*Y)완전 탐색으로 문제를 해결하기에는 무리가 있다.


우리는 지도의 세로축들을 쿼리로 관리하여 x좌표 ,y좌표1, y좌표2 그리고 끝나는 변인지 시작하는 변인지 변수로 관리를 해준다.


이제 쿼리들을 X좌표 기준으로 정렬을 해보자.


쿼리를 순서대로 볼건데 시작하는 변인 쿼리는 y1~y2구간을 1씩 증가시켜줄것이고 끝나는 변인 쿼리는 y1~y2구간을 1씩 감소시켜 줄것이다.


쿼리를 세그먼트 트리에 업데이트 해주기 전에 우리는 가장 최근에 처리한 쿼리의 x좌표와 현재 처리중인 x좌표의 차이를 dx라고 할때 


현재 확인중인 x좌표까지의 면적을 dx*(업데이트 된 y좌표의 개수)로 구할 수 있다.


이때 주의해야 할 점은 y좌표를 우리는 1증가 감소로 업데이트 시키지만 우리가 트리에서 얻어와야할 쿼리는 1이상인 y좌표의 개수이다. 그냥 구간합을 출력하면 오답이 나온다는 소리다.


이를 처리해주기 위하여 카운트 배열을 따로 생성하여 

=>1.카운트배열이 1이상인 경우 그 구간 전체가 y좌표가 1이상이므로 y-x+1을 return

=>2. 1번이 아닌경우 리프노드일 경우 0을 return해주고 아닐 경우 자식 노드의 합을 return 해준다.


이러한 방식으로 쿼리를 계산해주어 전체 면적을 구해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <algorithm>
#define MAX_N 10000
#define MAX_Y 30000
using namespace std;
struct m {
    int x, y1, y2, z;
};
bool cmp(m a, m b) {
    return a.x < b.x;
}
int n, seg[* MAX_Y], a, b, c, d, cnt[* MAX_Y], last, res;
m arr[* MAX_N];
void update(int lo, int hi, int val, int node, int x, int y) {
    if (y < lo || hi < x)
        return;
    if (lo <= x&&<= hi)
        cnt[node] += val;
    else {
        int mid = (x + y) >> 1;
        update(lo, hi, val, node * 2, x, mid);
        update(lo, hi, val, node * + 1, mid + 1, y);
    }
    if (cnt[node])seg[node] = y - x + 1;
    else {
        if (x == y)seg[node] = 0;
        else seg[node] = seg[node * 2+ seg[node * + 1];
    }
}
int main() {
    scanf("%d"&n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d%d"&a, &b, &c, &d);
        arr[i] = { a,b,d - 1,};
        arr[i + n] = { c,b,d - 1,-};
    }
    sort(arr, arr + * n, cmp);
    for (int i = 0; i < * n; i++) {
        if (i) {
            int dx = arr[i].x - last;
            res += dx*seg[1];
        }
        update(arr[i].y1, arr[i].y2, arr[i].z, 10, MAX_Y);
        last = arr[i].x;
    }
    printf("%d\n", res);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1561 놀이 공원  (0) 2017.01.14
BOJ)1666 최대 증가 직사각형 집합  (2) 2017.01.14
BOJ)2336 굉장한 학생  (0) 2017.01.13
BOJ)1395 스위치  (0) 2017.01.13
BOJ)10999 구간 합 구하기2  (1) 2017.01.13