fenwick tree
-
[BOJ] 16979 수열과 쿼리 23PS/BOJ 2020. 9. 12. 18:18
https://www.acmicpc.net/problem/16979 16979번: 수열과 쿼리 23 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. s e: s ≤ i Aj인 (i, j) 쌍의 개수를 출력한다. (1 ≤ s ≤ e ≤ N) www.acmicpc.net 알고리즘: Mo's, Fenwick tree 시간복잡도: $O((N+M)\sqrt NlogN)$ Mo's로 해결하였다. $A_i>A_j$를 구하는 것이므로, $A_i$를 왼쪽에서 추가 혹은 삭제를 할 때는 $A_i$보다 작은 원소의 개수를 더해주거나 빼주고, $A_i$를 오른쪽에서 추가 혹은 삭제를 할 때는 $A_i$보다 큰 원소의 개수를 더해주거나..
-
[BOJ] 13553 수열과 쿼리 8PS/BOJ 2020. 9. 7. 23:28
https://www.acmicpc.net/problem/13553 13553번: 수열과 쿼리 8 길이가 N인 수열 A1, A2, ..., AN과 정수 K가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. l r: l ≤ i < j ≤ r이면서 abs(Ai - Aj) ≤ K인 (i, j) 쌍의 개수를 출력한다. www.acmicpc.net 알고리즘: 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$의 개수를 더해주거나 빼주면 된다. 특정 범위를 만족하는 수의 개수를 구하..