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

문제 링크

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

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

 

만들어질 수 있는 V형 별자리의 총개수를 구해야 하는 문제입니다.

우선 한 점을 기준으로, (왼쪽 위에 있는 모든 점의 개수)*(오른쪽 위에 있는 모든 점의 개수) 만큼의 V형 별자리를 만들 수 있습니다. 물론 $N \leq 200,000$이므로 한 점마다 매번 반복해서 점의 개수를 구하는 건 불가능합니다.

결론부터 말하면 구간 트리(세그먼트 트리, 펜윅 트리)를 이용해 풀 수 있습니다. 저는 펜윅 트리를 이용했습니다.
트리의 구간은 x축(수학에서의 x축)의 범위를 나타냅니다.
각 구간에 대한 쿼리로 해당 x축 구간에 점이 몇 개 있는지를 반환합니다.

특정 별의 위쪽에 있는 별들의 개수를 구해야 하니 y축에 대해서도 관리해야 할 것 같지만 그러지 않아도 가능합니다.
모든 별을 구간 트리에 업데이트해둔 뒤, y축 좌표가 가장 낮은 별부터 높은 별의 순서로 처리하면 됩니다.

우선 처음엔 구간 트리에서 관리하는 별들이 지금 처리해야 할 별보다 위쪽에 있다는 것이 자명합니다.
물론 지금 보는 별과 같은 y축 좌표를 가지는 별이 있다면 그 별들은 구간 트리에서 미리 빼둬야 합니다. 현재 처리 중인 별도 포함해서요.

이렇게 한 y축마다 그 좌표에 있는 별들을 구간 트리에서 제거하고, 해당 별들에 대해 각각 V형 별자리의 개수를 구하면서 쭉쭉 올라가면 구간 트리는 항상 현재 처리 중인 별보다 위에 있는 별들만 관리할 수 있게 됩니다.

 

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define fst first
#define snd second
using ll = long long;
const ll MOD = 1e9 + 7;
const int addCor = 200001;
const int corMax = 200000 + addCor;
 
int n;
ll tree[500000];
pair<int, int> p[300000];
ll ans;
ll query(int i) {
    ll val = 0;
    while (i > 0) {
        val += tree[i];
        i -= (i&-i);
    }
    return val;
}
void update(int i, ll diff) {
    while (i <= corMax) {
        tree[i] += diff;
        i += (i&-i);
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i].snd >> p[i].fst;
        update(p[i].snd + addCor, 1);
    }
    sort(p, p + n, [&](auto &a, auto &b) {
        return (a.fst == b.fst) ? a.snd < b.snd : a.fst < b.fst;
    });
    
    int l = 0x3f3f3f3f;
    for (int i = 0; i < n;i++) {
        if (l != p[i].fst) {
            l = p[i].fst;
            for (int j = i; p[j].fst == l; j++) {
                update(p[j].snd + addCor, -1);
            }
        }
        int x = p[i].snd + addCor;
        ll left = query(x - 1) % MOD;
        ll right = (query(corMax) - query(x)) % MOD;
        ans += (left*right) % MOD;
        ans %= MOD;
    }
    cout << ans;
}