백준 5419 북서풍

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

북서풍 즉 X, Y  좌표를 기준으로 x 로 sorting 했을때 기존 Y 값보다 크거나 같은 모든 값을 카운팅 하면 

결국 북서풍으로 항해 살수 있는 섬을 구하는 갯수가 된다.

#include <stdio.h>
#include <iostream>
#include <memory.h>
using namespace std;
 
typedef long long ll;
int N, M, K;
int TN = 1;
 
struct SegTree {
 
    int x;
    int y;
 
    SegTree &operator = (const SegTree &org){
 
        x = org.x;
        y = org.y;
 
        return *this;
    }
 
    /*
    bool operator <(const SegTree &other) const{

        if (x == other.x)
            return y > other.y;

        return x < other.x;
    }
    */
};
 
struct SegTree temp[75001];
struct SegTree aa[75001];
 
int tree[400005];
 
//query l, query r, idx, l, r//
int query(int ql, int qr, int idx, int l, int r){
 
    if (ql <= l && r <= qr) return tree[idx];
    if (r < ql || qr < l) return 0;
 
 
    int lnode = query(ql, qr, idx * 2, l, (l + r) / 2);
    int rnode = query(ql, qr, idx * 2 + 1, (l + r) / 2 + 1, r);
 
    return lnode + rnode;
}
 
//val 추가 
void update(int idx, int val){
 
    int Nidx = TN + idx - 1;
    tree[Nidx] = val;
    Nidx >>= 1;
 
    while (Nidx > 0){
 
        tree[Nidx] = tree[Nidx * 2] + tree[Nidx * 2 + 1];
        Nidx >>= 1;
    }
}
 
 
 
void MergeSortX(int l, int r, struct SegTree arr[]){
 
    int half = (l + r) / 2;
    int li = l;
    int ri = half + 1;
 
    int idx = l;
 
    if (l == r)return;
 
    MergeSortX(l, half, arr);
    MergeSortX(half + 1, r, arr);
 
    while (li <= half && ri <= r){
 
        if (arr[li].x < arr[ri].x){
            temp[idx++] = arr[li++];
        }
        else if (arr[li].x == arr[ri].x){
            
            //x 좌표 값이 같을 경우에는 y 를 좀더 큰값으로 가져가보자 
            //뒤에 카운트를 해보기 위해서 .
 
            if (arr[li].y > arr[li].y)
                temp[idx++] = arr[li++];
            else 
                temp[idx++] = arr[ri++];
 
        }
        else{
            temp[idx++] = arr[ri++];
        }
 
    }
    while (li <= half) temp[idx++] = arr[li++];
    while (ri <= r) temp[idx++] = arr[ri++];
 
    for (int i = l; i <= r; i++){
        arr[i] = temp[i];
    }
}
 
 
 
void MergeSortY(int l, int r, struct SegTree arr[]){
 
    int half = (l + r) / 2;
    int li = l;
    int ri = half + 1;
 
    int idx = l;
 
    if (l == r)return;
 
    MergeSortY(l, half, arr);
    MergeSortY(half + 1, r, arr);
 
    while (li <= half && ri <= r){
 
        if (arr[li].y < arr[ri].y){
            temp[idx++] = arr[li++];
        }
#if 1
        else if (arr[li].y == arr[ri].y){
 
            if (arr[li].x < arr[ri].x)  {
                temp[idx++] = arr[li++];
            }
            else{
                temp[idx++] = arr[ri++];
            }
        }
#endif 
        else  {
            temp[idx++] = arr[ri++];
        }
 
    }
    while (li <= half) 
        temp[idx++] = arr[li++];
    while (ri <= r) 
        temp[idx++] = arr[ri++];
 
    for (int i = l; i <= r; i++){
        arr[i] = temp[i];
    }
}
 
 
int tempBuf[75001];
 
void MergeSortInt(int l, int r, int arr[]){
 
    if (l == r)return;
 
    int half = (l + r) / 2;
    int li = l;
    int ri = half + 1;
 
    int idx = l;
 
 
    MergeSortInt(l, half, arr);
    MergeSortInt(half + 1, r, arr);
 
    while (li <= half && ri <= r){
 
        if (arr[li] < arr[ri])
            tempBuf[idx++] = arr[li++];
        else
            tempBuf[idx++] = arr[ri++];
 
    }
    while (li <= half) tempBuf[idx++] = arr[li++];
    while (ri <= r) tempBuf[idx++] = arr[ri++];
 
    for (int i = l; i <= r; i++){
        arr[i] = tempBuf[i];
    }
}
 
int main()
{
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("input.txt", "r", stdin); setbuf(stdout, NULL);
 
 
    int TC;
    cin >> TC;
 
    int yPos[75005];
    int b[75005];
 
    int YY[75005];
    int diff = 0;
 
    while (TC--){
 
        cin >> N;
 
        memset(tree, 0, sizeof(tree));
        memset(yPos, 0, sizeof(yPos));
        memset(YY, 0, sizeof(YY));
        memset(b, 0, sizeof(b));
 
        TN = 1;
        while (TN < N){
            TN <<= 1;
        }
 
        int x, y;
 
 
        for (int i = 1; i <= N; i++){
 
            cin >> aa[i].x >> aa[i].y;
            yPos[i] = aa[i].y;
        }
 
        // x값 기준 sorting 
        MergeSortY(1, N, aa);
 
 
        //y 좌표로만   기준 sorting
        MergeSortInt(1, N, yPos);
 
        diff = 1;
        YY[1] = 1;
 
 
        for (int i = 2; i <= N; i++){
 
            if (yPos[i] != yPos[i - 1])
                diff++;
 
            YY[i] = diff;
        }
 
        for (int i = 1; i <= N; i++){
            aa[i].y = YY[i];
        }
 
 
        MergeSortX(1, N, aa);
 
        /*
        segment tree 로 count 를 하게 한다..//
        0 0 0 0 
        1 0 0 0
        0 1 0 0
        0 0 1 0
        0 0 0 1 
        */
 
 
        ll ans = 0;
        int startY;
        
        for (int i = 1; i <= N; i++){
 
            startY = aa[i].y;
            //cout << "startY ==> [ " << startY << " ]" << endl;
 
            //int ret = query(startY, TN, 1, 1, TN);
            ans += (long long)query(startY, TN, 1, 1, TN);
 
            
            //ans += (long  long)ret;
            b[startY]++; // Y 축에 있는 값 증가 시키고 
 
            //cout << "Answer ==> [ " << ans << " ]" << endl;
            update(startY, b[startY]);
        }
 
        cout << ans << "\n";
 
    }
 
    return 0;
}