BOJ 13704 | 수열과 쿼리 11

수열과 쿼리 0에서 쓰인 prefix sum과 비슷한 기법을 사용한 문제이다.

prefix xor 정도로 부를 수 있겠다.

XOR 연산의 성질인 교환법칙과 결합법칙이 성립한다 정도만 생각해도 풀 수 있겠다.

$A_i$ ^ $A_{i+1}$ ^ ... ^ $A_{j}=K$ 인 $[i, j]$ 를 찾는 것은 다음과 같이 바꿔 쓸 수 있다.

$A_{1}$ ^ ... ^ $A_{i}=X_{i}$ 일 때, $X_{i-1}$ ^ $X_j = K$

XOR 연산의 특징인 $a$ ^ $a = 0$ 을 생각하면 이해가 될 것이다.

따라서 $X_j = X_{i-1}$ ^ $K$ 이므로 새로운 $j$가 들어올 때마다 이 식을 만족하는 $i-1$의 개수를 찾아주면 된다.

당연히 완전탐색으로 찾으면 큰일나고 cnt 배열을 만들어서 관리해줘야 한다.

$[l, r]$ 이 바뀌면 삽입되거나 삭제된 값을 cnt에도 업데이트 해줘야 한다.

대강 이렇게 생각하고 작성했더니 몇번 트라이 끝에 맞았다.

여담이지만 #define endl '\n' 이랑 FASTIO 안 쓰고 제출했다가 계속 TLE 났다...
항상 확인하도록 하자.

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

#define lint long long

int N, K;
int Q;
lint cnt[1100005];
lint arr[100005];

struct Query{
	int l, r;
	int idx;
};

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);

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

const int SIZE_PER_BUCKET = 300;
const int BUCKET_SIZE = 1111111/SIZE_PER_BUCKET + 20;

bool _cmp(Query a, Query b){
	if (a.l/SIZE_PER_BUCKET != b.l/SIZE_PER_BUCKET)
		return a.l/SIZE_PER_BUCKET < b.l/SIZE_PER_BUCKET;
	return a.r < b.r;
}

vector<Query> q;
lint ans[100005];

int main(){
	FASTIO;
	cin >> N >> K;
	for (int i = 1; i <= N; i++){
		cin >> arr[i];
	}
	//prefix xor
	for (int i = 2; i <= N; i++) arr[i] ^= arr[i-1];
	
	cin >> Q;
	
	for (int i = 0; i < Q; i++){
		int a, b; cin >> a >> b;
		q.push_back({a-1, b, i});
	}
	sort(q.begin(), q.end(), _cmp);
	
	int lp = q[0].l, rp = lp-1;
	lint sum = 0;
	
	for (int i = 0; i < Q; i++){
		int l = q[i].l; int r = q[i].r;
		int idx = q[i].idx;
		
		while (rp < r){
			rp++;
			sum += cnt[K ^ arr[rp]];
			cnt[arr[rp]]++;
		}
		
		while (l < lp){
			lp--;
			sum += cnt[K ^ arr[lp]];
			cnt[arr[lp]]++;
		}
		
		while (rp > r){
			cnt[arr[rp]]--;
			sum -= cnt[K ^ arr[rp]];
			rp--;
		}
		
		while (lp < l){
			cnt[arr[lp]]--;
			sum -= cnt[K ^ arr[lp]];
			lp++;
		}
		
		ans[idx] = sum;
	}
	
	for (int i = 0; i < Q; i++){
		cout << ans[i] << endl;
	}
	
}