-
[BOJ] 16979 수열과 쿼리 23PS/BOJ 2020. 9. 12. 18:18
https://www.acmicpc.net/problem/16979
알고리즘: Mo's, Fenwick tree
시간복잡도: $O((N+M)\sqrt NlogN)$
Mo's로 해결하였다.
$A_i>A_j$를 구하는 것이므로,
$A_i$를 왼쪽에서 추가 혹은 삭제를 할 때는 $A_i$보다 작은 원소의 개수를 더해주거나 빼주고,
$A_i$를 오른쪽에서 추가 혹은 삭제를 할 때는 $A_i$보다 큰 원소의 개수를 더해주거나 빼주었다.
특정 원소보다 크거나 작은 원소의 개수를 세는것은 segment tree로 해결이 가능하나,
저번에 상수 무시했다가 큰 코 다친적이 있어서 그냥 fenwick tree로 구현하였다.
Hilbert curve를 이용하면 딱히 뭘로 구현하든 딱히 상관없긴 하다.
'PS > BOJ' 카테고리의 다른 글
[BOJ] 13545 수열과 쿼리 0, 13550 수열과 쿼리 7 (0) 2020.10.23 [BOJ] 13546 수열과 쿼리 4 (0) 2020.10.22 [BOJ] 13704 수열과 쿼리 11 (0) 2020.09.12 [BOJ] 13557 수열과 쿼리 10 (0) 2020.09.12 [BOJ] 13553 수열과 쿼리 8 (0) 2020.09.07