BOJ 17353. 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

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

17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

문제를 간단하게 말하자면,

쿼리 1: [l, r] 구간의 원소에 각각 1, 2, ..., r-l+1을 더한다.

쿼리 2: x번 원소를 출력한다.

 

 

풀이 1: sqrt decomposition

내가 처음 생각해낸 풀이이다. 우선 전체 array를 sqrt(MAX_N)크기의 bucket 여러개로 나누자. bucket의 모든 자리는 num(현재 값), add(이 자리에서부터 시작해서 bucket끝까지 모든 자리에 add를 더해야 한다), step(이 자리에서부터 bucket끝까지 step, 2step, 3step...을 더해야 한다)를 저장한다. 즉 add와 step는 num을 update할 정보를 lazy하게 가지고 있다.

이제 두 쿼리는 아래와 같다.

update: add와 step을 잘 업데이트한다. 마지막 버킷 빼고는 버킷당 한 자리만 업데이트해주면 된다. (마지막 버킷은 두 자리)

query: add와 step을 이용해 bucket하나를 잘 update한다.(lazy한 정보를 참고하면서) 해당 bucket을 처음부터 끝까지 linear하게 훑으면 된다.

소스 링크: https://www.acmicpc.net/source/14114141

 

 

풀이 2: Fenwick

풀고 난 후 더 좋은 풀이가 없나 찾아보다가 발견했다. TAMREF님의 소스를 참고했다. https://www.acmicpc.net/source/14088580

이렇게 이해하면 될 거 같다. 쿼리된 점을 x라 하자. 문제의 쿼리는 아래와 같은 정보가 있으면 답변할 수 있다.

1. x가 몇 개의 update안에 포함되어 있는가? 모든 update가 [1, r]꼴이였으면, 이 문제의 답*x가 최종 답이다. 이렇게 답변할 경우 실제 답보다 큰 숫자를 답변하게 되는데, 정확히는 update하나당 (그 update의 시작점 - 1)만큼 큰 숫자이다. 이걸 알고 있으면 답변을 정확히 보정할 수 있다.

2. x가 포함되어 있는 update들의 (시작점-1)의 합.

1번과 2번 정보 각각 펜윅트리 하나를 이용해 로그 시간에 업데이트하고 쿼리할 수 있다. 구간의 시작점에 플러스 연산, 끝점에 마이너스 연산을 하는식으로 하면 된다.

 

좀 더 추상화를 해 보자면, 이 문제의 update는 대애충 (y=x-l)라는 함수의 특정 구간을 a[x]에 더한다고 생각할 수 있는데, 이런 함수 여러개를 더하면 y=ax+b꼴이 될거고, 풀이 2부분의 1번 정보는 a(기울기)를 알려주고, 2번 정보는 b(상수항)을 알려준다고 생각하면 될거같다.