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

핵심 아이디어

점 $p$에서 만들 수 있는 V형 별자리의 개수는

$p$보다 $y$좌표가 작은 점들 중 $(p_x\leq x \text{인 점들의 수}) \times(p_x\geq x \text{인 점들의 수})$ 이다.

<aside> 💡

즉 $y$값이 큰 점들부터 $x$값의 개수를 세그먼트 트리에 넣으면서 현재 점$p$의 오른쪽에 있는 점의 수와 왼쪽에 있는 점의 수를 곱해 정답에 더해주면 된다.

이때 왼쪽, 오른쪽에 있는 점들은 $p$보다 $y$값이 더 작아야 하므로 $y$값이 같은 점들은 계산이 끝난뒤에 한번에 업데이트 해야 한다.

$-2\times 10^5 \leq x \leq 2\times 10^5$ 이므로 모든 $x$값에 base를 더해야 한다.

</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;
#define int long long
#define MOD 1'000'000'007

const int base = 200'001;

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);}
};

vector<int> xs[400'002];

signed main()
{
    FASTIO;
    
    int n;
    cin >> n;
    Seg cnt;
    cnt.init(400'001);

    for(int i = 0; i<n; i++){
        int x, y;
        cin >> x >> y;
        xs[y+base].push_back(x+base);
    }

    ll ans = 0;
    for(int y = 400'001; y>=0; y--){
        for(int x: xs[y]){
            ll l = cnt.qry(1, x-1);
            ll r = cnt.qry(x+1, 400'001);
            ans = (ans+l*r%MOD)%MOD;
        }
        for(int x: xs[y]){
            cnt.upd(x, 1);
        }
    }

    cout << ans;
    
    return 0;
}

메모

세그먼트 트리의 배열을 1 인덱스로 만들어서 base를 200,001로 해야한다.