백준 1395 c++ "스위치" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 세그먼트 자료구조를 이용하여 풀어아 되는 문제이다.

또한 Update함수를 호출할때 범위 내 left 와 right의 변경을 요함으로 매번 하나하나 변경하게 되면

시간초과가 발생하게 된다. 이에 대한 해결법은 Propagation을 이용하여 느린 전파를 하게 되면 

시간내에 풀수 있다.

또한 이 문제만의 매력은 ^연산자 즉 xor연산자를 사용하여 0을 1로 1을 0으로 뒤집는 연산이다.

모든 연산을 ^으로 하는게 아니라 갱신만 저렇게 하고 나머지는 합을 구하므로 합연사으로 진행해 주어야 된다.

[코드 해설]

1. Lazy Propagation을 활용한 업데이트 (Update 함수)

• 목적: 특정 구간의 값을 XOR 연산을 통해 반전시킵니다.

1. Propagation을 호출하여 현재 노드에 적용되지 않은 lazy 값을 처리합니다.
2. 현재 구간이 업데이트 범위에 완전히 포함되면:
   • Lazy 배열을 갱신하여 반전 연산을 예약합니다.
   • 즉시 Propagation을 호출하여 변경 사항을 적용합니다.
3. 업데이트 범위가 현재 구간과 겹치는 경우:
   • 구간을 왼쪽과 오른쪽으로 나누어 재귀적으로 처리합니다.
   • 자식 노드 값을 기반으로 현재 노드의 값을 갱신합니다.

---

2. Lazy Propagation을 활용한 쿼리 처리 (Query 함수)

• 목적: 특정 구간 내 "1의 개수"를 계산합니다.

1. Propagation을 호출하여 현재 노드에 적용되지 않은 lazy 값을 처리합니다.
2. 현재 구간이 쿼리 범위와 겹치지 않으면 0을 반환합니다.
3. 현재 구간이 쿼리 범위에 완전히 포함되면:
   • 해당 노드의 값을 반환합니다.
4. 쿼리 범위가 구간과 일부 겹치는 경우:
   • 구간을 왼쪽과 오른쪽으로 나누어 재귀적으로 처리합니다.
   • 자식 노드에서 반환된 값을 합산하여 반환합니다.

---

3. Propagation 함수

• 목적: Lazy Propagation을 통해 예약된 연산을 처리하고, 자식 노드에 전파합니다.

1. lazy[node] 값이 0이 아니라면:
   • 현재 노드의 값을 업데이트합니다. (구간 길이에서 현재 "1의 개수"를 뒤집음)
   • 리프 노드가 아닌 경우:
     • Lazy 값을 자식 노드로 전파하여 구간 업데이트를 예약합니다.
   • Lazy 값을 초기화합니다.

---

4. 입력 처리 및 명령 수행 (Game_Start 함수)

• 목적: 세그먼트 트리와 Lazy 배열을 초기화하고 명령을 처리합니다.

1. 배열 크기 NNN과 명령 개수 MMM을 입력받습니다.
2. 세그먼트 트리와 Lazy 배열의 크기를 초기화합니다.
3. MMM개의 명령을 처리합니다:
   • 명령 0: 구간 [Si,TiSi, TiSi,Ti]의 값을 반전시킵니다.
   • 명령 1: 구간 [Si,TiSi, TiSi,Ti]에서 "1의 개수"를 출력합니다.

---

5. 메인 함수

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

1. Game_Start 함수를 호출하여 전체 프로그램을 실행합니다.
2. 표준 입출력을 최적화하여 빠르게 동작하도록 설정합니다.

[소스 코드]

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