[BOJ/Platinum 5] 백준 1615 교차개수세기(C++)

문제 링크

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

1615번: 교차개수세기

 

문제

각각 N(1 ≤ N ≤ 2,000)개의 쌍으로 이루어진 2N개의 정점과 M(1 ≤ M ≤ N×(N-1)/2)개의 간선으로 구성된 이분그래프가 주어질 때 서로 교차하는 총 개수를 구하는 것이다.

• 교차 조건 : 한 독립 집합 A와 다른 독립 집합 B가 연결된 두 개의 간선을 (A1, B1), (A2, B2)라 한다면 A1 < A2, B1 > B2 또는 A1 > A2, B1 < B2를 만족한다면 두 간선을 교차한다고 한다.

예를 들어 위에 예에서 (3, 2)는 (1, 5)와 (5, 1)과 교차한다. 이 문제를 해결하는 프로그램을 작성하시오.

입력

첫 줄에 N과 간선의 개수 M이 주어진다. 그 다음 줄부터 M+1번째 줄까지 두 개의 수(i, j)가 주어지는데 이는 왼쪽 그룹의 i번 정점과 오른쪽 그룹의 j번 정점을 연결하는 간선이 있다는 의미이다. 중복되는 간선이 입력으로 주어지지 않는다.

출력

입력에서 주어진 간선이 교차하는 총 개수를 출력한다.

예제 입력 1

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

예제 출력 1

8

알고리즘 분류

• 자료 구조

풀이

간선의 두 점 중 A를 Index, B를 Value라고 한다면 Inversion Counting에 해당된다는 것을 알 수 있다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 2001
#define LL long long
#define INF 1e9

using namespace std;
int N, M;
vector<int> Vec[MAX];
vector<int> SegTree;
LL answer = 0;

void Input() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int I, J;
		cin >> I >> J;
		Vec[I].push_back(J);
	}
}

void Update_Tree(int Node, int Start, int End, int Val) {
	if (Start == End) {
		SegTree[Node] += 1;
		return;
	}
	int Mid = (Start + End) / 2;
	if (Val <= Mid) {
		Update_Tree(Node * 2, Start, Mid, Val);
	}
	else {
		Update_Tree(Node * 2 + 1, Mid + 1, End, Val);
	}
	SegTree[Node] = SegTree[Node * 2] + SegTree[Node * 2 + 1];
}

LL Query(int Node, int Start, int End, int Left, int Right) {
	if ((End < Left) || (Right < Start)) {
		return 0;
	}
	if ((Left <= Start) && (End <= Right)) {
		return SegTree[Node];
	}
	int Mid = (Start + End) / 2;
	return Query(Node * 2, Start, Mid, Left, Right) + Query(Node * 2 + 1, Mid + 1, End, Left, Right);
}

void Settings() {
	int Height = (int)ceil(log2(N));
	int Size = (1 << (Height + 1));
	SegTree.resize(Size);
}

void Find_Answer() {
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < Vec[i].size(); j++) {
			int X = Vec[i][j];
			answer += Query(1, 1, N, X + 1, N);
		}
		for (int j = 0; j < Vec[i].size(); j++) {
			int X = Vec[i][j];
			Update_Tree(1, 1, N, X);
		}
	}
	cout << answer << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}