[BOJ] 13553 수열과 쿼리 8

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

13553번: 수열과 쿼리 8

알고리즘: Mo's, Fenwick tree

 

시간복잡도: $O((N+M)\sqrt NlogN)$

---

$|A_i-A_j|\le K$를 풀어쓰면, $A_i-K\le A_j \le A_i+K$가 된다.

 

Mo's 로 접근해보면, $A_i$를 추가 및 삭제를 할 때 위 구간을 만족하는 $A_j$의 개수를 더해주거나 빼주면 된다.

특정 범위를 만족하는 수의 개수를 구하는 쿼리는 segment tree로 해결이 가능하다.

 

어차피 $A_i\le 10^5$으로 범위가 매우 작으므로 좌표 압축을 하지 않고,

$A_i$의 값을 index로 삼는 segment tree를 만들어 개수를 저장해주면 된다.

 

 

는... segment tree로 구현했다가 TLE를 받아버려서 좀 더 빠른 fenwick tree로 구현하여 통과하였다 (...)