백준 스위치(1395)

스위치

1. 힌트

1) 스위치가 켜져 있는지 여부를 $0$과 $1$로 나타내면 구간 내의 켜진 스위치의 개수는 구간의 합과 같다.

2) 구간 내의 스위치들을 반전시키는 연산을 $O(lgN)$에 처리하려면 lazy propagation이 필요하다.

3) $[s, e]$에 대해 반전시키면 켜진 스위치의 개수는 $(e - s + 1) - sum(s, e)$가 된다.

2. 접근

1) 문제를 분해할 수 있을까?

lazy propagation 연습 문제. 반전 시키는 연산을 바로 연산하지 않고 lazy배열에 저장해둘 수 있다. 반전을 두번 시키면 결국 원래대로 돌아오기 때문에 lazy배열은 boolean으로 선언할 수 있다.
$[s, e]$에 대해 반전 연산은 주어진 구간을 절반으로 나눠서 $[s, mid], [mid + 1, e]$ 재귀적으로 연산할 수 있다.

3. 구현

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		RSQ q = new RSQ(N);
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int O = Integer.parseInt(st.nextToken());
			int S = Integer.parseInt(st.nextToken()) - 1;
			int T = Integer.parseInt(st.nextToken()) - 1;
			if (O == 0) q.update(S, T);
			else bw.append(q.query(S, T)).append("\n");
		}
		System.out.print(bw);
	}
	
}
class RSQ {
	int n; int[] range; boolean[] lazy;
	
	RSQ(int length) {
		this.n = length;
		range = new int[4 * n]; lazy = new boolean[4 * n];
	}
	
	int query(int left, int right) {
		return query(left, right, 1, 0, n - 1);
	}
	
	private int query(int left, int right, int node, int nodeLeft, int nodeRight) {
		propagate(node, nodeLeft, nodeRight);
		if (right < nodeLeft || nodeRight < left) return 0;
		if (left <= nodeLeft && nodeRight <= right) return range[node];
		int mid = (nodeLeft + nodeRight) / 2;
		return query(left, right, 2 * node, nodeLeft, mid) + query(left, right, 2 * node + 1, mid + 1, nodeRight);
	}
	
	void update(int left, int right) {
		update(left, right, 1, 0, n - 1);
	}
	
	private void update(int left, int right, int node, int nodeLeft, int nodeRight) {
		propagate(node, nodeLeft, nodeRight);
		if (right < nodeLeft || nodeRight < left) return;
		if (left <= nodeLeft && nodeRight <= right) {
			lazy[node] ^= true;
			propagate(node, nodeLeft, nodeRight);
			return;
		}
		int mid = (nodeLeft + nodeRight) / 2;
		update(left, right, 2 * node, nodeLeft, mid);
		update(left, right, 2 * node + 1, mid + 1, nodeRight);
		range[node] = range[2 * node] + range[2 * node + 1];
	}
	
	private void propagate(int node, int nodeLeft, int nodeRight) {
		if (lazy[node]) {
			if (nodeLeft != nodeRight) {
				lazy[2 * node] ^= true;
				lazy[2 * node + 1] ^= true;
			}
			range[node] = nodeRight - nodeLeft + 1 - range[node];
			lazy[node] = false;
		}
	}
	
}

1) 시간 복잡도

두 가지 쿼리 모두 시간 복잡도가 $O(lgN)$이므로 전체 시간 복잡도는 $O(MlgN)$

2) 테스트 케이스