백준 4297 c++ "Ultra-QuickSort" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 inverstion Counting 문제를 이용하여 푸는 문제이다.

필자는 주어지는 값들이 범위가 크기 때문에 좌표 압축을 통해 인덱스들을 관리했고

그 이후 inverstion 카운팅 알고리즘을 이용하여 해당 갯수들을 출력했다.

[코드 해설]

. 입력 처리 (Input 함수)

• 목적: 입력 데이터를 받아 배열을 초기화하고, 좌표 압축을 수행합니다.

1. 입력으로 크기 NNN과 NNN개의 숫자를 받습니다.
2. 입력된 값과 해당 인덱스를 arrarrarr 벡터에 저장합니다.
   • 예: arr[i]=(값,인덱스)arr[i] = (\text{값}, \text{인덱스})arr[i]=(값,인덱스)
3. arrarrarr를 값 기준으로 정렬한 뒤, 좌표 압축을 수행합니다.
   • 압축된 값은 compressedArrcompressedArrcompressedArr에 저장되며, 각 원소의 새로운 순서를 나타냅니다.
   • compressedArr[원본 인덱스]=압축된 순서compressedArr[\text{원본 인덱스}] = \text{압축된 순서}compressedArr[원본 인덱스]=압축된 순서

---

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

• 목적: 세그먼트 트리의 크기를 배열 크기에 맞게 초기화합니다.

1. 4×N4 \times N4×N 크기의 트리를 초기화하여 모든 노드를 0으로 설정합니다.

---

3. 세그먼트 트리 업데이트 (Update 함수)

• 목적: 특정 위치의 값을 갱신합니다.

1. 구간 [start,end][start, end][start,end]에서, idxidxidx 위치에 valvalval을 추가합니다.
2. idxidxidx가 현재 노드의 구간에 포함될 경우:
   • 리프 노드까지 내려가며 값을 갱신합니다.
3. 리프 노드에서 값이 변경되면, 부모 노드들도 재귀적으로 값을 갱신합니다.

---

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

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

1. 현재 노드의 구간이 쿼리 범위와 겹치지 않는 경우, 0을 반환합니다.
2. 현재 노드의 구간이 쿼리 범위에 완전히 포함된 경우, 노드 값을 반환합니다.
3. 일부만 겹치는 경우, 구간을 분할하여 왼쪽과 오른쪽 자식 노드의 값을 합산합니다.

---

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

• 목적: 배열 내 역전 수를 계산합니다.

1. 입력 값을 읽어 Input 함수를 호출하고, 배열 및 세그먼트 트리를 초기화합니다.
2. 각 원소를 순서대로 처리하며 다음을 수행합니다:
   • 현재 원소의 압축된 순서를 idxidxidx로 가져옵니다.
   • idx+1idx + 1idx+1부터 NNN까지의 값(자신보다 큰 원소 개수)을 Query로 계산합니다.
   • 계산된 값은 역전 수에 누적합니다.
   • 현재 위치 idxidxidx에 대해 Update를 호출하여 값을 갱신합니다.
3. 모든 원소를 처리한 후, 누적된 역전 수를 출력합니다.

---

6. 메인 함수

• 목적: 프로그램 실행의 시작점입니다.

1. Game_Start 함수를 호출하여 역전 수 계산 프로그램을 반복적으로 실행합니다.
2. N=0N = 0N=0이 입력되면 프로그램을 종료합니다.

[소스 코드]

#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;
}