문제

www.acmicpc.net/problem/5419


알고리즘

스위핑, 세그먼트 트리


풀이

북서풍으로 인해 동쪽과 남쪽에 있는 섬으로만 항해가 가능할 때, 가능한 쌍의 수를 묻고 있습니다.

이전에도 소개했던 문제들 중 inversion count 문제가 있습니다. 그 문제도 inversion이 발생하는 쌍을 count 하는 문제입니다. 브루트 포스로 $O(N^2)$에 해결 가능하지만 세그먼트 트리를 활용하면 $O(NlogN)$에 해결 가능합니다.

이 문제또한 가능한 쌍을 묻고 있으며, 지금까지 지나온 섬들을 세그먼트 트리에 업데이트를 하면 보고 있는 섬마다 $O(logN)$에 지나온 섬의 개수를 알 수 있습니다.

섬을 정렬한 후 순차적으로 쿼리와 업데이트를 진행합니다. x좌표가 같을 때는 y좌표가 큰 섬에서 y좌표가 작은 섬으로 항해 가능하므로, 섬을 정렬하는 과정에서 x좌표가 같을 땐 y좌표가 큰 섬이 앞의 인덱스로 오게 하면 됩니다. 문제에서 요구하는 쿼리를 풀어서 설명하자면 " 지금까지 지나온 섬들 중에서 현재 보고 있는 섬보다 y좌표가 같거나 큰 섬들의 개수"입니다. 즉 세그먼트 트리 구간합 쿼리와 일치하며 열심히 구현하면 됩니다.

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

typedef pair<int, int> pii;

const int MAX_N = 75000;

int tc,N,S;
int Y[MAX_N+1],fenwick[MAX_N+1];
pii pos[MAX_N+1];
long long ans;

bool cmp(const pii & a, const pii & b) {
    if (a.first == b.first) return a.second > b.second;
    return a.first < b.first;
}

void update(int idx, int val) {
    while (idx <= S) {
        fenwick[idx] += val;
        idx += idx & -idx;
    }
}

int query(int idx) {
    int ret = 0;
    while (idx) {
        ret += fenwick[idx];
        idx -= idx & -idx;
    }
    return ret;
}

int main() {
    FAST;
    cin >> tc;
    while (tc--) {
        cin >> N;

        rep(i, N) {
            auto& [x, y] = pos[i];
            cin >> x >> y;
            Y[i] = y;
        }

        sort(pos, pos + N, cmp);
        sort(Y, Y + N);
        S = unique(Y, Y + N) - Y;

        memset(fenwick, 0, sizeof(fenwick));
        ans = 0;
        rep(i, N) {
            int p = lower_bound(Y, Y + S, pos[i].second) - Y+1;
            ans += query(S) - query(p-1);
            update(p, 1);
        }
        cout << ans << '\n';
    }

    return 0;
}