[백준]대한민국(3770)

문제 링크 : [백준]대한민국(3770)

3770번: 대한민국

 

문제 설명

왼쪽 도시에서 오른쪽 도시로 연결하는 고속도로들 중 교차점의 갯수를 구하세요.

입력

T(테스트 케이스 수)

N(왼쪽 도시 갯수, 1 <= N <= 1,000)

M(오른쪽 도시 갯수, 1 <= M <= 1,000)

K(고속도로 갯수, 1 <= K <=400,000)

A_i B_i(고속도로 정보, 왼쪽 도로 중 A_i번째 도시와 B_i도시가 연결 됨)

1
3 4 4
1 4
2 3
3 2
3 1

 

출력

Test case 1: 5

 

카테고리

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

 

시간 복잡도 상한

O(KlogK)

 

해결 방법

1. 왼쪽 지점에서 오른쪽 지점으로 연결하는 선 중 교차하는 지점을 찾는 문제입니다.
2. 교차하는 지점은 왼쪽에서는 상대적으로 위쪽에 있었으나, 오른쪽에서 상대적으로 아래쪽에 있는 지점들의 갯수를 세면 됩니다.
   1. 왼쪽에서 맨 위에 있던 지점과 오른쪽에서 위에서 두번째 있는 지점과
   2. 왼쪽에서 위에서 두번째에 있는 지점과 오른쪽에서 맨 위에 있는 지점을 연결하는 선은 교차하게 됩니다.
3. 왼쪽 지점을 기준으로 선을 정렬합니다.
4. 정렬된 선들을 차례대로 방문하면서 현재 도로의 오른쪽 지점보다 아래에 있는 오른쪽 지점이 이전에 몇개나 나왔었는지를 셉니다.
5. 3번에서 왼쪽 지점을 기준으로 정렬했기 때문에, 4번에서 세는 지점의 갯수는 2번에서 설명한 지점의 갯수가 됩니다.
6. 누적합으로 갯수를 세면 되지만 값이 빈번히 변경되기 때문에 세그먼트 트리나 펜윅트리를 이용하여 문제를 풉니다.
7. 단, 왼쪽에서 같은 지점일 경우, 오른쪽을 내림차순으로 정렬하여야 중복 카운팅이 되지 않습니다.
8. 아래 코드는 반대로 정렬하였습니다.

시간복잡도

O(Klog(max(N,M)))

코드

#include<iostream>
#include<algorithm>
#include<string.h>
#define F first
#define S second
using namespace std;
typedef pair<int,int>P;
typedef long long L;
int t,c,n,m,k,i,e[1001];
L a;
P d[400001];
void u(int p){
    while(p<=n)e[p]++,p+=p&-p;
}
int q(int p){
    int s=0;
    while(p)s+=e[p],p-=p&-p;
    return s;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>t;
    for(c=1;c<=t;c++){
        memset(e,0,sizeof(e));
        cin>>n>>m>>k;
        for(i=0;i<k;i++)cin>>d[i].F>>d[i].S,d[i].F*=-1,d[i].S*=-1;
        sort(d,d+k);
        for(a=i=0;i<k;i++){
            a+=q(-d[i].S-1);
            u(-d[i].S);
        }
        cout<<"Test case "<<c<<": "<<a<<"\n";
    }
}