백준 14427 c++ "수열과 쿼리 15" -PlusUltraCode-

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

 

[필자 사고]

필자는 수열에서 크기가 가장 작은 값의 인덱스를 출력하라고 했다.

처음에는 tree에 pair을 이용하여 자료형을 2개 관리했다. 값과 인덱스

근데 생각해보니 최소값을 찾은 노드에 start 나 end를 반환하면 해당 인덱스가 된다.

이 사실을 늦게 알아서 코드가 상당히 길어졌다.

다음에는 유동적으로 사고해야 되겠다.

[코드 해설]

1. 입력 처리 (Input 함수)

• 목적: 배열 크기와 데이터를 입력받아 초기화합니다.

1. NNN: 배열의 크기를 입력받습니다.
2. arr[i]arr[i]arr[i]: 배열의 각 값을 입력받아 저장합니다.
3. 세그먼트 트리 treetreetree를 크기 4×N4 \times N4×N으로 초기화합니다.

---

2. 두 노드 중 최소값 선택 (whatIsMin 함수)

• 목적: 두 구간의 값을 비교하여 최소값과 해당 인덱스를 반환합니다.

1. 두 노드의 값이 같다면, 인덱스가 작은 노드를 반환합니다.
2. 두 노드의 값이 다르다면, 값이 더 작은 노드를 반환합니다.
3. 반환값은 pair(값,인덱스)\text{pair}(값, 인덱스)pair(값,인덱스) 형태입니다.

---

3. 세그먼트 트리 초기화 (Init_Tree 함수)

• 목적: 세그먼트 트리를 구성하여 구간 내 최소값과 인덱스를 저장합니다.

1. 기저 조건: 현재 구간이 하나의 원소를 나타내면 해당 값을 저장합니다.
2. 재귀 처리:
   • 구간을 왼쪽과 오른쪽으로 나누어 각각 초기화합니다.
   • 두 자식 노드의 값을 비교하여 부모 노드에 최소값과 인덱스를 저장합니다.

---

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

• 목적: 배열의 특정 값을 갱신하고 세그먼트 트리를 업데이트합니다.

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

---

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

• 목적: 특정 범위 [left,right][left, right][left,right] 내 최소값과 인덱스를 구합니다.

1. 기저 조건:
   • 현재 구간이 쿼리 범위와 겹치지 않으면 {0,0}\{0, 0\}{0,0}을 반환합니다.
   • 현재 구간이 쿼리 범위에 완전히 포함되면, 해당 노드 값을 반환합니다.
2. 재귀 처리:
   • 구간을 나누어 왼쪽과 오른쪽 자식 노드의 쿼리 결과를 비교하여 최소값을 반환합니다.

---

6. 게임 시작 (Game_Start 함수)

• 목적: 명령을 처리하고 결과를 출력합니다.

1. 명령의 개수 MMM을 입력받습니다.
2. 세그먼트 트리를 초기화합니다.
3. MMM개의 명령을 처리합니다:
   • 명령 2: 배열 전체 구간의 최소값을 구하고, 해당 인덱스를 출력합니다.
   • 명령 1: 배열의 특정 인덱스를 주어진 값으로 갱신합니다.

---

7. 메인 함수

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

1. Input 함수로 데이터를 입력받습니다.
2. Game_Start 함수로 명령을 처리합니다.

[소스 코드]

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