[백준] 교차개수세기(1615)

문제 링크 : [백준] 교차개수세기(1615)

문제 설명

이분 그래프가 존재 할 때, 한쪽 Set에서 다른 Set으로 선으로 그을 때, 교차하는 선분의 수를 구하세요.
교차의 조건은 둘 중 하나를 만족하면 됩니다.

1. A_i < A_j && B_i > B_j
2. A_i > A_j && B_i < B_j

입력

N(한 Set에서 노드의 갯수, 1 <= N <= 2,000)
M(선을 긋는 횟수, 1 <=M <= N*(N-1)/2)
A_i B_i(두 엣지를 잇는 선을 긋습니다.)

5 6
1 5
2 2
3 2
4 3
5 1
5 3

출력

8

카테고리

#정렬 #펜윅트리 #세그먼트트리

시간 복잡도 상한

O(MlogM)

해결 방법

1. 두 엣지들 사이의 값이 역전되는 갯수를 세면 됩니다.(1, 2 조건 중 하나만 만족하면 됩니다.)
2. 단 모든 엣지들간의 관계를 검사하려면 O(N²)이 되어 TLE가 됩니다.
3. 그렇다면 둘중에 한 지점을 정렬하여, 나머지 하나의 관계만 비교를 하도록 만듭니다.
   3-1. A_i로 정렬을 하고, 정렬된 순서로 순차로 처리하게 되면, A의 좌표간의 관계는 고려하지 않아도 됩니다.
4. A를 내림차순으로 정렬하였다면, B들간의 관계는 이미 나왔던 수 중, 자신보다 작은 숫자의 갯수를 세면 됩니다.
5. 4를 세기 위해서는 또 O(N²)이 발생합니다.
6. 이것은 세그먼트 트리나 펜윅트리를 사용하여 현재 값보다 작은 수의 부분합을 조회하고, 현재 값을 1 증가하도록 업데이트합니다.
7. 현재보다 작은 값을 조회하기 때문에, B_i이 1인 경우, 인덱스가 0을 조회하게 되어 펜윅트리를 사용 할 수 없어 값 보정하는 코드가 있습니다.

시간복잡도

O(MlogN)
정확하게는 정렬 때문에 MlogM + MlogN 정도가 될 것입니다.

코드

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long L;
typedef pair<int,int>P;
int n,m,i;
L s,t[2002];
P p[1999000];
void u(int v){
    while(v<=n)t[v]++,v+=v&-v;
}
L q(L v){
    L s=0;
    while(v)s+=t[v],v-=v&-v;
    return s;
}
int main(){
    scanf("%d%d",&n,&m);
    n++;
    for(i=0;i<m;i++)scanf("%d%d",&p[i].first,&p[i].second);
    sort(p,p+m);
    for(i=m-1;i>=0;i--){
        s+=q(p[i].second);
        u(p[i].second+1);
    }
    printf("%lld",s);
}