백준) 스위치_1395

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

 

🐢 설명

인덱스드 트리 + 천천히 갱신되는 트리 활용이다. 이러한 유형의 문제들의 특징은 값의 변경이 특정 인덱스 하나가 아니라 범위로 주어진다는 특징이 있다.

 

하나의 값 변경에는 logN이 소요되고 범위가 1~N으로 주어지면 NlogN, 이러한 쿼리가 M번 주어지면 M * N * log N이 되어 N^2을 넘어가는 시간복잡도를 갖게된다. 따라서 시간복잡도 개선을 위해 값 변경이 이뤄지는 구간에 대해서 동일한 변경이 이뤄지는 노드들의 공통 부모에만 변경사항을 쌓아놓고 실제 변경이 필요할 때 자식노드로 변경해야할 값을 적용하도록 하는 지연 갱신 방식이 사용된다.

 

예를들어서 1~8번 노드가 존재한다고 하자. 이때 update(1, 8, 10)으로 1~8번 노드에 +10을 하라는 명령이 오면 이를 각 노드에 모두 전파하지 않고, 1~8의 공통 부모에만 +10을 적용하게 한다. 만약 update(1, 8, diff)가 100번 오더라도 공통 부모에만 diff 값을 적용하다가 실제 query(1, 8)을 물으면 그때 합산 diff를 자식노드에 전달한다.

 

이 경우에는 구간의 스위치를 키고 끄고 하므로 각 트리 노드는 자식 노드의 켜진 스위치 개수를 갖도록 한다. 이후 스위치 반전 명령이 오면 (하위 노드 개수 - 현재 켜진 개수)가 현재 켜진 개수로 변경되므로 이를 현재 노드 값으로 변경한다. 이후 자식 노드의 지연 변경 배열에 기록을 하기 위해 1이면 0으로, 0이면 1로 변경한다.

 

기존 인덱스드 트리 구조에서 updateLazy() 함수를 추가해서 변경사항이 있다면 적용하고, 자식에게 변경사항을 상속하고 자신의 변경사항은 적용됐으므로 0으로 지우면 된다. 이 함수는 update()에도 넣고, query()에도 넣어줘야 한다.

 

🐢코드

package 인덱스트리;

import java.io.*;
import java.util.*;

public class 스위치_1395 {
	static int N;
	static int M;
	static int S;
	static int[] lazy;
	static int[] tree;
	static StringBuilder answer = new StringBuilder();

	public static void main(String[] args) throws Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		S = 1;
		while (S < N) S *= 2;
		lazy = new int[S * 2];
		tree = new int[S * 2];

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int cmd = Integer.parseInt(st.nextToken());
			int queryLeft = Integer.parseInt(st.nextToken());
			int queryRight = Integer.parseInt(st.nextToken());

			if (cmd == 0) {
				updateRange(1, 1, S, queryLeft, queryRight);
			} else if (cmd == 1) {
				int count = query(1, 1, S, queryLeft, queryRight);
				answer.append(count).append("\n");
			}
		}

		System.out.print(answer);
	}

	private static void updateRange(int node, int start, int end, int queryLeft, int queryRight) {
		updateLazy(node, start, end);

		if (queryLeft > end || queryRight < start) return;

		if (queryLeft <= start && end <= queryRight) {
			tree[node] = (end - start + 1) - tree[node];

			if (start != end) {
				lazyTurn(node * 2);
				lazyTurn(node * 2 + 1);
			}
			return;
		}

		int mid = (start + end) / 2;
		updateRange(node * 2, start, mid, queryLeft, queryRight);
		updateRange(node * 2 + 1, mid + 1, end, queryLeft, queryRight);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}

	private static void updateLazy(int node, int start, int end) {
		if (lazy[node] != 0) {
			tree[node] = (end - start + 1) - tree[node];

			if (start != end) {
				lazyTurn(node * 2);
				lazyTurn(node * 2 + 1);
			}

			lazy[node] = 0;
		}
	}

	private static int query(int node, int start, int end, int queryLeft, int queryRight) {
		updateLazy(node, start, end);

		if (queryLeft > end || queryRight < start)
			return 0;

		if (start == end)
			return tree[node];

		if (queryLeft <= start && end <= queryRight)
			return tree[node];

		int mid = (start + end) / 2;
		return query(node * 2, start, mid, queryLeft, queryRight) +
				query(node * 2 + 1, mid + 1, end, queryLeft, queryRight);
	}

	private static void lazyTurn(int node) {
		lazy[node] = lazy[node] == 1 ? 0 : 1;
	}
}

🐢 마무리