작성한 질문수 29

0

(1, 10) (2, 10) (3, 10) (4, 10) (5, 10) (6, 10) (7, 10) (8, 10) (9, 10) (10, 10)

이렇게 있었을 때 답은 45입니다.

_y는 (-10, -10, -10, -10, -10, -10, -10, -10, -10, -10) ->-1을 곱했기 때문

이렇게 되고 이분 탐색 함수의 반환값 즉 이분탐색 진입 하자마자 mid값 바로 반환하여 idx는 무조건 4가 나옵니다.

find_index의 반환값은 4이고

int idx = find_index(_y, a[i].second) + 1;

이 로직에 의해 idx는 5가 됩니다.

만약 i가 1이라고 했을 때 위의 예제에서 1 10보다 왼쪽에 있는건 0개인데 여기서는 일단 4개라고 치고 그냥 계산을 하는데 왜 이렇게 해도 맞는건지에 대한 설명이 부족한 것 같습니다.

ret += 1LL * sum(idx);update(idx, 1);

결국 5를 9번 더하여 45로 결과는 맞는데

중복 y값을 왜 이렇게해도 맞는지에 대한 설명이 필요합니다.

0

같은 의문점이 생겨 질문드립니다!

y좌표가 같은 두 점이 존재할 경우, find_inedx() 함수를 사용하여 반환되는 인덱스가 동일한데, 로직에 지장이 없는걸까요?

        update(find_index(_y, a[0].second) + 1, 1);
        for(int i = 1; i < n; i++){
            int idx = find_index(_y, a[i].second) + 1;
            ret += 1LL * sum(idx);update(idx, 1);

0

안녕하세요 재윤님 ㅎㅎ

int find_index(const vector<int> & _y, int value){
    int lo = 0, hi = _y.size() - 1;
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        if(_y[mid] == value) return mid;
        if(_y[mid] < value) lo = mid + 1;
        else hi = mid - 1;
    }
}

이부분 말씀하시는거죠?

이 문제는 y의 좌표를 카운팅해야 하는 것입니다. a라는 값 위에 y가 "몇개" 있냐라는 카운팅을 해야하는 것이죠.

자 일단은 y는 하나하나 -10^9 ~ 10^9까지의 범위를 가집니다. 따라서 이걸 카운팅배열로 저장할수도 없는 것이죠.

예를 들어 a[1000000000] = 1 이런식으로 말이죠.

그렇기 때문에 그저 vector v에다가 집어넣고 여기에서 해당 y에 관한 지점을 이분탐색으로 고릅니다. 물론 그냥 선형적으로 탐색할 수도 있지만 이미 정렬이 되어있기 때문에 이분탐색으로 해야 더 빠르기 때문에 이분탐색으로 해당 좌표를 찾는 것입니다.

        for(int i = 1; i < n; i++){
            int idx = find_index(_y, a[i].second) + 1;
            ret += 1LL * sum(idx);update(idx, 1);
        } 

또한 좌표압축을 하는건데 -10^9 ~ 10^9 을 1 ≤ n ≤ 75000 이러한 범위를 가지는 idx로 변환을 시켜서 넣는 것입니다.

그림을 그려보면 다음과 같습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.