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

핵심 아이디어

어떤 점 $p$에 대해서$p$ $y \leq p_y,\ x\geq p_x$ 인 점들은 $p$와 항해할 수 있는 쌍을 이룬다.

<aside> 💡

$y$값이 작은 순서대로 보면서 $x$값에 대해 inversion counting을 하면 된다.

이때 $-10^9\leq x \leq 10^9$이므로 좌표압축을 해야한다.

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

class Seg
{
    private:
        int n;
        vector<int> tree;

        void upd(int node, int start, int end, int idx, int val)
        {
            if(idx<start || end<idx) return;
            if(start == end){
                tree[node]++;
                return;
            }

            int mid = start+end>>1;
            upd(2*node, start, mid, idx, val);
            upd(2*node+1, mid+1, end, idx, val);

            tree[node] = tree[2*node]+tree[2*node+1];
        }

        int qry(int node, int start, int end, int left, int right)
        {
            if(end<left || right<start) return 0;
            if(left<=start && end<=right) return tree[node];

            int mid = start+end>>1;
            int l = qry(2*node, start, mid, left, right);
            int r = qry(2*node+1, mid+1, end, left, right);

            return l+r;
        }

    public:
        void init(int n)
        {
            this->n = n;
            tree.resize(4*n);
        }

        void upd(int idx, int val) {upd(1, 1, n, idx, val);}
        int qry(int left, int right) {return qry(1, 1, n, left, right);}
};

struct Point
{
    int x, y;
    bool operator<(Point o){
        if(this->y == o.y) return this->x > o.x;
        return this->y<o.y;
    }
};

int n;
Point p[75'001];
vector<int> itov;
int vtoi(int v) {return lower_bound(itov.begin(), itov.end(), v)-itov.begin();}

void solve()
{
    cin >> n;
    Seg cnt;
    cnt.init(n);
    itov.clear();
    itov.resize(n);
    for(int i = 0; i<n; i++){
        cin >> p[i].x >> p[i].y;
        itov[i] = p[i].x;
    }

    sort(itov.begin(), itov.end());
    itov.erase(unique(itov.begin(), itov.end()), itov.end());

    sort(p, p+n);

    ll ans = 0;
    int midx = itov.size();
    for(int i = 0; i<n; i++){
        // cout << p[i].x << " " << p[i].y <<": ";
        int idx = vtoi(p[i].x)+1;
        ans += cnt.qry(idx, midx);
        cnt.upd(idx, 1);
        // cout << ans <<"\\n";
    }
    cout << ans <<"\\n";
}

signed main()
{
    FASTIO;
    int _tc; cin >> _tc;
    while(_tc--) solve();    
    return 0;
}