[BOJ] 13704 수열과 쿼리 11

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

13704번: 수열과 쿼리 11

알고리즘: Mo's

 

시간복잡도: $O((N+M)\sqrt N)$

 

---

XOR 연산을 하는 문제다.

아래 두가지 관찰만 하면 쉽게 접근이 가능하다.

 

1. a ^ a = 0 : 자기 자신을 xor하면 0이 나옴

2. a ^ 0 = a : xor 0을 하면 자기 자신이 나옴

 

따라서 $a[i]=A_1$^$A_2$^...^$A_i$ 로 두면,

$a[j]$^$a[i-1]=A_i$^$A_{i+1}$^...^$A_j$ 이다.

 

$a[j]$^$a[i-1]=K$를 정리하면,

$a[j]=K$^$a[i-1]$ 가 되므로

Mo's 로 접근하여 $a[j]$를 추가 및 제거를 할 때, $K$^$a[i-1]$의 개수를 더하거나 빼주면 된다.

 

 

query [l, r]의 구간을 [l-1, r]로 저장해주면 구현이 깔끔해진다.

 

 

	// 13704: 수열과 쿼리 11
	#include<iostream>
	#include<cmath>
	#include<algorithm>
	#include<utility>
	using namespace std;
	typedef long long ll;
	int N, M, K, l, r, a[100001];
	ll total_cnt, cnt[1050000], ans[100001];
	struct Q
	{
	int l, r, idx;
	ll d;
	bool operator < (const Q &a) const
	{
	return d < a.d;
	}
	}q[100001];
	ll convHilbert(int x, int y, int pow, int rotate)
	{
	if (!pow) return 0;
	int hpow = 1 << (pow - 1);
	int seg = (x < hpow) ? ((y < hpow)?0:3) : ((y < hpow)?1:2);
	seg = (seg + rotate) & 3;
	const int rotateDelta[4] = {3, 0, 0, 1};
	int nx = x & (x^hpow), ny = y & (y^hpow);
	int nrot = (rotate + rotateDelta[seg]) & 3;
	ll subSquareSize = (ll)1 << (2*pow - 2);
	ll ans = seg * subSquareSize;
	ll add = convHilbert(nx, ny, pow-1, nrot);
	ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
	return ans;
	}
	int main()
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N; ++i)
	{
	cin >> a[i];
	a[i] ^= a[i-1];
	}
	cin >> M;
	for (int i = 0; i < M; ++i)
	{
	cin >> q[i].l >> q[i].r;
	q[i].l--;
	q[i].idx = i;
	q[i].d = convHilbert(q[i].l, q[i].r, 17, 0);
	}
	sort(q, q+M);
	l = q[0].l;
	r = l - 1;
	for (int i = 0; i < M; ++i)
	{
	while (l < q[i].l)
	{
	cnt[a[l]]--;
	total_cnt -= cnt[K^a[l]];
	l++;
	}
	while (l > q[i].l)
	{
	l--;
	total_cnt += cnt[K^a[l]];
	cnt[a[l]]++;
	}
	while (r < q[i].r)
	{
	r++;
	total_cnt += cnt[K^a[r]];
	cnt[a[r]]++;
	}
	while (r > q[i].r)
	{
	cnt[a[r]]--;
	total_cnt -= cnt[K^a[r]];
	r--;
	}
	ans[q[i].idx] = total_cnt;
	}
	for (int i = 0; i < M; ++i)
	cout << ans[i] << "\n";
	return 0;
	}

view raw BOJ_13704.cpp hosted with ❤ by GitHub