백준 9463 c++ "순열 그래프" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 교차점 구하는 문제를 응용한거라 본다.

교차점의 핵심은 시작위치에서 끝위치의 인덱스를 기준으로 +1을하여 

Query를 작성한다.

idx+1 보다 큰 값들의 갯수가 증가되어 있지 않다면 교차점이 없는거다.

그 후 Update를 이용하여 해당 idx에 +1을 하여 내가 여기 왔습니다 와 같은 영역 표시를 해준다.

위와 같은 과정을 반복하면 교차점들을 구할 수 있다.

[코드 해설]

 

• InitArrAndTree 함수: 배열 및 세그먼트 트리 초기화
  • 배열 arr와 세그먼트 트리 tree를 초기화한다.
  • 입력된 숫자를 읽어 배열 arr에 저장하고, 두 번째 입력으로 각 숫자의 순서를 map 자료구조 myMap에 저장한다.
    • 이때, 숫자 num의 위치를 myMap[num] = i로 기록하여 나중에 참조할 수 있도록 한다.
• Query 함수: 구간 합 계산
  • 세그먼트 트리에서 특정 구간 [left, right]의 합을 계산한다.
  • 현재 노드의 구간 [start, end]가 완전히 포함되면 해당 노드 값을 ans에 더한다.
  • 구간이 겹치는 경우, 왼쪽 자식 노드와 오른쪽 자식 노드를 재귀적으로 호출하여 합을 계산한다.
• Update 함수: 값 갱신
  • 배열의 특정 인덱스 idx에 값을 추가하거나 변경한다.
  • 세그먼트 트리에서 해당 위치를 찾아 값의 변화량 diff를 반영하며, 이를 부모 노드로 전달하여 구간 합을 업데이트한다.
• Game_Start 함수: 주요 로직 실행
  • 입력된 테스트 케이스 수 T에 대해 반복 실행한다.
    • 각 테스트 케이스에서 배열 및 세그먼트 트리를 초기화한다.
    • 배열 arr의 각 원소를 처리하며, 다음을 수행한다:
      1. 현재 숫자 num의 순서 idx를 myMap을 통해 찾는다.
      2. Query 함수를 호출하여 인덱스 [idx + 1, N] 구간에서 현재까지 처리된 숫자들의 합을 계산한다.
      3. Update 함수를 호출하여 인덱스 idx에 값을 추가(1 증가)하여 숫자를 처리했음을 기록한다.
    • 최종적으로 계산된 결과 ans를 출력한다.
• main 함수: 프로그램 실행
  • Game_Start 함수를 호출하여 입력을 처리하고 테스트 케이스를 실행한다.
  • ios::sync_with_stdio(false)와 cin.tie(0)을 사용하여 입출력 속도를 최적화한다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <map>
#define MAX N

using namespace std;

int T;
vector<long> tree;
vector<int> arr;
map<int, int> myMap;
long ans = 0;

int N;

void InitArrAndTree() {
	tree.clear();
	arr.clear();
	tree.resize(N * 4);
	arr.resize(N + 1);

	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
		
		
	}
	for (int i = 1; i <= N; i++) {
		int num;
		cin >> num;


		myMap[num] = i;
	}
}

void Query(int node, int start, int end, int left, int right) {
	if (left <= start && end <= right) {
		ans += tree[node];
		return;
	}
	if (end < left || right < start)return;
	int mid = (start + end) / 2;
	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 (start == end) {
		tree[node] += diff;
		return;
	}

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


void Game_Start() {
	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> N;
		InitArrAndTree();
		ans = 0;
		for (int k = 1; k <= N; k++) {
			int num = arr[k];
			int idx = myMap[num];

			Query(1, 1, MAX, idx + 1, N);
			Update(1, 1, MAX, idx, 1);
		}
		cout << ans << '\n';
	}
}

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

	Game_Start();
}