백준 1615번 : 교차개수세기 (c++)

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

1615번: 교차개수세기

문제

각각 N(1 ≤ N ≤ 2,000)개의 쌍으로 이루어진 2N개의 정점과 M(1 ≤ M ≤ N*(N-1)/2)개의 에지로 구성된 이분그래프가 주어질 때 서로 교차하는 총 개수를 구하는 것이다.
  교차 조건 : 한 Independent Set A과 다른 Independent Set 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

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef long long ll;
int N, M;
vector <ll> nums;

struct IndexedTree {
	vector <ll> tree;
	vector <ll> num;
	int leafSize = 0, depth = 0;

	IndexedTree(vector <ll> num1) {
		num = num1;
		while (pow(2, depth) < num1.size()) {
			depth++;
		}
		leafSize = pow(2, depth);
		tree.resize(2 * leafSize);
	}

	void update(int node, int left, int right, int index, int diff) {
		if (index < left || right < index) {
			return;
		}
		else {
			tree[node] += diff;
			if (left != right) {
				ll mid = (left + right) / 2;
				update(node * 2, left, mid, index, diff);
				update(node * 2 + 1, mid + 1, right, index, diff);
			}
		}
	}

	ll query(int node, int left, int right, int qLeft, int qRight) {
		if (right < qLeft || qRight < left) {
			return 0;
		}
		else if (qLeft <= left && right <= qRight) {
			return tree[node];
		}
		else {
			ll mid = (left + right) / 2;
			return query(node * 2, left, mid, qLeft, qRight) + query(node * 2 + 1, mid + 1, right, qLeft, qRight);
		}
	}
};


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	nums.resize(N + 1);
	IndexedTree h(nums);
	vector <pair<int, int>> chk;
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		chk.push_back({ a,b });
	}
	sort(chk.begin(), chk.end());
	ll result = 0;
	for (int i = M-1; i >= 0; i--)
	{
		int b = chk[i].second;
		result+=h.query(1, 1, h.leafSize, 1, b-1);
		h.update(1, 1, h.leafSize, b, 1);
	}
	cout << result;
	return 0;
}