[BOJ] 13537 수열과 쿼리 1

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

13537번: 수열과 쿼리 1

 

알고리즘: Segment tree, Offline query

 

시간복잡도: $O((N+M)logN+MlogM)$

---

접근:

1. 구간 쿼리 및 많은 쿼리 개수 : Segment tree

 

2. $A_i$의 값을 변경하는 쿼리가 없다

->

$A_i$에 대한 정보를 segment tree에 한번 넣어주고 나면,

그 뒤에는 $A_i$에 대해 신경 쓸 필요가 없다.

 

3. 쿼리의 순서를 바꿔도 상관없다

->

만약 쿼리의 순서가 결과에 영향을 끼치지 않으면,

쿼리의 순서를 바꿔주는 것 만으로도 답을 쉽게 얻을 수 있다.

이를 offline query라고 한다.

 

반대로 쿼리의 순서가 결과에 영향을 미치면, 이를 online query라고 한다.

관련 문제: BOJ 13544 (수열과 쿼리 3)

---

이 문제에서 구하고 싶은 것은 구간 [l, r]에서 k보다 큰 원소의 개수를 구하는 것이다.

 

특정 구간 내 원소의 개수를 구하는 segment tree를 생각해보자.

ex) $query(l, r)=\sum_{i=l}^r a_i\quad (a_i=0\ or\ 1)$

($a_i=1$이라는 것은 해당 index에 원소가 존재한다는 것이다.)

 

그리고 query를 k에 대한 내림차순으로 정렬한 다음,

$k<A_i$를 만족하는 $a_i$들을 차례대로 1로 갱신시켜주면,

매 쿼리마다 $O(logN)$의 시간복잡도로 k보다 큰 원소의 개수를 구해줄 수 있다.

 

ex) 문제의 예제

$A=\{ 5,1,2,3,4\}$

$a=\{ 0,0,0,0,0\}$ (초기 상태)

 

쿼리 (k 내림차순으로 정렬):

4 4 4 

1 5 2

2 4 1

 

1. 4 4 4

$A_i>4$

 

 

 

 

 

 

 

 

 

[4, 4] 원소 개수 = 0

 

2. 1 5 2

$A_i>2$

 

 

 

 

 

 

 

 

 

[1, 5] 원소 개수 = 3

 

3. 2 4 1

$A_i>1$

 

 

 

 

 

 

 

 

 

 

[2, 4] 원소 개수 = 0+2 = 2

 

---

 

	// 13537: 수열과 쿼리 1
	// Offline query
	#include<iostream>
	#include<algorithm>
	using namespace std;
	struct Q
	{
	int l, r, k, idx;
	bool operator<(const Q &a) const
	{
	return this->k > a.k;
	}
	}q[100001];
	struct A
	{
	int v, idx;
	bool operator<(const A &a) const
	{
	return this->v < a.v;
	}
	}a[100001];
	int N, M, ans[100001], tree_size = 1;
	int tree[1<<18];
	void updateST(int idx)
	{
	idx += tree_size;
	while (idx >= 1)
	{
	tree[idx]++;
	idx >>= 1;
	}
	}
	int getCnt(int l, int r)
	{
	int cnt = 0;
	l += tree_size, r += tree_size;
	while (l <= r)
	{
	if (l & 1) cnt += tree[l++];
	if (~r & 1) cnt += tree[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)
	{
	cin >> a[i].v;
	a[i].idx = i;
	}
	sort(a, a+N);
	cin >> M;
	for (int i = 0; i < M; ++i)
	{
	cin >> q[i].l >> q[i].r >> q[i].k;
	q[i].idx = i;
	}
	sort(q, q+M);
	int p, s = N-1;
	A tmp;
	tmp.idx = 0;
	for (int i = 0; i < M; ++i)
	{
	tmp.v = q[i].k;
	p = upper_bound(a, a+s+1, tmp) - a;
	for (int j = s; j >= p; --j)
	updateST(a[j].idx);
	s = p-1;
	ans[q[i].idx] = getCnt(q[i].l-1, q[i].r-1);
	}
	for (int i = 0; i < M; ++i)
	cout << ans[i] << "\n";
	return 0;
	}

view raw BOJ_13537.cpp hosted with ❤ by GitHub