백준 2517 c++ "달리기" -PlusUltraCode-

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

[필자 사고]

평범한 inversing index인줄 알았지만... 입력될 수 있는 범위가 겁나 크다.

즉 새롭게 알게된 알고리즘 좌표 압축을 통해 내가 가지고 있는 배열에는 값이 아닌 index를 저장해놓는 방식이다.

 

필자는 myMap을 통해 위와 같은 문제를 해결했고 다른 분들의 코드를 살펴보니

기존 배열을 다른 배열로 temp 를 담고 정렬뒤 해당 값을 찾으면 index를 arr원본 배열에 저장하는 식으로 

좌표 압축을 하였다.

 

새로운 알고리즘 학습하기에는 좋은 문제다.

[코드 해설]

 

• 입력 처리 및 초기화 (Input 함수)
  Input 함수는 데이터를 입력받아 초기화하는 역할을 한다.
  • 배열 arr에 입력된 데이터를 저장한다.
  • 입력 데이터를 정렬한 후, 원래 값에 대한 순위를 매핑하여 myMap에 저장한다.
  • 이 매핑은 값의 상대적인 순서를 정렬 기반으로 관리하기 위함이다.
• 구간 합 쿼리 (Query 함수)
  Query 함수는 세그먼트 트리를 이용해 특정 범위의 합을 구한다.
  • 현재 노드가 요청 범위 안에 완전히 포함될 경우, 해당 노드 값을 반환한다.
  • 요청 범위와 겹치지 않는 경우, 0을 반환한다.
  • 겹치는 경우, 현재 범위를 두 부분으로 나눠 각각 재귀적으로 호출하여 결과를 합산한다.
• 세그먼트 트리 업데이트 (Update 함수)
  Update 함수는 세그먼트 트리에 특정 값의 변경을 반영한다.
  • 업데이트 대상 인덱스가 현재 범위에 포함되지 않으면 함수가 종료된다.
  • 리프 노드에 도달하면 값을 변경하고 반환한다.
  • 범위가 더 클 경우, 현재 범위를 두 부분으로 나눠 재귀적으로 호출하여 값을 갱신한다.
• 게임 시작 (Game_Start 함수)
  Game_Start 함수는 문제를 해결하기 위한 주된 로직을 포함한다.
  • 입력 데이터의 각 값에 대해, 해당 값보다 큰 값의 개수를 세그먼트 트리를 이용해 계산한다.
    • Query 함수로 현재 값의 순위 이후의 구간 합을 계산한다.
  • 계산된 결과를 출력한 후, 해당 값을 세그먼트 트리에 추가하여 업데이트한다.
    • Update 함수로 현재 값의 순위를 갱신한다.
  • 위 과정을 모든 입력 데이터에 대해 반복한다.
• 메인 함수
  main 함수는 프로그램 실행의 시작점으로, Input 함수로 데이터를 초기화한 뒤, Game_Start 함수로 문제를 해결한다.
  • ios::sync_with_stdio(false)와 cin.tie(0)를 통해 입출력 속도를 최적화한다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define MAX 1000000
using namespace std;

vector<long> tree;
vector<long> arr;

int N;
long ans = 0;
map<long, long> myMap;
void Input() {
	cin >> N;
	arr.resize(N + 1);
	tree.resize(MAX * 4);
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
		
	}
	vector<long> temp = arr;
	sort(temp.begin() + 1, temp.end());

	for (int i = 1; i <= N; i++) {
		myMap[temp[i]] = i;
	}
}

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] += diff;
}

void Game_Start() {

	for (int i = 1; i <= N; i++) {
		long num = arr[i];
		ans = 0;
		int idx = myMap[num];
		cout << Query(1, 1, MAX, idx + 1, MAX)+1 << '\n';
	
		Update(1, 1, MAX, idx, 1);
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	Input();
	Game_Start();
}