[백준] 14245 XOR

문제

문제가 길면 출제자도 수강생도 힘들다. 따라서 이 문제는 너무 친절하게도 짧다.

수열이 주어 졌을 때 두 가지 연산을 할 수 있다.

• 특정 구간 [a, b]에 c를 xor한다.
• a번째 원소의 값을 출력한다.

초기 수열과 연산의 정보가 주어졌을 때, 그에 맞게 출력하라.

입력

첫 번째 줄에 수열의 크기 n (0 < n ≤ 500,000)이 주어진다.

두 번째 줄에 수열의 원소가 0번부터 n - 1번까지 차례대로 주어진다. 수열의 원소는 100,000보다 크지 않은 음이 아닌 정수이다.

세 번째 줄에 여러분이 수행할 쿼리의 개수 m (0 < m ≤ 500,000)이 주어진다.

그 다음 m개의 줄에는 t로 시작하는 쿼리가 주어진다. t가 1이면 a, b, c를 입력받아 구간 [a, b]의 각 원소에 c를 xor한다.(0 ≤ a ≤ b < n, 0 ≤ c ≤ 100,000) t가 2 이면 a를 입력받아 a번째 원소의 값을 출력한다. (0 ≤ a < n)

출력

쿼리가 2가 들어올 때마다, a번째 원소를 출력하라.

 

 

레이지 문제입니다

a,b에 c를 xor할건데 lazy에 xor할 c를 xor합니다

lazy^=k로 lazy를 저장해두고,

쿼리가 나올때마다 propagate하면서 값을 출력해줍니다.

#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];
void init(int l, int r, int n) {
	if (l == r) {
		seg[n] = a[l]; return;
	}
	int mid = (l + r) / 2;
	init(l, mid, n * 2);
	init(mid + 1, r, n * 2 + 1);
	return;
}
void propagate(int l, int r, int n) {
	if (lazy[n]) {
		if (l != r) {
			lazy[n * 2] ^= lazy[n];
			lazy[n * 2 + 1] ^= lazy[n];
		}
		seg[n] ^= lazy[n];
		lazy[n] = 0;
	}
}
void update(int l, int r, int n, int f, int t, int k) {
	propagate(l,r,n);
	if (r < f || t < l)return;
	if (f <= l && r <= t) {
		lazy[n] = int(lazy[n] ^ k);
		return;
	}
	int mid = (l + r) / 2;
	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 t) {
	propagate(l, r, n);
	if (r < t || t < l)return 0;
	if (l==t && r==t)return seg[n];
	int mid = (l + r) / 2;
	return query(l, mid, n * 2, t) + query(mid + 1, r, n * 2 + 1, 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 t;
			cin >> t; //t의 값 출력
			cout << query(1, N, 1, t+1) << "\n";
		}
	}
}