백준 4442 c++ "빌보의 생일" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 inverstion Counting 활용 문제이다.

먼저 문제에서 주어지는 입력값들은 문자로 되어있어서 필자는

map자료구조를 이용하여 해당 값들을 좌표압축을 통해 세그먼트 트리를 손쉽게 작성했다.

그 이후 inverstion 알고리즘을 적용하여 원하는 값들을 출력했다.

[코드 해설]

1. 입력 처리 (Input 함수)

• 목적: 두 개의 문자열 배열을 입력받아 매핑 정보를 생성합니다.

1. 첫 번째 입력:
   • NNN: 배열의 크기.
   • arrarrarr: 첫 번째 문자열 배열로, 순서를 유지한 채 저장합니다.
2. 두 번째 입력:
   • myMapmyMapmyMap: 두 번째 문자열 배열로, 문자열을 정렬된 순서대로 인덱스를 매핑합니다.
     • 예: myMap["apple"]=1\text{myMap["apple"]} = 1myMap["apple"]=1, myMap["banana"]=2\text{myMap["banana"]} = 2myMap["banana"]=2.
3. 이를 통해, 문자열이 두 배열 간에 어떻게 정렬되었는지 확인할 수 있습니다.

---

2. 세그먼트 트리 초기화 (InitTree 함수)

• 목적: 세그먼트 트리를 초기화하여 구간 합 계산을 위한 데이터 구조를 준비합니다.

1. 4×N4 \times N4×N 크기의 트리를 초기화합니다.
2. 모든 값을 0으로 설정하여 초기 상태를 만듭니다.

---

3. 세그먼트 트리 쿼리 (Query 함수)

• 목적: 특정 범위 [left,right][left, right][left,right] 내의 값을 계산합니다.

1. 기저 조건:
   • 쿼리 범위와 현재 구간이 겹치지 않으면 0을 반환합니다.
   • 쿼리 범위가 현재 구간을 완전히 포함하면 해당 노드 값을 반환합니다.
2. 재귀 처리:
   • 구간을 왼쪽과 오른쪽으로 나누어 각각 쿼리를 수행합니다.
   • 두 결과를 합산하여 반환합니다.

---

4. 세그먼트 트리 갱신 (Update 함수)

• 목적: 특정 위치의 값을 변경하고 세그먼트 트리를 업데이트합니다.

1. 기저 조건:
   • 변경하려는 인덱스가 현재 구간에 포함되지 않으면 반환합니다.
   • 현재 구간이 단일 원소라면 값을 갱신합니다.
2. 재귀 처리:
   • 구간을 왼쪽과 오른쪽으로 나누어 해당 인덱스가 포함된 자식 노드를 갱신합니다.
   • 갱신된 자식 노드 값을 기반으로 부모 노드를 갱신합니다.

---

5. 역전 수 계산 (Game_Start 함수)

• 목적: 문자열 배열 간 순서 차이를 기반으로 역전 수를 계산합니다.

1. 입력값을 읽고 Input 및 InitTree 함수로 초기화합니다.
2. 첫 번째 배열의 각 문자열에 대해:
   • 해당 문자열이 두 번째 배열에서 매핑된 위치를 가져옵니다 (idxidxidx).
   • 현재 문자열보다 뒤에 있으면서 작은 값의 개수를 세그먼트 트리 쿼리로 계산합니다.
     • Query(1,1,N,idx+1,N)\text{Query}(1, 1, N, idx + 1, N)Query(1,1,N,idx+1,N)은 idxidxidx 이후 값들의 합을 구합니다.
   • 해당 문자열의 위치를 세그먼트 트리에 추가합니다.
     • Update(1,1,N,idx,1)\text{Update}(1, 1, N, idx, 1)Update(1,1,N,idx,1)은 현재 위치에 1을 추가합니다.
3. 모든 문자열에 대해 역전 수를 누적하고 결과를 출력합니다.

[소스 코드]

#include <iostream>
#include <vector>
#define ll long long
using namespace std;

vector<ll> lazy;
vector<ll> tree;
int N, M;

void Propagation(int node, int start, int end) {
	if (lazy[node] != 0) {
		tree[node] = (end - start + 1) -tree[node];

		if (start != end) {
			lazy[node * 2] ^= lazy[node];
			lazy[node * 2 + 1] ^= lazy[node];
		}
		lazy[node] = 0;
	}
}

void Update(int node, int start, int end, int left, int right) {
	Propagation(node, start, end);

	if (left <= start && end <= right) {
		lazy[node] ^= 1;
		Propagation(node, start, end);
		return;
	}
	int mid = (start + end) / 2;
	Update(node * 2, start, mid, left, right);
	Update(node * 2 + 1, mid + 1, end, left, right);

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

int Query(int node, int start, int end, int left, int right) {
	Propagation(node, start, end);

	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 >> M;
	tree.assign(4 * N, 0);
	lazy.assign(4 * N, 0);

	for (int i = 0; i < M; i++) {
		int flag, Si, Ti;
		cin >> flag >> Si >> Ti;

		if (flag == 0) {

			Update(1, 1, N, Si, Ti);
		}
		else {

			cout << Query(1, 1, N, Si, Ti) << '\n';
		}
	}
}

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

	Game_Start();
	return 0;
}