레몬 나무에 n개의 레몬이 매달려 있으며, 각각은 두 가지 속성인 시각적 아름다움(a_i)과 신맛 강도(b_i)를 가진다. 특정 레몬 i를 섭취했을 때 얻는 기쁨 값 e_i는 자기 자신을 제외하고, 아름다움과 신맛 모두가 자신 이하인 다른 레몬들의 개수로 정의된다.

즉, 다음 조건을 동시에 만족하는 인덱스 j의 수이다:

• j ≠ i
• a_j ≤ a_i
• b_j ≤ b_i

모든 레몬에 대해 이 값을 계산해야 하며, 입력 크기는 최대 200,000개까지 가능하다. 단순한 이중 반복문 접근은 시간 초과를 유발하므로 효율적인 알고리즘이 필요하다.

해결 전략: 좌표 압축과 분할 정복

이 문제는 전형적인 2차원 편순(2D partial order) 문제로, 한 점이 다른 점보다 "작거나 같다"고 정의될 때 그보다 작은 점의 개수를 세는 문제다. 주어진 조건에서 두 속성이 모두 작거나 같아야 하므로, 이를 효율적으로 처리하기 위해 다음과 같은 방법을 사용한다:

1. 정렬 기반 접근: 첫 번째 기준(예: a_i)으로 정렬한 후, 두 번째 기준(b_i)에 대해 순차적으로 누적 개수를 관리한다.
2. 병합 정렬 응용: 병합 정렬 과정에서 왼쪽 배열의 원소들이 오른쪽 배열의 원소보다 먼저 등장하면, 해당 오른쪽 원소는 왼쪽 원소들 중 일부보다 크다는 의미이므로 개수를 더해줄 수 있다.
3. 동일 요소 처리: 같은 a_i와 b_i 값을 가진 경우가 존재하므로, 사전 처리를 통해 동일한 그룹 내에서의 보정값을 미리 계산해야 한다.

구현 방식

다음은 C++ 기반의 최적화된 구현 예시이다:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Fruit {
    int beauty, sourness, index;
};

bool compareByBeauty(const Fruit& u, const Fruit& v) {
    if (u.beauty != v.beauty)
        return u.beauty < v.beauty;
    return u.sourness < v.sourness;
}

void mergeAndCount(vector<Fruit>& items, vector<int>& result, int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    mergeAndCount(items, result, left, mid);
    mergeAndCount(items, result, mid + 1, right);

    vector<Fruit> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    int leftCounter = 0;

    while (i <= mid || j <= right) {
        if (i <= mid && (j > right || items[i].sourness <= items[j].sourness)) {
            temp[k++] = items[i];
            leftCounter++;
            i++;
        } else {
            result[items[j].index] += leftCounter;
            temp[k++] = items[j];
            j++;
        }
    }

    for (int idx = 0; idx < k; ++idx) {
        items[left + idx] = temp[idx];
    }
}

vector<int> calculateJoy(const vector<int>& beauty, const vector<int>& sourness) {
    int n = beauty.size();
    vector<Fruit> fruits(n);
    for (int i = 0; i < n; ++i) {
        fruits[i] = {beauty[i], sourness[i], i};
    }

    sort(fruits.begin(), fruits.end(), compareByBeauty);

    // 동일한 (beauty, sourness) 그룹 내에서 추가 보정
    vector<int> offset(n, 0);
    for (int i = 0; i < n; ) {
        int j = i;
        while (j < n && fruits[j].beauty == fruits[i].beauty && fruits[j].sourness == fruits[i].sourness)
            j++;
        int groupSize = j - i;
        for (int k = 0; k < groupSize; ++k) {
            offset[fruits[i + k].index] = groupSize - 1 - k;
        }
        i = j;
    }

    vector<int> joy(n, 0);
    mergeAndCount(fruits, joy, 0, n - 1);

    for (int i = 0; i < n; ++i)
        joy[i] += offset[i];

    return joy;
}

입력 예제:

12
9 10 6 1 3 11 2 7 8 4 12 5
12 4 1 3 6 11 7 2 5 10 8 9

출력 결과:

8
3
0
0
1
9
1
1
3
3
7
3

각 단계에서 정렬과 병합을 통해 O(n log n) 시간 복잡도로 문제를 해결하며, 중복 요소에 대한 보정을 통해 정확한 결과를 도출한다.