백준 17131 (C++) 여우가 정보섬에 올라온 이유

최초 업로드: 2025-04-21 00:25:11

최근 수정 시간: 2025-07-25 09:28:57

게시자: rlatjwls3333

카테고리: 백준

# [Platinum III] 여우가 정보섬에 올라온 이유

#### [문제 링크](https://www.acmicpc.net/problem/17131)

## 문제 설명

여우가 정보섬에 올라왔다!

오늘도 하늘에는 아름다운 별들이 빛나고 있다. 정보섬은 언덕 꼭대기에 위치해 있기 때문에 별이 잘 보이기로 유명하다. 그래서인지, 여우 한 마리가 정보섬에 올라와 밤하늘을 바라보며 별자리를 만들고 있다. 여우는 세 개의 별을 연결하여 V형 별자리를 만드는데, 그 이유는 V가 자신의 얼굴과 닮았기 때문이라나 뭐라나. 여우는 자신의 시점을 기준으로 생각하기 때문에, V가 회전한 모양(<, >, ㄴ, ㄱ, ^ 등)은 V라고 생각하지 않는다.

여우는 만들 수 있는 V형 별자리의 총 개수가 궁금해졌다. 그러나 일일이 세보기에는 별이 너무 많았기 때문에, 여우는 뛰어난 프로그래머인 당신에게 도움을 요청했다! 귀여운 여우를 위해 얼마나 많은 V형 별자리가 만들어질 수 있는지 계산해 주자.

V형 별자리를 명확하게 정의하면 다음과 같다. 세 별 (s,t,u)가 s.x < t.x < u.x이고 s.y > t.y < u.y이면 V형 별자리이다. 예를 들어 아래의 '정보섬의 밤하늘 참고도'에서 (a,b,c)는 V형 별자리를 이루지만 (d,b,c)는 d.x < b.x가 아니므로 V형 별자리가 아니다. V형 별자리의 개수를 셀 때, 한 별이 여러 별자리에 속할 수 있다.

답이 매우 커질 수 있으므로 (109+7)로 나눈 나머지를 출력한다.

## 입력

첫 줄에 별의 개수 N이 주어진다. 그 다음 줄부터 N개의 줄에 걸쳐 별의 좌표 x y가 주어진다.

## 출력

(만들 수 있는 V형 별자리의 개수) mod (109+7)을 출력한다.

## 풀이
#### 자신보다 y가 큰 좌표 중에 x가 작은 좌표의 개수 * x가 큰 좌표의 개수를 계산하는 문제이다. y가 큰 순을 기준으로 정렬하고, 세그먼트 트리로 0~cur.-1 * cur.x+1~MAX_X 를 하면 된다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const long long MOD = 1e9+7;
const int MAX = 400'000*3;
typedef pair<int, int> P;
long long _size=1, arr[MAX];

bool comp(P a, P b) {
    return a.second > b.second;
}

long long getCnt(int L, int R, int nodeNum, int nodeL, int nodeR) {
 if(R<nodeL || nodeR<L) return 0;
 if(L<=nodeL && nodeR<=R) return arr[nodeNum];
 int mid = (nodeL+nodeR)/2;
 return getCnt(L, R, nodeNum*2, nodeL, mid) + getCnt(L, R, nodeNum*2+1, mid+1, nodeR);
}

void update(int x) {
    int nodeNum = _size/2+x;
    arr[nodeNum]++;
    while(nodeNum>1) {
        nodeNum>>=1;
        arr[nodeNum] = arr[nodeNum*2] + arr[nodeNum*2+1];
    }
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n; cin >> n;
 vector v(n);
 for(int i=0;i<n;i++) {
 cin >> v[i].first >> v[i].second;
 v[i].first += 200'000;
 }
 sort(v.begin(), v.end(), comp);

while(_size<400'000) _size<<=1;
 _size<<=1;

vector tmp; // y가 같은 별들 임시로 모아둘 장소
 long long totalCnt=0;
 for(int i=0;i<n;i++) {
 while(!tmp.empty() && tmp.back().second>v[i].second) {
 update(tmp.back().first);
 tmp.pop_back();
 }
 totalCnt += getCnt(0, v[i].first-1, 1, 0, _size/2-1) * getCnt(v[i].first+1, 400'000, 1, 0, _size/2-1);
 totalCnt %= MOD;
 tmp.push_back(v[i]);
 }
 cout << totalCnt;
}
```