[BOJ] 수열과 쿼리 3

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

13544번: 수열과 쿼리 3

알고리즘: Merge sort tree

 

시간 복잡도: $O(NlogN+Mlog^2N)$

---

얼핏 봤을 때는 수열과 쿼리 1과 동일한 문제인 것 같지만

이전 쿼리의 결과 값으로 쿼리를 만들어야 한다.

l = a^last_ans

r = b^last_ans

k = c^last_ans

처럼 (a, b, c)가 입력으로 주어지면 이전 결과 값과 XOR을 하여 (l, r, k) 값을 구해야 한다.

 

따라서 앞에서 사용했던 offline query 기법을 사용할 수는 없다.

 

---

지금까지 segment tree는 각 노드에 하나의 값을 저장했고 이를 이용해 각종 쿼리를 처리하였다.

이 선입견에서 벗어나서, 각 노드에 여러 값을 저장해주면 이번 문제를 쉽게 해결할 수 있다.

 

 

이번에는, 각 노드에 하나의 값이 아닌 해당 구간에 속하는 모든 $A_i$의 값이 정렬시켜 저장해보자

그럼 아래 그림과 같이 segment tree가 만들어질 것이다.

 

그럼 [l, r] 구간 내 k보다 큰 원소의 개수는, 해당하는 노드에서 upper_bound 함수를 사용하여 구할 수 있다.

 

예를 들어, [2, 5]에서 2보다 큰 원소의 개수를 구해보려면,

 

 

 

 

 

 

 

 

 

 

 

색칠된 노드에서 upper_bound를 사용하여 0 + 1 + 1 = 2 라는 값을 구해낼 수 있다.

 

 

이러한 자료구조를 merge sort tree 라고 부른다고 한다. (solved.ac tag명을 보아하니)

 

 

	// 13544: 수열과 쿼리 3
	#include<iostream>
	#include<algorithm>
	#include<vector>
	using namespace std;
	int N, M, a, u, v, k, tree_size = 1, last_ans;
	vector<int> tree[1<<18];
	void updateST(int idx, int val)
	{
	idx += tree_size;
	tree[idx].push_back(val);
	while (idx > 1)
	{
	idx >>= 1;
	tree[idx].push_back(val);
	}
	}
	int num_overK(int l, int r)
	{
	int ans = 0;
	l += tree_size, r += tree_size;
	while (l <= r)
	{
	if (l & 1)
	{
	ans += tree[l].end() - upper_bound(tree[l].begin(), tree[l].end(), k);
	l++;
	}
	if (~r & 1)
	{
	ans += tree[r].end() - upper_bound(tree[r].begin(), tree[r].end(), k);
	r--;
	}
	l >>= 1, r >>= 1;
	}
	return ans;
	}
	int main()
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N;
	while (tree_size < N) tree_size <<= 1;
	for (int i = 0; i < N; ++i)
	{
	cin >> a;
	updateST(i, a);
	}
	cin >> M;
	for (int i = 1; i <= tree_size; ++i)
	sort(tree[i].begin(), tree[i].end());
	while (M--)
	{
	cin >> u >> v >> k;
	u ^= last_ans;
	v ^= last_ans;
	k ^= last_ans;
	last_ans = num_overK(u-1, v-1);
	cout << last_ans << "\n";
	}
	return 0;
	}

view raw BOJ_13544.cpp hosted with ❤ by GitHub