백준 : 12844

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

12844번: XOR

세그먼트 트리 늦은 전파문제.

XOR연산은 A ^ B = C 
라고한다면
A ^ B ^ B = A^(0) = A 가 된다.

이걸이용해서 풀면된다.

laze를 상속할때는 laze[n*2] = laze[n*2] ^ laze[n] 을 해서 기존 laze에 추가적으로 비트연산을 추가해주면된다.

A ^ B = B ^ A 랑 같다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class B12844 {
    static int N;
    static int M;
    static int arr[];
    static int Tree[];
    static int laze[];
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
 
        arr = new int[N + 1];
        Tree = new int[4 * N];
        laze = new int[4 * N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int n = 1; n <= N; n++) {
            arr[n] = Integer.parseInt(st.nextToken());
        }
        Init(1, N, 1);
        M = Integer.parseInt(br.readLine());
 
        for (int m = 1; m <= M; m++) {
            st = new StringTokenizer(br.readLine());
            int t = 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 (t == 1) {
                int c = Integer.parseInt(st.nextToken());
                Update(1, N, a, b, c, 1);
            } else {
                System.out.println(getValue(1, N, a, b, 1));
            }
        }
 
    }
 
    public static int getValue(int start, int end, int a, int b, int n) {
        lazeUpdate(start, end, n);
        if (b < start || end < a)
            return 0;
 
        if (a <= start && end <= b) {
            return Tree[n];
        }
 
        int mid = (start + end) / 2;
 
        return (getValue(start, mid, a, b, n * 2)) ^ (getValue(mid + 1, end, a, b, n * 2 + 1));
 
    }
 
    public static void lazeUpdate(int start, int end, int n) {
        if (laze[n] == 0)
            return;
        if ((end - start + 1) % 2 == 1) Tree[n] ^= laze[n];
        if (start != end) {
            laze[n * 2] ^= laze[n];
            laze[n * 2 + 1] ^= laze[n];
        }
        laze[n] = 0;
    }
 
    public static void Update(int start, int end, int a, int b, int c, int n) {
        lazeUpdate(start, end, n);
        if (b < start || end < a)
            return;
 
        if (a <= start && end <= b) {
            laze[n] = c;
            lazeUpdate(start, end, n);
            return;
        }
 
        int mid = (start + end) / 2;
        Update(start, mid, a, b, c, n * 2);
        Update(mid + 1, end, a, b, c, n * 2 + 1);
        Tree[n] = Tree[n * 2] ^ Tree[n * 2 + 1];
 
    }
 
    public static int Init(int start, int end, int n) {
        if (start == end) {
            return Tree[n] = arr[start];
        }
 
        int mid = (start + end) / 2;
 
        return Tree[n] = (Init(start, mid, n * 2)) ^ (Init(mid + 1, end, n * 2 + 1));
    }
}