BOJ 18254 쿼리와 쿼리

http://noj.am/18254

20.03.11 기준 solved.ac R5

 

----------------------------------------스포방지선----------------------------------------

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

M개의 선행 쿼리를 쿼리1, Q개의 후행 쿼리를 쿼리2라고 부르겠다.

 

전처리로 쿼리1이 ${A}_{i}$를 변화시키는 것을 처리해야한다. Lazy Propagation을 이용한 세그먼트 트리로도 가능하지만, 이후에 쿼리2를 처리할 때도 비슷한 구간 xor 쿼리를 처리해야 하기 때문에, 상수의 이득을 위해서 펜윅 트리를 사용하는 것이 좋다. 기우성에 따라 잘 나누어서 펜윅 트리로 처리하면 펜윅 트리 2개만을 이용해서 구간 xor 쿼리를 처리할 수 있다. 아래의 코드를 참고하는 것이 이해하기 좋을 것이다.

시간복잡도는 $O(MlgN)$.

 

쿼리1을 Square Root Decomposition으로 쪼갤 것이다.

각 Bucket마다 Prefix Sum을 통해 현재 Bucket이 관리하는 쿼리1들이 ${A}_{1}$부터 ${A}_{i}$까지를 총 몇 번 구간에 의해 덮는지를 저장한다. 어차피 $x$ $xor$ $x$ $=$ $0$이기 때문에 2로 나눈 나머지만 저장해도 무방하다.

시간복잡도는 $O(N\sqrt{M})$.

 

이제 쿼리2를 처리해야 한다.

갱신 쿼리 : 버킷 전체가 [L, R]에 포함되지 않는 쿼리1들은 그냥 일일히 갱신시켜준다. ($O(\sqrt{M}lgN)$) 나머지 쿼리1들은 버킷에 v값만 xor해서 저장해준다. ($O(\sqrt{M})$)

출력 쿼리 : 모든 버킷을 보면서 ((버킷이 관리하는 쿼리1들이 $[l, r]$을 덮는 횟수)%2)*(버킷에 저장된 v값)을 전부 xor한다. ($O(\sqrt{N})$) 관리하던 A값의 [l, r] 구간 xor값과 xor하면 구하려는 답이다.

 

전체 시간복잡도는 $O(MlgN+N\sqrt{M}+Q\sqrt{M}lgN)$이다.

BOJ 기준 시간은 1.7s, 메모리는 34MB가 나온다.

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

const int MX = 100005, B = 330, C = 310;

int N, M, K, Q;
int ar[MX], L[MX], R[MX], X[C];
bool Qu[C][MX];

struct Fenwick {
	int st[MX];
	void upd(int t, int v) { while (t<=N) st[t]^=v, t+=t&-t; }
	int get(int t) { int r=0; while (t) r^=st[t], t-=t&-t; return r; }
	int get(int s, int e) { return get(s-1)^get(e); }
}A, O, E;

void upd(int l, int r, int v) {
	(l%2?O:E).upd(l, v);
	if ((l^r)&1) (l%2?O:E).upd(r+1, v);
	else (l%2?E:O).upd(r, v);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>N>>M>>Q;
	for (int i=1, a; i<=N; i++) cin>>a, A.upd(i, a);
	K=(M+B-1)/B;
	for (int s=0, l, r, x; s<M; s+=B) {
		int e=min(M, s+B)-1, in=s/B;
		for (int i=s; i<=e; i++) {
			cin>>l>>r>>x; L[i]=l, R[i]=r;
			upd(l, r, x);
			Qu[in][l]^=1; Qu[in][r+1]^=1;
		}
		for (int i=1; i<=N; i++) Qu[in][i]^=Qu[in][i-1];
		for (int i=1; i<=N; i++) Qu[in][i]^=Qu[in][i-1];
	}
	while (Q--) {
		int q, l, r, v;
		cin>>q>>l>>r;
		if (q==1) {
			cin>>v; l--; r--;
			for (int i=l-1; i>=l/B*B; i--) upd(L[i], R[i], v);
			for (int i=r+1; i<M&&i<(r/B+1)*B; i++) upd(L[i], R[i], v);
			for (int i=l/B; i<=r/B; i++) X[i]^=v;
		}
		if (q==2) {
			int v=A.get(l, r);
			v^=((l-1)&1?O:E).get(l-1)^(r&1?O:E).get(r);
			for (int i=0; i<K; i++) v^=X[i]*(Qu[i][r]^Qu[i][l-1]);
			cout<<v<<'\n';
		}
	}
	return 0;
}