BOJ 12844 | XOR

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

레이지 프로퍼게이션을 쓰는 연습 문제입니다.

XOR 연산은 합 연산과 다르게 구간 [s, e]에 대해 (e-s+1) 이 홀수일 때만 노드에 lazy를 xor해주면 됩니다.

0^a = a
a^a = 0
x^a^a = x

인 점을 생각해서 코드를 짜면 됩니다.

원래는 여러 조건도 빠져 있고 데이터도 말썽이 심했다고 들었는데 지금은 일반적인 연습문제가 된 것 같습니다.

코드

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define ll long long
#define pll pair<ll, ll>
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

class SegTree{
private:
	vector<ll> tree;
	vector<ll> lazy;
public:
	SegTree(int N){
		tree.resize(N*4);
		lazy.resize(N*4);
	}
	
	ll init(vector<ll> &nums, ll node, ll s, ll e){
		if (s == e) return tree[node] = nums[s];
		
		return tree[node] = init(nums, node*2, s, (s+e)/2) ^ init(nums, node*2+1, (s+e)/2+1, e);
	}
	
	void update(ll node, int s, int e, int l, int r, ll dx){
		push(node, s, e);
		if (e < l || r < s) return; // break condition
		if (s >= l && e <= r){ // tag condition
			lazy[node] ^= dx;
			push(node, s, e);
			return;
		}
		
		update(node*2, s, (s+e)/2, l, r, dx);
		update(node*2+1, (s+e)/2+1, e, l, r, dx);
		tree[node] = tree[node*2] ^ tree[node*2+1];
	}
	
	void push(ll node, int s, int e){
		if (lazy[node] != 0){
			if ((e-s+1) & 1)
				tree[node] ^= lazy[node];
			if (s != e){
				lazy[node*2] ^= lazy[node];
				lazy[node*2+1] ^= lazy[node];
			}
			lazy[node] = 0;
		}
	}
	
	ll query(ll node, int s, int e, int l, int r){
		push(node, s, e);
		if (s > r || l > e) return 0;
		if (l <= s && e <= r) return tree[node];
		
		return query(node*2,s,(s+e)/2,l,r) ^ query(node*2+1,(s+e)/2+1,e,l,r);
	}
	
};

int main(){
	FASTIO;
	int N, Q; cin >> N;
	SegTree SG(N);
	vector<ll> a; a.push_back(0);
	
	for (int i = 0; i < N; i++){
		ll t; cin >> t;
		a.push_back(t);
	}
	
	cin >> Q;
	SG.init(a, 1, 1, N);
	
	for (int i = 0; i < Q; i++){
		ll o, x, y; cin >> o >> x >> y;
		x++; y++;
		if (o == 1){
			ll v; cin >> v;
			SG.update(1, 1, N, x, y, v);
		}
		else{
			cout << SG.query(1, 1, N, x, y) << endl;
		}
	}
}