[P3] 백준 1395번 스위치 C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리

 

리뷰

 

느리게 갱신되는 세그먼트 트리 문제 치고 굉장히 짧고 쉬운 문제!

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

 

전역 변수

• MAX_N : 스위치의 최대 개수를 정의할 정수형 상수 변수
• tree : 세그먼트 트리 정보를 저장할 배열 MAX_N * 4 크기로 초기값은 0이다.
• lazy : 업데이트 갱신을 적용하기 위한 트리 배열 MAX_N * 4 크기로 초기값은 0이다.
• n, m : 스위치의 개수를 저장할 변수 n, 쿼리의 개수를 저장할 변수 m

 

함수

1. propagate

void propagate(int node, int start, int end)

 

1. 현재 노드에 갱신이 필요하다면 갱신을 진행하고 자식 노드에 지연 업데이트를 기록하는 함수이다.
2. 현재 노드에 갱신이 필요하다면 구간의 길이 - 자신의 값을 새로운 값으로 갱신해 준다.
3. 현재 노드가 리프 노드가 아니라면 자식에게 업데이트 정보를 전달해 주어야 한다.
4. 자식 노드의 lazy가 1이라면 0으로, 0이라면 1로 반전하여 전달해 주면 된다.
5. 갱신이 완료되었다면 자기 자신의 업데이트 정보를 다시 0으로 초기화 해준다.

 

2. update

void update(int node, int start, int end, int L, int R)

 

1. 구간에 업데이트를 적용시킬 함수이다.
2. 함수 시작과 동시에 현재 노드에서 propagate를 실행해 줘 갱신되지 않은 업데이트가 있다면 진행해 준다.
3. 구간을 포함하는 범위가 나왔을 경우 현재 노드의 lazy가 0이라면 1로, 1이라면 0으로 갱신시켜 준다.
4. 이후 현재 노드를 기준으로 propagate함수를 실행해 주고 리턴 처리해 준다.
5. 범위 내에 존재하지 않다면 왼쪽 오른쪽을 각각 탐색하여 update를 재귀로 진행해 준다.
6. 재귀가 완료되면 누적합 업데이트를 진행해 준다.

 

3. query

int query(int node, int start, int end, int L, int R)

 

1. 구간 내 스위치가 켜진 합을 출력해 줄 함수이다.
2. update와 마찬가지로 함수 시작과 동시에 현재 노드에서 propagate 함수를 실행해 준다.
3. 구간을 포함하는 범위가 나왔을 경우 트리의 현재 노드값을 리턴해 준다.
4. 범위 내에 존재하지 않다면 왼쪽 오른쪽을 각각 탐색하여 리턴값을 받아 저장해 준다.
5. 재귀가 완료되면 왼쪽과 오른쪽 값을 더해 리턴해 준다.

 

문제풀이

1. n과 m값을 입력 받아준다, 스위치는 모두 꺼진 상태로 시작하므로 tree는 build없이 0으로 초기화 해주면 된다.
2. m개의 쿼리를 받을 반복문을 실행해 주고, 명령과 범위 정보를 입력 받아준다.
3. 명령이 0일경우 범위 내 스위치를 반전시켜 주고, 명령이 1일 경우 범위 내 켜진 스위치의 합을 구해준 뒤 출력한다.

 

참고 사항

1. 초기에는 모든 스위치의 상태는 꺼져있는 상태로 되어있다.
2. 노드 배열이 필요가 없으니 세그먼트 트리의 build가 전혀 필요가 없다는 말이다.
3. 업데이트 및 lazy업데이트를 진행할때 스위치를 반전 시켜주는게 중요한 문제이다. (삼항 연산자를 사용하면 간단하게 구현할 수 있다.)

 

정답 코드

#include<iostream>

using namespace std;

const int MAX_N = 100000;
int tree[MAX_N * 4] = { 0, };
int lazy[MAX_N * 4] = { 0, };
int n, m;

void propagate(int node, int start, int end) {
	if (lazy[node]) {
		tree[node] = (end - start + 1) - tree[node];
		if (start != end) {
			lazy[node * 2] = lazy[node * 2] ? 0 : lazy[node];
			lazy[node * 2 + 1] = lazy[node * 2 + 1] ? 0 : lazy[node];
		}
		lazy[node] = 0;
	}
}

void update(int node, int start, int end, int L, int R) {
	propagate(node, start, end);
	if (R < start || end < L) return;
	if (L <= start && end <= R) {
		lazy[node] = lazy[node] ? 0 : 1;
		propagate(node, start, end);
		return;
	}
	int mid = (start + end) / 2;
	update(node * 2, start, mid, L, R);
	update(node * 2 + 1, mid + 1, end, L, R);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int query(int node, int start, int end, int L, int R) {
	propagate(node, start, end);
	if (R < start || end < L) return 0;
	if (L <= start && end <= R) return tree[node];
	int mid = (start + end) / 2;
	int left = query(node * 2, start, mid, L, R);
	int right = query(node * 2 + 1, mid + 1, end, L, R);
	return left + right;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		if (!a) update(1, 0, n - 1, b - 1, c - 1);
		else cout << query(1, 0, n - 1, b - 1, c - 1) << "\n";
	}
}