[BOJ1615] 교차개수세기(c++)

https://www.acmicpc.net/problem/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를 만족하면 두 간선이 교차한다고 정의합니다.

• (1 ≤ N ≤ 2,000)
• (1 ≤ M ≤ N×(N-1)/2)

---

문제 풀이

이 문제는 세그먼트 트리와 정렬을 활용하여 해결할 수 있습니다.

핵심 아이디어

1. 정렬: 왼쪽 정점을 기준으로 간선들을 오름차순 정렬합니다.
2. 세그먼트 트리: 각 간선을 순회하면서, 현재 간선의 오른쪽 정점보다 큰 위치에 있는 간선들의 개수를 세그먼트 트리로 쿼리합니다.
3. 교차 판정: 왼쪽은 작고(정렬로 보장) 오른쪽은 큰 간선들이 교차하는 간선이 됩니다.

알고리즘 과정

간선들을 왼쪽 정점 기준으로 정렬한 후, 순서대로 처리하면서:

• 현재 간선의 오른쪽 정점을 v[i].second라고 할 때
• v[i].second + 1부터 n까지의 구간에서 이미 등록된 간선의 개수를 세그먼트 트리로 쿼리
• 이 개수가 현재 간선과 교차하는 간선의 개수입니다
• 쿼리 후 현재 간선의 오른쪽 정점 위치에 카운트를 업데이트

예를 들어, 간선 (1, 5)를 먼저 처리하고 (3, 2)를 처리할 때:

• (3, 2)의 오른쪽 정점 2보다 큰 위치(3~5)에 있는 간선을 쿼리하면 (1, 5)가 카운트됩니다
• 왼쪽은 1 < 3이고, 오른쪽은 5 > 2이므로 교차 조건을 만족합니다

---

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
long long res;
vector<pair<int, int>> v;

int seg[2001 * 4];

int update(int x, int s, int e, int idx) {
	if (idx < s || e < idx) return seg[x];
	if (s == e) return seg[x] += 1;
	int mid = s + (e - s) / 2;
	return seg[x] = update(x * 2, s, mid, idx) + update(x * 2 + 1, mid + 1, e, idx);
}

long long query(int x, int s, int e, int l, int r) {
	if (r < s || e < l) return 0;
	if (l <= s && e <= r) return seg[x];
	int mid = s + (e - s) / 2;
	return query(x * 2, s, mid, l, r) + query(x * 2 + 1, mid + 1, e, l, r);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	int x, y;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		v.push_back({ x, y });
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < m; i++) {
		res += query(1, 1, n, v[i].second + 1, n);
		update(1, 1, n, v[i].second);
	}
	cout << res << '\n';
	return 0;
}

시간 복잡도

• 정렬: O(M log M)
• 각 간선마다 세그먼트 트리 쿼리 및 업데이트: O(M log N)
• 전체 시간 복잡도: O(M log N)

이 알고리즘은 N이 2,000, M이 최대 약 2,000,000인 경우에도 충분히 동작합니다.