[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

 

---