[BOJ] 백준 12844번 XOR (Java)

#12844 XOR

난이도 : 플레 3

유형 : 세그먼트 트리 / Lazy Propagation

12844번: XOR

▸ 문제

크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자.

• 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다.
• 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다.

▸ 입력

첫 번째 줄에 수열의 크기 N이 주어진다.

두 번째 줄에는 A0, A1, ..., AN-1이 차례대로 주어지며, 공백 한 칸으로 구분되어져 있다.

세 번째 줄에는 쿼리의 개수 M이 주어지고, 다음 M개의 줄에 쿼리가 한 줄에 하나씩 주어진다.

▸ 출력

2번 쿼리의 결과를 모두 출력한다.

• 1 ≤ N, M ≤ 500,000
• 0 ≤ Ai ≤ 100,000
• Ai는 정수
• 쿼리 1, 2
  • 0 ≤ i ≤ j < N
• 쿼리 1
  • 0 ≤ k ≤ 100,000
  • k는 정수

 

문제 풀이  

세그먼트 트리 구간 업데이트는 lazy propagation을 사용하여 풀이를 해줘야 한다. 구간 XOR는 그냥 기존 그대로 사용한다. 다만 메소드 도입부분에 업데이트 로직만 추가해주면 된다.

• 최악의 경우 전체 구간을 계속해서 갱신해줘야 하는데, 그러면 트리 자료구조를 쓰는 의미가 없어진다. O(NM)
• 느리게 갱신되는 lazy propagation 기법을 쓰면 O(MlogN)으로 처리할 수 있다.

 

세그먼트 트리 + Lazy Propagation에 대한 자세한 설명은 여기를 참고해주세요.

 

느리게 갱신시키기

구간 합과 다른점은 부모 노드(tree[node])를 갱신하는 부분이다. 원래는 lazy[node] * (e-s+1)로 자식노드의 개수를 곱해줘야 했는데, XOR은 그런건 상관없고 홀수일 때는 lazy[node], 짝수일 때는 0을 넣어주면 된다. 즉, 홀수일 때만 갱신해주면 된다.

• 자식노드가 짝수개일 때, a^a = 0
• 자식노드가 홀수개일 때, a^a^a = a

static void propagate(int s, int e, int node) {
	if(lazy[node] != 0) {
		if(s!=e) {
			lazy[node*2] ^= lazy[node];
			lazy[node*2+1] ^= lazy[node];
		}
		if((e-s+1)%2 == 1) { // a^a = 0
			tree[node] ^= lazy[node] * (e-s+1);
		}
		lazy[node] = 0;
	}
}

 

XOR 구간 업데이트

해당 원소가 변경되는 것이 아니라 [a, b] 구간에 c값을 xor하는 것이기 때문에, 기존 원소 값 갱신없기 구간 업데이트만 해주면 된다.

 

1 2 4 9 연산([a, b]에 9를 xor하기)을 수행하면 다음과 같다.

구간 XOR 업데이트하기

 

XOR 구간

XOR구간은 구간합과 구할 때와 같이 XOR한 값을 출력해주면 된다.

 

2 0 4 연산([0, 4]을 모두 xor하기)을 수행하면 다음과 같다. 전체구간이므로 루트노드를 출력해주면 된다.

구간 XOR 구하기

 

 

마지막으로 lazy된 부분을 업데이트 시켜주려면 각 노드의 값을 구해주는 연산을 수행해주면 된다. 3번 노드가 갱신이 필요없는 이유는 위에서 말했다시피 자식노드가 짝수개이기 때문이다.

• 2 3 3 : [3, 3] XOR 구하기
• 2 4 4 : [4, 4] XOR 구하기

 

풀이 코드 

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

public class Main {
	static int n;
	static int[] arr, tree, lazy;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		arr = new int[n+1];
		tree = new int[4*n];
		lazy = new int[4*n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=1; i<=n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		init(1,n,1);
		
		StringBuilder sb = new StringBuilder();
		int m = Integer.parseInt(br.readLine());
		while(m-->0) {
			st = new StringTokenizer(br.readLine());
			int op = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken())+1;
			int b = Integer.parseInt(st.nextToken())+1;
			if(a > b) {
				int tmp = a;
				a = b;
				b = tmp;
			}
			if(op == 1) {
				int v = Integer.parseInt(st.nextToken());
				update(1,n,1,a,b,v);
			} else {
				sb.append(pXOR(1,n,1,a,b)+"\n");
			}
		}
		System.out.println(sb.toString());
	}
	
	static int init(int s, int e, int node) {
        if (s == e) {
            return tree[node] = arr[s];
        }
        int mid = (s+e)/2;
        return tree[node] = init(s, mid, node*2)^init(mid + 1, e, node*2+1);
    }
	
	
	static void update(int s, int e, int node, int l, int r, int dif) {
		propagate(s, e, node);
		if(r < s ||  e < l) return;
		if(l <= s && e <= r) {
			lazy[node] = dif;
			propagate(s, e, node);
			return;
		}
		int mid = (s+e)/2;
        update(s, mid, node*2, l, r, dif);
        update(mid + 1, e, node*2+1, l, r, dif);
        tree[node] = tree[node*2] ^tree[node*2+1];
	}
	
	static int pXOR(int s, int e, int node, int l, int r) {
		propagate(s, e, node);
		if(r < s ||  e < l) return 0;
		if(l <= s && e <= r) {
			return tree[node];
		}
		
		int mid = (s+e)/2;
		return pXOR(s, mid, node*2, l, r)^pXOR(mid+1, e, node*2+1, l, r);
	}
	
	static void propagate(int s, int e, int node) {
		if(lazy[node] != 0) {
			if(s!=e) {
				lazy[node*2] ^= lazy[node];
				lazy[node*2+1] ^= lazy[node];
			}
			if((e-s+1)%2 == 1) { // a^a = 0
				tree[node] ^= lazy[node];
			}
			lazy[node] = 0;
		}
	}
}