-
[BOJ] 13545 수열과 쿼리 0, 13550 수열과 쿼리 7PS/BOJ 2020. 10. 23. 21:15
알고리즘: Mo's (+평방 분할)
시간복잡도: $O((N+M)\sqrt N)$
1. 수열과 쿼리 0
$A_i=-1\ or\ 1$
$S_i=A_1+A_2+...+A_i$ 라고 해보자 그러면,
$A_i+A_{i+1}+...+A_r= S_r-S_{i-1}$ 이다.
따라서, 이 문제는 $S_r=S_{i-1}$ 일 때, $max\{ r-i\}$를 구하는 문제로 바뀌게 된다.
수열과 쿼리 4와 동일한 문제이다.
Tip) 쿼리의 구간을 저장할 때 [l-1, r]로 저장해주면 코드가 깔끔해진다.
2. 수열과 쿼리 7
$S_i=(A_1+A_2+...+A_i)\ mod\ K$ 라고 하면,
$(A_i+A_{i+1}+...+A_r)\ mod\ K = S_r-S_{i-1}$ 이다.
따라서, 수열과 쿼리 0과 동일한 문제로 바뀐다.
'PS > BOJ' 카테고리의 다른 글
[BOJ] 단계별로 풀어보기 - 최단 경로 (0) 2021.06.15 [BOJ] 수열과 쿼리 13 (0) 2020.10.23 [BOJ] 13546 수열과 쿼리 4 (0) 2020.10.22 [BOJ] 16979 수열과 쿼리 23 (0) 2020.09.12 [BOJ] 13704 수열과 쿼리 11 (0) 2020.09.12