BOJ 백준 21918 전구 [JAVA] 느리게 갱신되는 세그먼트 트리

문제 : https://www.acmicpc.net/problem/21918

 

 

[ 문제 요약 ]

• 전구의 개수와 전구의 초기 상태, 켜고 끌 명령어 개수가 주어질 때 해당 명령어대로 실행한 후 전구의 최종 결과를 출력하는 문제입니다. 1은 켜진 상태, 0은 꺼진 상태입니다. 명령어 종류는 아래와 같이 4개가 있습니다.
• 1 i x = i 번째 전구를 x로 변경합니다.
• 2 l r = l ~ r까지의 전구 상태를 반전 시킵니다(xor)
• 3 l r = l ~ r까지의 전구를 모두 끕니다.
• 4 l r = l ~ r까지의 전구를 모두 켭니다.

 

[ 테스트 케이스 설명 ]

8 3// 전구 숫자1<=4000, 쿼리 숫자 1<=4000
0 0 0 0 0 0 0 0// 전구의 초기 상태
1 2 1// 명령어들
1 4 1
2 2 4
답 : 0 0 1 0 0 0 0 0

 

[ 알고리즘 분류 ]

• 구현
• 시뮬레이션

 

[ 문제 해설 ]

 

이 문제는 브론즈 2 레벨 문제로 일반적인 반복문으로 쉽게 해결 가능합니다.

 

느리게 갱신되는 세그먼트 트리로 좀 더 빠르게 해결 가능할 것 같아 고급 알고리즘을 사용해 문제를 풀었습니다.

 

명령어 1은 특정 전구 변경이고, 2는 범위 반전, 3은 범위 off, 4는 범위 on입니다.

 

이를 통해 2번 명령어가 없다면 쉽게 구현이 가능하지만 2번이 있어 구현이 복잡해집니다.

 

일반적인 lazy 정보를 담을 배열을 만들고, 반전(xor)을 담을 배열을 하나 더 만들어서 값을 전파하면 됩니다.

 

식은 아래와 같이 생각하면 됩니다.

 

f(x) = ((lazy != -1) ? lazy : x) ^ (isXor ? 1 : 0)

 

lazy 값 전파할 것이 있다면 전파하고, xor 할게 있다면 계산 결과에 xor을 진행해 줍니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main{
	
	static int N, M;
	static int[] tree, lazy;
	static boolean[] isXor;
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		tree = new int[N * 4];
		lazy = new int[N * 4];
		isXor = new boolean[N * 4];
		
		Arrays.fill(lazy, -1);// 전파 배열의 기본 값은 -1
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
			updateRange(1, 1, N, i, i, Integer.parseInt(st.nextToken()), false);
		
		while(M-->0)
		{
			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken());
			int l = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());
			
			if(i == 1)		updateRange(1, 1, N, l, l, r, false);
			else if(i == 2)	updateRange(1, 1, N, l, r, 0, true);
			else if(i == 3)	updateRange(1, 1, N, l, r, 0, false);
			else if(i == 4)	updateRange(1, 1, N, l, r, 1, false);
		}
		StringBuilder sb = new StringBuilder();

		for(int i=1; i<=N; i++)
			sb.append(query(1, 1, N, i)).append(' ');
		
		System.out.print(sb);
	}
	static void lazy(int treeNode, int s, int e) {
		if(lazy[treeNode] == -1 && !isXor[treeNode])// 전파할 것이 전혀 없다면 스킵
			return;
	
		if(s == e)
		{
			if(lazy[treeNode] != -1) // 다이렉트 저장이 있다면 저장
				tree[treeNode] = lazy[treeNode];
			
			if(isXor[treeNode])// xor도 있다면 xor 처리를 해줌
				tree[treeNode] ^= 1;
		}
		else
		{
			int left = treeNode << 1;
			int right = treeNode << 1 | 1;
			
			if(lazy[treeNode] != -1)// 전파할 값이 있다면
			{
				lazy[left] = lazy[treeNode];// 다이렉트로 전파
				lazy[right] = lazy[treeNode];// 다이렉트로 전파
				isXor[left] = false;// 다이렉트 전파면, xor은 필요 없으므로 false 처리
				isXor[right] = false;// 다이렉트 전파면, xor은 필요 없으므로 false 처리
			}
			
			if(isXor[treeNode])//  xor전파가 있다면
			{
				if(lazy[left] != -1)// lazy 전파가 남아 있다면 해당 값을 반전 처리
					lazy[left] ^= 1;
				else
					isXor[left] = !isXor[left];// lazy전파가 없다면 xor 전파
				
				if(lazy[right] != -1)
					lazy[right] ^= 1;
				else
					isXor[right] = !isXor[right];
			}
		}
		lazy[treeNode] = -1;
		isXor[treeNode] = false;
		
	}
	static void updateRange(int treeNode, int s, int e, int left, int right, int val, boolean xor) {
		
		lazy(treeNode, s, e);
		
		if(e < left || right < s)
			return;
		
		if(left <= s && e <= right)
		{
			if(xor)// 반전일 경우
			{
				if(lazy[treeNode] != -1)// lazy에 값이 있다면 lazy값을 변경함
					lazy[treeNode] ^= 1;
				else
					isXor[treeNode] = !isXor[treeNode];// 아닌경우 xor을 저장
			}
			else
			{
				lazy[treeNode] = val;// 다이렉트 저장은 값을 그대로 대입
				isXor[treeNode] = false;// xor은 false로 초기화
			}
			
			lazy(treeNode, s, e);
			return;
		}
		
		int mid = (s + e) >> 1;
		
		updateRange(treeNode << 1, s, mid, left, right, val, xor);
		updateRange(treeNode << 1 | 1, mid + 1, e, left, right, val, xor);
	}
	static int query(int treeNode, int s, int e, int targetIdx) {
		lazy(treeNode, s, e);
		
		if(e<targetIdx || targetIdx < s)
			return -1;
		
		if(s == e)
			return tree[treeNode];
		
		int mid = (s + e) >> 1;
		
		if(targetIdx <= mid)
			return query(treeNode << 1, s, mid, targetIdx);
		
		return query(treeNode << 1 | 1, mid + 1, e, targetIdx);
	}
}