백준[5419] 북서풍

문제 설명

문제 링크

http://icpc.me/5419

5419번: 북서풍

풀이

스위핑과 세그먼트 트리를 이용하여 풀이할 수 있다.

y좌표를 좌표압축을 한 후에 x좌표 기준 오름차순 정렬하고 만약 x좌표가 같다면 y좌표가 큰 순으로 정렬한다.

k번째 점과 쌍이 될 수 있는 점의 수는  x좌표가 k보다 작고, y좌표는 k보다 크거나 같은 점의 수이다.

이때 이 점들을 전탐색하면 O(N^2)으로 시간이 터져버린다.

그렇기 때문에 k번째 점과 쌍이 될 수 있는 점의 수를 세그먼트 트리를 이용하여 시간을 줄여줘야 한다.

k의 y좌표 ~ 범위 끝까지의 수를 가져오면 빠르게 수를 구할 수 있다.

세그먼트 트리를 이용하여 k번째 점과 쌍이 될 수 있는 점의 수를 O(logN)만에 가져오면 O(NlogN)에 해결할 수 있다.

코드

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

ll tree[75000 * 4];
ll tmp[75003];
pll arr[75003];

ll query(ll node, ll s, ll e, ll qs, ll qe) {
    if (e < qs || qe < s) return 0;
    if (qs <= s && e <= qe) return tree[node];
    ll mid = (s + e) >> 1;
    return query(2 * node, s, mid, qs, qe) + query(2 * node + 1, mid + 1, e, qs, qe);
}

void update(ll node, ll s, ll e, ll idx) {
    if (idx < s || e < idx) return;
    tree[node]++;
    if (s == e) return;
    ll mid = (s + e) >> 1;
    update(2 * node, s, mid, idx);
    update(2 * node + 1, mid + 1, e, idx);
}

void solve() {
    memset(tree, 0, sizeof tree);
    ll n; scanf("%lld", &n);
    for (ll i = 0; i < n; i++) {
        scanf("%lld %lld", &arr[i].first, &arr[i].second);
    }
    sort(arr, arr + n, [](pll &a, pll &b) { return a.second < b.second; });

    ll cnt = 0;
    for (ll i = 0; i < n; i++) {
        if (i > 0 && arr[i].second != arr[i - 1].second) cnt++;
        tmp[i] = cnt;
    }
    for (ll i = 0; i < n; i++) arr[i].second = tmp[i];

    sort(arr, arr + n, [](pll &a, pll &b) {
        if (a.first == b.first) return a.second > b.second;
        return a.first < b.first;
    });

    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        ans += query(1, 0, 75000, arr[i].second, 75000);
        update(1, 0, 75000, arr[i].second);
    }
    printf("%lld\n", ans);
}

int main() {
    ll t; scanf("%lld", &t);
    while (t--) {
        solve();
    }
}