BOJ 14463 - 소가 길을 건너간 이유 9 (세그트리, 라인스위핑)

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

 

<문제설명>

distinct한 좌표를 갖는 교차하는 선분쌍의 '개수' nlogn에 구하기

 

 

<풀이>

참고: n^2에 모든 교차하는 선분쌍을 하나하나 들여다 보는 로직 https://suuntree.tistory.com/112

 

선분i를 처음부터 순차로 보면서, 선분 i의 범위가 [lo,hi]라면, hi를 세그먼트트리에서 1 올리는 update를 해준다.

 

그러면 0~i-1번 선분과 선분 i가 교차하는 쌍의 개수는 psum[i끝점] - psum[i시작점]이다.

 

다시말해서, 0~i-1번 선분 중에 선분 i[lo,hi]와 교차하는 선분의 개수는, 끝나는 점이 [lo,hi]에 속하는 선분의 개수이다.

(선분i에 포함되는 선분은 i+1이후이므로 신경쓰지 않는다.)

 

<코드>

const int MAX = 1e5 + 4;
const int SMAX = (1 << 20);
int seg[SMAX];

void update(int i) {
	i += (SMAX / 2);
	seg[i]++;	
	while (i > 1) {
		i /= 2;
		seg[i] = seg[i * 2] + seg[i * 2 + 1];
	}
}
int val(int s, int e, int node, int ns, int ne) {
	if (e < ns || ne < s) return 0;
	if (s <= ns && ne <= e) return seg[node];
	int mid = (ns + ne) / 2;
	return val(s, e, node * 2, ns, mid) + val(s, e, node * 2 + 1, mid + 1, ne);
}
int val(int s) { return val(0, s, 1, 0, SMAX / 2 - 1); }

P lr[MAX];
int main() {
	FAST;
	int n, ans=0; cin >> n;
	fill(lr, lr + MAX, make_pair(-1, -1));
	for (int i = 0,x; i < 2 * n; i++) {
		cin >> x;
		if (lr[x].first == -1) lr[x].first = i;
		else lr[x].second = i;
	}
	sort(lr+1, lr + n+1);
	for (int i = 1; i <= n; i++) {
		ans += val(lr[i].second) - val(lr[i].first);
		update(lr[i].second);
	}

	cout << ans << '\n';
}