[BOJ] 13547 수열과 쿼리 5

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

13547번: 수열과 쿼리 5

알고리즘: Merge sort tree

 

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

---

접근:

[l, r] 구간에 속하는 $A_i$ 중 서로 다른 수의 개수를 구하는 문제이다.

매 쿼리마다 [l, r] 을 모두 살펴보면 $O(MN)$으로 TLE를 받게 된다.

 

따라서, 어떻게 하면 중복되는 $A_i$들의 값을 걸러낼 수 있을지 생각해봐야한다.

 

당연히 $A_i$의 값 그대로 세그먼트 트리에 넣어버린다면 쿼리를 처리할 때,

중복 값을 찾아내는대만 $O(N)$이 걸리므로 다른 방식을 찾아봐야한다.

 

이 때 인덱스 값을 이용하면 $O(logN)$만에 서로 다른 수의 개수를 찾아낼 수 있다.

$A_i$의 인덱스 값(i)을 그대로 저장하는게 아닌, 다음에 나오는 같은 수의 인덱스 값을 저장하는게 핵심이다.

 

예제를 살펴보면,

1 1 2 1 3을 위 방식대로 다음에 나올 인덱스 값을 계산해보면, (편의상 다음에 같은 수가 안나오면 N+1로 계산했다)

2 4 6 6 6

이렇게 나온다.

 

여기서 [1, 5] 쿼리를 처리한다고 하면,

인덱스 값이 5이하인 수는 [1, 5] 안에 같은 수가 중복해서 나온다는 뜻이므로 6이상인 수들만 카운팅 해주면 된다. (3개)

 

[2, 4]는 5이상인 수를 카운팅 (2개)

[3, 5]는 6이상인 수를 카운팅 (3개)

 

따라서 [l, r]구간 안에 r+1 이상인 수를 찾는 문제로 바뀌게 되고,

이는 merge sort tree를 이용하여 매 쿼리마다 $O(logN)$으로 해결이 가능하다.

(수열과 쿼리3 문제와 비슷 https://www.acmicpc.net/problem/13544)

 

 

	// 13547: 수열과 쿼리 5
	#include<iostream>
	#include<algorithm>
	#include<unordered_map>
	#include<vector>
	using namespace std;
	int N, Q, a[100001], tree_size = 1, u, v;
	unordered_map<int, int> map;
	vector<int> tree[1<<18];
	int next_idx[100001];
	void updateST(int idx, int val)
	{
	idx += tree_size;
	while (idx >= 1)
	{
	tree[idx].push_back(val);
	idx >>= 1;
	}
	}
	int num_overK(int l, int r, int val)
	{
	int cnt = 0;
	l += tree_size, r += tree_size;
	while (l <= r)
	{
	if (l & 1)
	{
	cnt += tree[l].end() - upper_bound(tree[l].begin(), tree[l].end(), val);
	l++;
	}
	if (~r & 1)
	{
	cnt += tree[r].end() - upper_bound(tree[r].begin(), tree[r].end(), val);
	r--;
	}
	l >>= 1, r >>= 1;
	}
	return cnt;
	}
	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) // hashing
	{
	cin >> a[i];
	if (map.end() == map.find(a[i])) map[a[i]] = map.size();
	a[i] = map[a[i]];
	}
	for (int i = 0; i < map.size(); ++i) next_idx[i] = N;
	for (int i = N-1; i >= 0; --i)
	{
	int &t = next_idx[a[i]];
	updateST(i, t);
	t = i;
	}
	for (int i = 1; i < tree_size; ++i) sort(tree[i].begin(), tree[i].end());
	cin >> Q;
	while (Q--)
	{
	cin >> u >> v;
	cout << num_overK(u-1, v-1, v-1) << "\n";
	}
	return 0;
	}

view raw BOJ_13547.cpp hosted with ❤ by GitHub

 

 

 

 

---

알고보니, 이 문제는 오프라인 쿼리로 접근하여 Mo's 알고리즘으로도 $O((N+M)\sqrt{N} )$으로 해결이 가능하다