백준 13681 c++ "Bolhas e Baldes" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 세그먼트 트리 기본문제이다.  세그먼트 트리를 설계를 할줄 알면 손쉽게 해결할 수 있다.

N의 범위도 10^5이라 문제될거 없다.

 

[코드 해설]

 

• 세그먼트 트리 초기화
  vector<ll> tree를 사용하여 세그먼트 트리를 선언하고, 배열 크기의 4배로 초기화합니다. 세그먼트 트리는 구간 합을 관리하기 위해 사용됩니다.
• 업데이트 함수 (Update)
  Update 함수는 세그먼트 트리에 특정 인덱스의 값을 업데이트하는 역할을 합니다.
  • 기저 조건: 현재 노드가 업데이트하려는 인덱스에 도달하면 값을 더합니다.
  • 재귀 호출: 해당 인덱스가 포함된 구간을 찾아 좌측 자식 노드 또는 우측 자식 노드로 이동합니다.
  • 노드 값 갱신: 자식 노드들의 합으로 부모 노드의 값을 갱신합니다.
• 쿼리 함수 (Query)
  Query 함수는 주어진 구간 [left, right]의 합을 반환합니다.
  • 완전히 벗어난 경우: 구간이 일치하지 않으면 0을 반환합니다.
  • 완전히 포함된 경우: 현재 노드 값을 반환합니다.
  • 부분적으로 포함된 경우: 좌측과 우측 자식 노드를 각각 재귀 호출하여 합산합니다.
• 게임 로직 (Game_Start 함수)
  • 세그먼트 트리를 초기화합니다.
  • 입력으로 들어오는 숫자마다 다음을 수행합니다:
    • 현재 숫자보다 큰 숫자의 개수를 세그먼트 트리를 사용해 구간 합으로 계산합니다.
    • 해당 값을 count에 누적합니다.
    • 현재 숫자를 세그먼트 트리에 추가합니다.
  • count의 홀짝 여부에 따라 결과를 출력합니다:
    • 짝수라면 "Carlos"를 출력
    • 홀수라면 "Marcelo"를 출력
• 메인 함수
  • 무한 루프를 통해 게임을 반복적으로 실행합니다.
  • 입력된 N이 0일 경우 루프를 종료합니다.
  • 각 게임에서 Game_Start를 호출하여 게임 로직을 수행합니다.

 

[소스 코드]

나의 말:
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long 

using namespace std;

int N;

vector<ll> tree;

void Update(int node, int start, int end, int idx, int diff) {
	if (start == end) {
		tree[node] += diff;
		return;
	}
	if (idx < start || end < idx)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] = tree[node * 2] + tree[node * 2 + 1];
}
ll Query(int node, int start, int end, int left, int right) {
	if (end < left || right < start)return 0;

	if (left <= start && end <= right) {
		return tree[node];
	}

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

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

	ll count = 0;

	for (int i = 0; i < N; i++) {
		ll num;
		cin >> num;
		count +=Query(1, 1, N, num + 1, N);
		Update(1, 1, N, num, 1);
	}
	if (count % 2 == 0) {
		cout << "Carlos" << '\n';
	}
	else {
		cout << "Marcelo" << '\n';
	}
	
}

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


	while (1) {
		cin >> N;
		if (N == 0)break;
		Game_Start();
	}
}