boj 17131 - 여우가 정보섬에 올라온 이유

목차

개요 요약

개요

설명

코드

테스트 케이스

---

개요 요약

1. y좌표가 높은 별부터 시작해서 아래로 sweeping을 합니다.
2. 특정 별 A를 기준으로 좌상단에 별의 개수 $N$, 우상단에 별의 개수 $M$을 각각 segment tree를 통해 구한 후, 곱합니다. $N*M$이 별 A를 기준으로 그릴 수 있는 별자리 개수입니다.
3. $N*M$은 별 A만을 기준으로 삼았을 때입니다. 이를 모든 별에 대해 구해 누적하면 됩니다.
4. 같은 y좌표를 지닌 별들 간에는 별자리를 그릴 수 없습니다. 따라서 같은 y좌표를 가진 별자리들을 batching해서 처리하여야 합니다.

---

개요

이 문제는 [boj 5419 - 북서풍]을 푸셨다면 쉽게 응용할 수 있습니다. 마찬가지로 이번에는 위에서 아래 방향으로 훑어가면서 등장하는 별들의 x좌표를 segment tree에 담아 놓으면 됩니다.

 

다만 생각해야 할 부분은, 좌측과 우측 두 방향을 모두 신경 써줘야 한다는 점이죠. 별자리를 그리기 위한 조건은 현재 처리 중인 별보다 좌상단에 있는 별 하나, 우상단에 있는 별 하나를 고르는 것입니다. 즉, 별 A를 기준으로 좌상단에 별이 $N$개, 우상단에 별이 $M$개 있으면 별 A를 활용해 그릴 수 있는 별자리의 개수는 $N*M$개가 됩니다. 이는 segment tree를 통해 빠르게 구할 수 있습니다.

 

이제 이를 모든 별자리에 대해 구해가며 누적 하면 됩니다. 다만, 같은 y좌표를 지닌 별들 간에는 별자리를 그릴 수 없습니다. 따라서 별 하나 씩 Search→Insert 를 수행하면 같은 y좌표를 지닌 다음 별을 검색할 때 그릴 수 없는 별임에도 불구하고 영향을 주게 됩니다. 따라서 같은 y좌표 끼리는 batching을 통해 한 번에 Search 한 뒤 한꺼번에 Insert하면 됩니다.

위 그림을 살펴볼까요? 별 A와 별 B는 같은 y좌표를 갖고 있습니다. 별들을 하나하나 처리하는 과정에서 A를 B보다 먼저 처리했다고 가정합시다. 이 때, A를 처리한 뒤 바로 segment tree에 넣는다면 어떻게 될까요?

 

그러면, B가 segment tree를 통해 좌측과 우측의 별의 개수를 구할 때, 좌측은 2개, 우측은 1개가 검색될 것입니다! 사실 별 A는 별 B와 별자리를 그릴 수 없는데 개수에 포함된 것입니다..

 

그래서 이를 방지하기 위해서, 같은 y좌표를 지닌 별들의 경우 vector에 잠시 저장해둔 뒤, y좌표가 달라지면 한꺼번에 search해서 별자리 개수를 구한 뒤, insert 하는 batching 방식을 채택해야 합니다.

---

설명

간단하게 Segment tree와 Sweeping이 어떻게 동작하는지 다음 예제로 살펴볼까요?

5
1 0
1 5
2 5
0 10
3 10

가장 먼저, y좌표 기준 내림차순으로 정렬해야 합니다. x좌표는 상관 없으나, 여기서는 편의를 위해 오름차순으로 번호를 부여하였습니다.

Step 1 : y좌표 10

가장 먼저 10의 y좌표를 지닌 별들부터 살펴보겠습니다. 이는 batching 되어있어서 1번과 2번 별 동시에 Search부터 시작합니다.

 

별에서 자신보다 왼쪽, 오른쪽에 있는 별들의 개수를 구하기 위해서는 [0 ~ 자신의 x좌표-1], [자신의 x좌표+1 ~ N-1] 을 각각 segment tree에서 찾으면 됩니다. 그리고 이 둘을 곱해주면 되는데, 이 별들은 모두 0이므로 정답 값에 변화가 없습니다.

 

그 다음, 1번 별과 2번 별 각각의 x좌표를 segment tree에 등록 해주면 됩니다.

 

Step 2 : y좌표 5

이제 y좌표가 5인 별들을 살펴볼까요? 별 3, 4가 같은 y좌표여서 batching되어 있습니다.

 

별 3을 기준으로 왼쪽에 있는 별들의 수는 [0 ~ 0]의 부분합 node를 살펴보면 됩니다. 이 값은 1이네요. 마찬가지로 오른쪽에 있는 별들의 수는 [2 ~ 3]입니다. 이 값도 1이네요.

