[백준] 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는 정수

 

LazyProp문제입니다.

다른 XOR문제와 다른점은 2번쿼리가 i부터j까지 모두 xor한 값을 출력하는것입니다.

따라서 업데이트쿼리에서 자식노드 둘을 xor하면 되는데...

 

삽질을 좀 했습니다.....

세그트리의 n번 노드를 검사할때, n번 노드가 포함하는 범위 내의 숫자들이 홀수개면 seg[n]은 ^k를 해줘야합니다.

왜냐하면 ^k ^k 두번하면 제자리이기 때문입니다.

이는 propagation함수에서 사용하는 논리입니다.

 

업데이트함수에서 seg트리를 갱신할때, 굳이 홀/짝을 나누지 않고 그냥 자식노드 둘을 xor해주면 됩니다.

이때 범위를 넘어가더라도 seg[child]를 반환해주어야 xor할때 이상한값을 출력하지 않습니다.

 

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321;
int N, M, a[500001], seg[2000004], lazy[2000004];
int init(int l, int r, int n) {
	if (l == r) {
		return seg[n] = a[l];
	}
	int mid = (l + r) / 2;
	return seg[n] = init(l, mid, n * 2) ^ init(mid + 1, r, n * 2 + 1);
}
void propagate(int l, int r, int n) {
	if (lazy[n]) { //lazy가 존재하면
		if (l != r) {//자식노드가 있다면 lazy를 옮겨주고
			lazy[n * 2] ^= lazy[n];
			lazy[n * 2 + 1] ^= lazy[n];
		}
		if ((r - l + 1) % 2)seg[n] ^= lazy[n]; //만약 현재노드에서 포함하는 범위가 홀수라면 seg값이 갱신됩니다
		lazy[n] = 0;
	}
}
int update(int l, int r, int n, int f, int t, int k) {
	propagate(l, r, n);
	if (r < f || t < l)return seg[n]; //범위를 넘어서더라도 부모노드에서 xor을 해주어야하므로 seg[n]을 반환합니다.
	if (f <= l && r <= t) {
		lazy[n] ^= k;
		propagate(l, r, n);
		return seg[n];
	}
	int mid = (l + r) / 2;
	return seg[n]=update(l, mid, n * 2, f, t, k)^update(mid+1,r,n*2+1,f,t,k);
}
int query(int l, int r, int n, int f, int t) {
	propagate(l, r, n);
	if (r < f || t < l)return 0;
	if (f <= l && r <= t)return seg[n];
	int mid = (l + r) / 2;
	return query(l, mid, n * 2, f, t) ^ query(mid + 1, r, n * 2 + 1, f, t);
}
int main() {
	FAST;
	cin >> N;
	REP(i, N)
		cin >> a[i];
	init(1, N, 1);
	cin >> M;
	while (M--) {
		int x;
		cin >> x;
		if (x == 1) {
			int f, t, k;
			cin >> f >> t >> k; //f부터t까지 k XOR한다
			update(1, N, 1, f + 1, t + 1, k);
		}
		else {
			int f, t;
			cin >> f >> t; //t의 값 출력
			cout << query(1, N, 1, f + 1, t + 1) << "\n";
		}
	}
}