5419번: North-Western Winds

https://www.acmicpc.net/problem/5419


$O(tn\lg n)$

x축 정렬하고 보면 y 성분 값이 감소하거나 같은 쌍의 개수를 구하는 문제가 된다.
fenwick tree를 이용해서 해결한다.

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
const int MXN = 75e3;
int t, n, sz, bit[MXN + 1];
pair<int, int> p[MXN];
int main() {
    for (scanf("%d", &t); t--;) {
        map<int, int> mp;
        long long r = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d%d", &p[i].first, &p[i].second), mp[p[i].second *= -1] = 0;
        sort(p, p + n);
        sz = 0;
        for (auto &it : mp) it.second = ++sz, bit[sz] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = mp[p[i].second]; j; j -= j&-j) r += bit[j];
            for (int j = mp[p[i].second]; j <= sz; j += j&-j) bit[j]++;
        }
        printf("%lld\n", r);
    }
    return 0;
}