따라서 별 3을 기준으로 그릴 수 있는 별자리는 1개입니다. 이 값을 ANS에 더해줍시다.

 

 

별 4에 대해서도 마찬가지 입니다. 위처럼 [0 ~ 1]의 값 1과 [3 ~ 3]의 값 1을 곱해서 ANS에 더해주면 됩니다.

 

이제 가능한 별자리 개수의 파악은 끝났으니, segment tree에 x좌표를 저장해주면 되겠죠?

 

Step 3: y좌표 0

이제 마지막 별 5번에 대해서 살펴봅시다.

마지막 별 5의 x좌표는 1입니다. 따라서 [0 ~ 0]의 node값 1과 [2 ~ 3]의 node값 2를 곱해 ANS에 더해주면 됩니다.

이 예제의 정답은 4입니다!

---

코드

1. 이 코드에서는 좌표 압축을 수행했습니다. 그러나 x좌표의 범위가 넓지 않으므로 좌표 자체를 segment tree index로 사용해도 괜찮습니다.
2. 여러 풀이가 존재합니다. 이 포스트와는 반대로 미리 segment tree에 전부 추가해 놓은 뒤, 가장 아래의 y좌표부터 시작해서 구해 나가는 방법이 있습니다. 이 때는 같은 y좌표를 동시에 제거해줘야 합니다. (Batching vector가 필요 없으므로 메모리 상으로 이 포스트보다 조금 효율적일 듯 합니다. 대신에 segment tree의 초기화에서 시간 상으로 약간의 비용이 추가됩니다.)

※주의할 점

1. Modular 연산을 요구합니다. 따라서 중간 과정에서 Modular 연산을 하는 것을 잊지 말아야 합니다.
2. Segment tree의 Search는 return type이 long 이어야 합니다. (혹은 Search 후 곱할 때 type casting을 필요로 합니다.)
3. Batching을 필요로 한다는 것을 잊지 마세요!

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#define IMAX 2147483647
#define MOD 1000000007
using namespace std;

int N;
typedef struct vec{
        int x,y;
}Vec;
Vec arr[200000];

bool cmpX(const Vec& a, const Vec& b){
        return a.x < b.x;
}
bool cmpY(const Vec& a, const Vec& b){
        return a.y > b.y;
}

//좌표 압축은 선택
void compress(){
        sort(arr, arr+N, cmpX);
        int prev = IMAX, rank=-1;
        for(int i=0;i<N;i++){
                if(prev != arr[i].x) rank++;
                prev = arr[i].x;
                arr[i].x = rank;
        }
        sort(arr, arr+N, cmpY);
}
class Tree{
        public:
        int node[800000];

        void Insert(int cur, int left, int right, int index, int val){
                if(left==right){
                    node[cur] += val;
                    return;
                }
                int mid = (left+right)/2;
                if(index <= mid) Insert(cur*2, left, mid, index, val);
                else Insert(cur*2+1, mid+1, right, index, val);
                node[cur] = node[cur*2]+node[cur*2+1];
        }
        long Search(int cur, int left, int right, int start, int end){
                if(left>end || right < start) return 0;
            if(left <= start && right >= end) return node[cur];
            int mid = (start+end)/2;

            long sum = 0;
            if(left<=mid) sum += Search(cur*2, left, right, start, mid);
            if(right>mid) sum += Search(cur*2+1, left, right, mid+1, end);
            return sum;
        }
};

Tree* t = new Tree();
vector<int> batch_y;

long batch_process(){
        long ret = 0;

                //모든 batch된 data들에 대해 가능한 별자리 개수를 구함
        for(auto itr = batch_y.begin(); itr != batch_y.end(); itr++){
                ret = (ret + t->Search(1, 0, *itr-1, 0, N-1)*t->Search(1, *itr+1, N-1, 0, N-1))%MOD;
        }

                //모든 batch된 data들을 segment tree에 추가
        for(auto itr = batch_y.begin(); itr != batch_y.end(); itr++){
                t->Insert(1, 0, N-1, *itr, 1);
        }
        return ret;
}
int main(){
        scanf("%d",&N);
        for(int i=0;i<N;i++){
                scanf("%d %d",&arr[i].x, &arr[i].y);
        }
        compress();
        long ans=0;
        int past_y=IMAX;
        for(int i=0;i<N;i++){
                if(past_y != arr[i].y){
                                                //y좌표가 다른 경우 현재까지 저장된 batch들을 한 번에 처리
                        ans = (ans+batch_process())%MOD;
                        batch_y.clear();
                        past_y = arr[i].y;
                }
                batch_y.push_back(arr[i].x);
        }

        ans = (ans+batch_process())%MOD;
        printf("%ld\n",ans);
        return 0;
}

 

---

테스트 케이스

testcase.txt

2.01MB

단순하지만 범위를 넘어서는 test case입니다.

해당 input의 정답은 690662973 입니다.