[BOJ 11012]

문제 바로가기 : https://www.acmicpc.net/problem/11012
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

스위핑 + 세그먼트 트리(Lazy Propagation)로 풀었다.
Persistent segment tree로 풀 수 있는 널리 알려진 문제라고 하는데.. 안써도 풀 수 있대서 도전해봤다.
다음에는 꼭 익혀서 다른 유형도 풀 수 있도록 해보자!

문제를 간단히 하면, 각 점이 속하는 직사각형 개수들의 합을 출력하면 된다. (직사각형은 여러 개가 있을 수 있다)
이 문제도 역시 사각형의 두 세로선을 분리시켜 담는데서 시작한다.
스위핑을 위해서 점들과 선들을 x를 기준으로 오름차순으로 정렬한다. 선은 시작선이 끝선보다 먼저 오도록 한다.

//세로선
struct line {
    int x, b, t, start;

    line(int x, int b, int t, int start) : x(x), b(b), t(t), start(start) {}
    //세로선 정렬 기준
    bool operator<(line& l) { return x == l.x ? start > l.start : x < l.x; }
};
...

//input
int n, m; cin >> n >> m;
//folks
for (int i = 0; i < n; i++) {
    int x, y; cin >> x >> y;
    folk.push_back({ x, y });
}
//areas
for (int i = 0; i < m; i++) {
    int l, r, b, t; cin >> l >> r >> b >> t;
    lines.push_back({ l, b, t, 1 });
    lines.push_back({ r, b, t, -1 });
}
sort(folk.begin(), folk.end());
sort(lines.begin(), lines.end());

점들이 몇 개의 사각형에 속하는지 체크하는 방법이 뭐가 있을지 생각을 해봤는데, 크게 좋은 생각이 떠오르진 않았다.
x, y 정보를 모두 담는 배열을 선언하자니 메모리가 부족하고, 세로선을 탐색하면서 속하는 점을 세는건 비효율적이었다.
마지막으로 닿은 생각은 점들을 차례대로 탐색하되 선들에 대한 정보를 업데이트한 상태에서 답을 갱신하는 것이었다.
때문에 for loop의 i는 점들의 순서(folk[i])를 의미한다. 점이 정해지면 그 점의 위치까지 세로선 정보를 업데이트한다.
원래 소스에서 위 설명 위주로 간단히 줄였다.

int id = 0;
line cur = lines[0];
for (int i = 0; i < n; i++) {
  //i번째 점까지 선(cur)의 정보를 업데이트
  //선들의 정보 = 직사각형 개수 정보
  while (cur.x <= folk[i].first) {
    //[b, t]를 시작선이면 1을, 끝선이면 -1을 업데이트
    uplast_modified_at_range(1, 0, MAX - 1, cur.b, cur.t, cur.start);
    cur = lines[++id];
  }
  ret += sum(1, 0, MAX - 1, folk[i].second);
}

다만 이대로 컴파일하면 line의 인덱스를 가리키는 id가 범위를 벗어나 런타임 에러가 발생한다.
그래서 if(id<lines.size()-1)로 걸어주면 직사각형이 겹치는 선과 그 위에 있는 점때문에 반례가 발생한다.
이후 답을 여러번 갱신되지 않도록 하기 위해 resulted를 만들었다. 근데 문제가 또 발생했다.
겹치는 선 위에 점이 여러개면 반례가 또 발생한다. 때문에 끝선 정보를 업데이트하기 전에 점의 개수만큼 답을 갱신한다.
여기서 사용된 인덱스(idx)는 i를 갖고와서 시작했기 때문에 i에 다시 반영시켜준다. 근데 또 범위를 벗어나 런타임 에러가..

그렇다. 에러의 연속이다. 그래서 이렇게 저렇게 예외 처리를 하면서 극적으로 통과했다.
아이디어는 생각보다 복잡하지 않을거 같아서 희망을 품고 짜봤는데 많이 더러워졌다😶
그럴듯한 계획을 짰는데 실전에서 신나게 뚜들어 맞고 숨고 피하고 도망갔다가 결국 목표에 도달한 느낌.
앞으로 많은 경험을 쌓아보고 성장하라고 하는 문제인거 같다.
[단계별로 풀어보기 - 스위핑] 마지막 문제가 드디어 끝났다!