백준 1615 c++ "교차개수세기" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 세그먼트 트리의 indexing inversion 의 초기 개념이다.

처음 반복문은 오름차순으로 정렬순서로 준비하고

작은 index 부터 조사를 시작해야한다.

먼저 1에는 5라는값이 들어가 있기때문에

5라는보다 하나 큰 6이라는 위치에 Query를 던진다.

6~N 값에 값이 있따면 sum 을 반환할것이다.

 

그리고 여기서 중요한건 시작점이 여러개 소환될수 있ㄷ는 것이다.

즉 시작점에서는 절대로 겹치지 않아 update문은 Query for 문이 끝난 이후

다시 for문을 만들어 Update해야 된다. 이 부분이 실수하기 좋은 부분이다.

[코드 해설]

 

• 입력 처리 (Input 함수)
  • N과 M을 입력받습니다. N은 노드 수, M은 간선 수입니다.
  • 2차원 벡터 arr는 그래프를 표현하며, 각 노드에서 도달할 수 있는 다음 노드들의 리스트를 저장합니다.
  • M개의 간선을 입력받아 그래프를 구성합니다.
• 쿼리 함수 (Query 함수)
  • 세그먼트 트리에서 특정 구간 [left, right]의 합을 구합니다.
  • 재귀적으로 현재 노드가 구간에 완전히 포함되는 경우 값을 반환하고, 포함되지 않는 경우 0을 반환합니다.
  • 구간이 일부만 겹칠 경우, 좌측 및 우측 자식 노드를 재귀적으로 탐색하며 값을 합산합니다.
• 업데이트 함수 (Update 함수)
  • 특정 인덱스 idx의 값을 diff만큼 증가시키며 세그먼트 트리를 갱신합니다.
  • 구간을 반으로 나누어 해당 인덱스가 포함된 구간만을 재귀적으로 갱신합니다.
  • 리프 노드에서 시작하여 부모 노드로 거슬러 올라가며 값들을 갱신합니다.
• 게임 시작 함수 (Game_Start 함수)
  • 세그먼트 트리를 초기화합니다.
  • resultCount 변수를 통해 조건을 만족하는 쌍의 수를 계산합니다.
  • 각 노드 i에 대해:
    • 연결된 노드들 idx를 대상으로 Query를 호출하여 idx+1부터 N까지의 구간에서 값의 합을 구합니다. 이는 현재 노드에서 연결된 노드들 간의 특정 조건을 계산하는 데 사용됩니다.
    • 계산 후, 연결된 노드들 idx에 대해 Update를 호출하여 해당 인덱스를 세그먼트 트리에 갱신합니다.
  • 최종적으로 결과를 출력합니다.
• 메인 함수
  • Input 함수를 호출하여 입력을 처리합니다.
  • Game_Start 함수를 호출하여 계산을 수행하고 결과를 출력합니다.

 

[소스 코드]

	#include <iostream>
	#include <vector>

	using namespace std;
	vector<long>tree;
	vector<vector<int>> arr;
	int N, M;

	void Input() {
		cin >> N >> M;
		arr.resize(N+1);
	

		for (int i = 0; i < M; i++) {
			int start, end;
			cin >> start >> end;
			arr[start].push_back(end);
		}
	}

	long Query(int node, int start, int end, int left, int right) {
		if (left <= start && end <= right) {
			return tree[node];
		}
		if (end < left || right < start)return 0;

		int mid = (start + end) / 2;
		return Query(node*2, start, mid, left, right)
			+ Query(node*2+1, mid + 1, end, left, right);
	}

	void Update(int node, int start, int end, int idx, int diff) {
		if (idx<start || idx>end)return;
	
		if (start == end) {
			tree[node] += diff;
			return;
		}

		int mid = (start + end) / 2;
		if (mid >= idx) {
			Update(node*2, start, mid, idx, diff);
		}
		else {
			Update(node*2+1, mid + 1, end, idx, diff);
		}
	

		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}

	void Game_Start() {
	
		tree.resize(4 * N + 1);

		long resultCount = 0;
		for (int i = 1; i <= N; i++) {
			for (int k = 0; k < arr[i].size(); k++) {
				int idx = arr[i][k];
				resultCount += Query(1, 1, N, idx + 1, N);
			}

			for (int k = 0; k < arr[i].size(); k++) {
				int idx = arr[i][k];
				Update(1, 1, N, idx, 1);
			}
		}
		cout << resultCount;
	}

	int main(void) {
		ios::sync_with_stdio(false);
		cin.tie(0);
		cout.tie(0);
		Input();
		Game_Start();
	}