수열과 쿼리
-
[BOJ] 수열과 쿼리 13PS/BOJ 2020. 10. 23. 22:43
www.acmicpc.net/problem/13925 13925번: 수열과 쿼리 13 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y) 2 x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y www.acmicpc.net 알고리즘: Segtree, Lazy propagation 시간복잡도: $O((N+M)logN)$ 1, 2번 쿼리를 보면 구간에 있는 모든 원소에 특정 값을 연산한다. 따라서, Lazy propatagion을 써야한다는 것을 알 수 있다.' 1, 2번 쿼리를 통해 $a\rightarrow ax+b$로 바꼈다고 생각해보..
-
[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] 13557 수열과 쿼리 10PS/BOJ 2020. 9. 12. 13:21
https://www.acmicpc.net/problem/13557 13557번: 수열과 쿼리 10 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. x1 y1 x2 y2: x1 ≤ i ≤ y1, x2 ≤ j ≤ y2, i ≤ j인 모든 (i, j)에 대해서 Ai + ... + Aj의 최댓값을 출력한다. www.acmicpc.net 알고리즘: Segment tree 시간복잡도: $O(N+MlogN)$ $A_i+...+A_j$의 최댓값을 구하는 것은 DP로 $O(N)$만에 해결이 가능하다. 다만 이 문제에선 주어지는 구간마다 최댓값을 구해줘야 한다. 쿼리 개수가 많으므로 $O(N)$이 아니라 그보다 더 빠른 시간안에 해결해야 한다. 따라서 seg..
-
[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=..
-
[BOJ] 16903 수열과 쿼리 20PS/BOJ 2020. 9. 7. 22:31
https://www.acmicpc.net/problem/16903 16903번: 수열과 쿼리 20 첫째 줄에 쿼리의 개수 M(1 ≤ M ≤ 200,000)이 주어진다. 둘째 줄부터 M개의 줄에 쿼리가 주어진다. 입력으로 주어지는 x의 범위는 109보다 작거나 같은 자연수이다. 3번 쿼리는 하나 이상 주어진다. www.acmicpc.net 알고리즘: Trie 시간복잡도: $O(Mlog10^9)$ 접근: M이 20만으로 꽤 크다. 따라서 매 쿼리마다 빠른 시간 안에(log) 해결해야한다. 여기서 주요 연산이 XOR 라는 것에 주목했다. 어차피 문제가 되는건 3번 쿼리다. (1, 2번은 단순 추가/삭제니...) A에 있는 모든 원소와 XOR 연산을 하고 최댓값을 구해야한다. 두가지 관찰만 하면 풀이에 쉽게 ..