문제 링크
- http://icpc.me/16903
사용 알고리즘
- 모스 알고리즘
- 펜윅 트리
시간복잡도
- $O((N+Q) \sqrt N log N)$
풀이
$\vert A_i - A_j \vert ≤ K$ 라는 것은 $j-k ≤ i ≤ j+k$ 라는 것과 동일합니다.
업데이트가 없는 상황에서 구간의 어떤 값을 구하는 쿼리가 주어지기 때문에 모스 알고리즘을 생각해볼 수 있습니다.
모스 알고리즘은 구간의 양 끝에 어떤 수가 추가되거나 제거되는, 2가지 상황만 잘 처리해주면 됩니다.
어떤 수 x가 추가될 때는 이미 구간에 포함되어있는 수 중에서 $x-k ≤ y ≤ x+k$인 y의 개수를 정답에 더해주면 됩니다. 똑같은 방법으로 어떤 수 x가 제거될 때는 이미 구간에 포함되어있는 수 중에서 $x-k ≤ y ≤ x+k$인 y의 개수를 정답에서 빼주면 됩니다.
Fenwick Tree를 이용해 쉽게 처리할 수 있습니다.