MO
-
[BOJ] 13545 수열과 쿼리 0, 13550 수열과 쿼리 7PS/BOJ 2020. 10. 23. 21:15
www.acmicpc.net/problem/13545 13545번: 수열과 쿼리 0 1과 -1로만 이루어져 있는 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 합이 0이면서 가장 긴 연 www.acmicpc.net www.acmicpc.net/problem/13550 13550번: 수열과 쿼리 7 길이가 N인 수열 A1, A2, ..., AN과 정수 K가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. l r: l ≤ i ≤ j ≤ r이면서 (Ai + Ai+1 + ...+ Aj) mod K = 0인 가장 긴 연속 부분 수열의 길이를 www.acmicpc.ne..
-
[BOJ] 13546 수열과 쿼리 4PS/BOJ 2020. 10. 22. 00:25
더보기 https://www.acmicpc.net/problem/13546 13546번: 수열과 쿼리 4 1보다 크거나 같고, K보다 작거나 같은 수로 이루어져 있는 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. l r: max{|x − y| : l ≤ x, y ≤ r and Ax = Ay www.acmicpc.net 알고리즘: Mo's (+ 평방 분할) 시간복잡도: $O((N+M)\sqrt N)$ Mo's 알고리즘과 관련된 문제들을 보면, 구간 [l, r]에서 특정 값이 몇 번 등장하는지를 구하는 문제들이 빈번히 등장한다. push $A_i$: cnt[$A_i$]++ pop $A_i$: cnt[$A_i$]-- 이런 방식으로 말이다. 이를 ..
-
[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] 13704 수열과 쿼리 11PS/BOJ 2020. 9. 12. 18:03
https://www.acmicpc.net/problem/13704 13704번: 수열과 쿼리 11 길이가 N인 수열 A1, A2, ..., AN과 정수 K가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. l r: l ≤ i ≤ j ≤ r이면서 Ai, Ai+1, ..., Aj를 XOR한 값이 K인 (i, j) 쌍의 개수를 출력한다. www.acmicpc.net 알고리즘: Mo's 시간복잡도: $O((N+M)\sqrt N)$ XOR 연산을 하는 문제다. 아래 두가지 관찰만 하면 쉽게 접근이 가능하다. 1. a ^ a = 0 : 자기 자신을 xor하면 0이 나옴 2. a ^ 0 = a : xor 0을 하면 자기 자신이 나옴 따라서 $a[i]=A_1$^$A_2$^...^$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$의 개수를 더해주거나 빼주면 된다. 특정 범위를 만족하는 수의 개수를 구하..
-
[BOJ] 13548 수열과 쿼리 6PS/BOJ 2020. 9. 7. 23:10
https://www.acmicpc.net/problem/13548 13548번: 수열과 쿼리 6 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 가장 많이 등장하는 수가 몇 번 등장했는지 출력한다. www.acmicpc.net 알고리즘: Mo's 시간복잡도: $O((N+M)\sqrt N)$ 모스 알고리즘을 배우면서 풀어본 문제이다. 모스 알고리즘을 이용하면 데이터를 추가 및 삭제를 하는데 $O(1)$ 만에 해결할 수 있고, 포인터 이동(?)을 하는데 최대 $(N+M)\sqrt N$이므로 제한 시간 내 해답을 구할 수 있다. 답을 구하는데 필요한 배열은 총 2개이다. 1. $cnt[x]:$ $A_i=..