백준 27897 c++ "특별한 화재 경보" -PlusUltraCode-

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

 

[필자 사고] 

세그먼트 트리의 inverstion Counting 문제이다.

주어지는 값은 N보다 작은 값들이 주어지기 때문에 좌표압축은 안해도 된다.

마지막 조심해야 될 점은 N(N-1)/2 와 count+L 중 더 작은값을 골라야 된다.

전자는 전체 경우의 수이고 후자는 우리가 구한 수이다.

 

이 부분만 조심하면 잘 해결할 수 있다.

[코드 해설]

 

아래는 주어진 코드에 대한 설명입니다:

 

세그먼트 트리 초기화
vector<ll> tree를 사용하여 세그먼트 트리를 선언하고, 배열 크기의 4배로 초기화합니다. 세그먼트 트리는 구간 합을 효율적으로 계산하기 위해 사용됩니다.

 

업데이트 함수 (Update)
Update 함수는 세그먼트 트리에 특정 인덱스의 값을 업데이트합니다.

• 기저 조건: 현재 노드가 업데이트하려는 인덱스와 일치하는 경우, 해당 노드 값을 증가시킵니다.
• 재귀 호출: 인덱스가 포함된 구간에 따라 좌측 또는 우측 자식 노드로 이동합니다.
• 노드 값 갱신: 자식 노드들의 합을 통해 부모 노드 값을 갱신합니다.

쿼리 함수 (Query)
Query 함수는 주어진 구간 [left, right]의 합을 반환합니다.

• 구간 밖인 경우: 해당 구간이 탐색 범위를 벗어나면 0을 반환합니다.
• 구간 포함인 경우: 탐색 범위가 완전히 포함되면 현재 노드 값을 반환합니다.
• 부분 포함인 경우: 좌측 및 우측 자식 노드를 각각 재귀 호출하여 구간 합을 계산합니다.

게임 로직 (Game_Start 함수)

• 입력 처리: 숫자의 개수 N과 추가적인 값 L을 입력받습니다.
• 세그먼트 트리 초기화: 크기를 N * 4로 설정하여 초기화합니다.
• 역순 카운팅 계산:
  • 각 입력 값 num에 대해:
    1. Query 함수를 사용해 현재 숫자보다 큰 숫자의 개수를 구합니다.
    2. 해당 값을 count에 누적합니다.
    3. 현재 숫자를 세그먼트 트리에 추가하여 다음 입력에 반영합니다.
• 최종 출력:
  • count(역순 카운팅의 합)와 최대 가능한 역순 카운팅 합 (N * (N-1) / 2)에 L을 더한 값 중 작은 값을 출력합니다.
  • 이는 L 만큼 추가적인 조작이 가능하다고 가정했을 때 가능한 최대 역순 카운팅 수를 의미합니다.

메인 함수

• ios::sync_with_stdio(false)와 cin.tie(0)를 통해 입출력 속도를 최적화합니다.
• Game_Start를 호출하여 게임 로직을 실행합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long 

using namespace std;

int N;
ll L;
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() {
	cin >> N >> L;
	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);
	}

	cout << min((ll)N * (N - 1) / 2, count + L);
}

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