[BOJ 17611]

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

solution with segment tree (lazy propagation)

가로, 세로에서 각 최소 구간당 최댓값을 얻어서 출력하는 문제다.
처음에 읽으면서 lazy propagation이 아닌 풀이는 떠오르지 않았다. 근데 골드 1이라니? 그럴리 없어
구간별로 일일이 더해주면 TLE를 받을거 같아서 결국 생각난대로 풀어봤다.
두 점의 위치가 l, r일 때(물론 비교 대상인 x, y가 동일하다는 가정) [l+1, r]에 업데이트 해줘야 한다.
이 부분만 신경쓴다면 구현은 상당히 간단한 편이다. 알고리즘이 훨씬 복잡해 보인다.

solution with sweeping

이 문제에 가장 최적화 된 답은 스위핑인거 같다.
세그먼트 트리를 같이 사용하는 스위핑도 있지만.. 여기서는 세그먼트 트리를 사용하지 않는다.

input으로 들어오는 값은 (x, y)이다. 꼭짓점을 의미하는데 이 값을 받을 때마다 process()에서 처리한다.
다만 직전에 입력받은 input을 기준으로 같이 process()에 넣어준다.
그리고 x 또는 y를 비교하면서 벡터(R or H)에 넣는다. 작은 값은 시작한다는 의미에서 1을, 큰 값은 -1을 넣는다.

void process(int x1, int x2, int y1, int y2) {
    if (x1 > x2) swap(x1, x2);
    if (y1 > y2) swap(y1, y2);
    //작은값에는 1을, 큰값에는 -1 넣기
    //시작점, 끝점 구별 및 정답 계산에 도움을 줌
    if (x1 != x2) {
        R.push_back({ x1, 1 });
        R.push_back({ x2, -1 });
    }
    else {
        H.push_back({ y1, 1 });
        H.push_back({ y2, -1 });
    }
}

input을 다 받고난 후에는 R, H를 정렬해준다. x 또는 y가 같을 때 start는 -1이 먼저오게 해야한다.
이후에는 start값을 계속 반영하면서 최댓값을 뽑아준다.