[BOJ] 13545 수열과 쿼리 0, 13550 수열과 쿼리 7

PS/BOJ 2020. 10. 23. 21:15

13545번: 수열과 쿼리 0

1과 -1로만 이루어져 있는 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 합이 0이면서 가장 긴 연

www.acmicpc.net

13550번: 수열과 쿼리 7

길이가 N인 수열 A1, A2, ..., AN과 정수 K가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. l r: l ≤ i ≤ j ≤ r이면서 (Ai + Ai+1 + ...+ Aj) mod K = 0인 가장 긴 연속 부분 수열의 길이를

www.acmicpc.net

알고리즘: 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과 동일한 문제로 바뀐다.

코딩 코딩