백준[17131] 여우가 정보섬에 올라온 이유

문제 설명

문제 링크

http://icpc.me/17131

17131번: 여우가 정보섬에 올라온 이유

풀이

스위핑과 세그먼트 트리를 이용하여 풀이할 수 있다.

v를 만들기 위해서는 제일 아래 점 하나를 기준으로 (왼쪽 위의 점 개수) * (오른쪽 위의 점 개수)로 구할 수 있다.

모든 점에 대해 위의 값을 구하기 위해서는 y좌표 기준으로 오름차순으로 정렬한 후 가장 아래 있는 점부터 확인을 하며 업데이트를 해줘야 한다.

가장 아래 있는 점을 고르면 그것보다 x좌표가 작으면 항상 왼쪽 위에 존재하는 점이고, x가 크면 오른쪽 위에 존재하는 점이다.

하지만 이 성질이 항상 만족하려면 y좌표가 같은 점들은 배제를 시켜줘야 한다.

x좌표가 기준점보다 더 크고 작은 점의 개수는 세그먼트 트리를 이용하여 빠르게 구할 수 있다.

코드

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll MAX = 2e5 + 5;

struct SegTree {
    SegTree() { memset(tree, 0, sizeof tree); }
    ll tree[800005];

    ll query(ll node, ll s, ll e, ll qs, ll qe) {
        if (qe < s || e < qs) return 0;
        if (qs <= s && e <= qe) return tree[node];
        ll mid = (s + e) >> 1;
        return query(2 * node, s, mid, qs, qe) + query(2 * node + 1, mid + 1, e, qs, qe);
    }

    void update(ll node, ll s, ll e, ll idx, ll diff) {
        if (idx < s || idx > e) return;
        tree[node] += diff;
        if (s == e) return;
        ll mid = (s + e) >> 1; 
        update(2 * node, s, mid, idx, diff);
        update(2 * node + 1, mid + 1, e, idx, diff);
    }
};

pll arr[MAX];
ll tmp[MAX];

int main() {
    ll n; scanf("%lld", &n);
    for (ll i = 0; i < n; i++) {
        scanf("%lld %lld", &arr[i].first, &arr[i].second);
    }
	
    //좌표압축
    sort(arr, arr + n);    
    tmp[0] = 0;
    for (ll i = 1; i < n; i++) {
        if (arr[i - 1].first == arr[i].first) tmp[i] = tmp[i - 1];
        else tmp[i] = tmp[i - 1] + 1;
    }
    for (ll i = 0; i < n; i++) arr[i].first = tmp[i];

    SegTree seg = SegTree();
    
    for (ll i = 0; i < n; i++) {
        seg.update(1, 0, MAX, arr[i].first, 1);
    }

    sort(arr, arr + n, [](pll &a, pll &b) {
        return a.second == b.second ? a.first < b.first : a.second < b.second;
    });

    ll res = 0;
    ll cur = -2e9;
    for (ll i = 0; i < n; i++) {
    	// y좌표가 같은 것들 한번에 업데이트
        if (cur != arr[i].second) {
            cur = arr[i].second;
            for (ll j = i; cur == arr[j].second && j < n; j++) {
                seg.update(1, 0, MAX, arr[j].first, -1);
            }
        }
        ll l = seg.query(1, 0, MAX, 0, arr[i].first - 1) % MOD;
        ll r = seg.query(1, 0, MAX, arr[i].first + 1, MAX) % MOD;
        res += (l * r) % MOD;
    }
    printf("%lld", res % MOD);
}