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

백준 17131번: 여우가 정보섬에 올라온 이유

아이디어

스위핑을 두 번 해주면 된다. 왼쪽부터 훑으면서 나보다 y좌표가 큰 별이 몇개인지 세고, 오른쪽부터 훑으면서 나보다 y좌표가 큰 별이 몇개인지 센 후에 곱해주면 된다.

셀때 y좌표는 무조건 작은걸 먼저 세야 한다 큰걸 먼저 세면 x좌표가 같은 별도 포함하기 때문. 따라서 그냥 정렬하고 정순, 역순으로 탐색하면 안되고 {x, y}, {-x, y}로 x좌표가 같을 경우 y좌표는 오름차순으로 정렬되도록 해야 한다. 또한 같은 별끼리 곱해주기 위해 처음 입력받을 때 입력받은 순서도 함께 기록한다.

코드

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX = 200000, MOD = 1e9+7;
int N;
vector<pair<pair<int, int>, int>> arr, rarr;
vector<int> tree(8*MAX, 0);

void update(int start, int end, int idx, int node) {
    if (idx < start || end < idx) return ;
    if (start == end) {
        tree[node]++;
        return;
    }
    update(start, (start+end)/2, idx, node*2);
    update((start+end)/2+1, end, idx, node*2+1);
    tree[node] = tree[node*2] + tree[node*2+1];
}

long long query(int start, int end, int left, int right, int node) {
    if (end < left || right < start) return 0;
    if (left <= start && end <= right) return tree[node];
    return (query(start, (start+end)/2, left, right, node*2) + query((start+end)/2+1, end, left, right, node*2+1))%MOD;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        arr.push_back({{x, y}, i});
        rarr.push_back({{-x, y}, i});
    }

    sort(arr.begin(), arr.end());
    sort(rarr.begin(), rarr.end());
    vector<long long> cnt(N);

    for (auto i = arr.begin(); i != arr.end(); i++) {
        int y = (*i).first.second + MAX;
        int idx = (*i).second;
        cnt[idx] = query(0, 2*MAX, y+1, 2*MAX, 1);
        update(0, 2*MAX, y, 1);
    }

    tree = vector<int>(8*MAX, 0);
    long long ans = 0;

    for (auto i = rarr.begin(); i != rarr.end(); i++) {
        int y = (*i).first.second + MAX;
        int idx = (*i).second;
        long long v = cnt[idx]*query(0, 2*MAX, y+1, 2*MAX, 1);
        ans = (ans+v)%MOD;
        update(0, 2*MAX, y, 1);
    }

    cout << ans << '\n';
    return 0;
}

아이디어

x좌표 같은 경우 처리하기가 좀 빡셌다. 그리고 -20만~20만을 0~40만으로 바꿔서 세그트리에 기록했다. 따라서 세그트리 사이즈는 20만*2*4로 설정했다.