segment tree
-
[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] 13547 수열과 쿼리 5PS/BOJ 2020. 8. 31. 00:34
https://www.acmicpc.net/problem/13547 13547번: 수열과 쿼리 5 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력한다. www.acmicpc.net 알고리즘: Merge sort tree 시간복잡도: $O(NlogN+Mlog^2N)$ 접근: [l, r] 구간에 속하는 $A_i$ 중 서로 다른 수의 개수를 구하는 문제이다. 매 쿼리마다 [l, r] 을 모두 살펴보면 $O(MN)$으로 TLE를 받게 된다. 따라서, 어떻게 하면 중복되는 $A_i$들의 값을 걸러낼 수 있을지 생각해봐야한다. 당연히 $A_i$의 값 그대로 세그먼트 트리에 ..
-
[BOJ] 16978 수열과 쿼리 22PS/BOJ 2020. 8. 24. 20:32
https://www.acmicpc.net/problem/16978 16978번: 수열과 쿼리 22 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v: Ai = v로 변경한다. 2 k i j: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다. www.acmicpc.net 알고리즘: Segment tree, Offline query 시간복잡도: $O((N+M)logN+MlogM)$ 접근: 2번 쿼리를 보면, 'k번째 1번 쿼리까지 적용되었을 때' 라는 문구를 볼 수 있다. 이걸 보면 쿼리들을 k 순서로 정렬하는 offline query를 쓰면 되겠구나 라고 생각할 수 있다. 쿼리들을 k에 대한 오름..
-
[BOJ] 16975 수열과 쿼리 21PS/BOJ 2020. 8. 24. 20:22
https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 알고리즘: Segment tree 시간복잡도: $O(MlogN)$ 접근: 이 문제는 분류를 보니 lazy propagation에 속해있던데 굳이 쓰지 않아도 쉽게 풀리는 문제다. 쿼리가 구간에 대해 묻는게 아니라 단순히 $A_x$를 출력하는거라서... [l, r]에 k를 더하는 것을 segment tree에서 [l, r] 구간을 대표하는 노드에 k 값을 더해준 후, $A_x$ ..
-
[BOJ] 수열과 쿼리 3PS/BOJ 2020. 8. 23. 23:36
https://www.acmicpc.net/problem/13544 13544번: 수열과 쿼리 3 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 알고리즘: Merge sort tree 시간 복잡도: $O(NlogN+Mlog^2N)$ 얼핏 봤을 때는 수열과 쿼리 1과 동일한 문제인 것 같지만 이전 쿼리의 결과 값으로 쿼리를 만들어야 한다. l = a^last_ans r = b^last_ans k = c^last_ans 처럼 (a, b, c)가 입력으로 주어지면 이전 결과 값과 XOR을 하여 (l, r, k)..
-
[BOJ] 13537 수열과 쿼리 1PS/BOJ 2020. 8. 23. 23:15
https://www.acmicpc.net/problem/13537 13537번: 수열과 쿼리 1 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 알고리즘: Segment tree, Offline query 시간복잡도: $O((N+M)logN+MlogM)$ 접근: 1. 구간 쿼리 및 많은 쿼리 개수 : Segment tree 2. $A_i$의 값을 변경하는 쿼리가 없다 -> $A_i$에 대한 정보를 segment tree에 한번 넣어주고 나면, 그 뒤에는 $A_i$에 대해 신경 쓸 필요가 없다. 3. 쿼리의..
-
[ BOJ] 18436 수열과 쿼리 37PS/BOJ 2020. 8. 23. 20:03
https://www.acmicpc.net/problem/18436 18436번: 수열과 쿼리 37 길이가 N인 수열 A1, A2, ..., AN이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i x: Ai를 x로 바꾼다. 2 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 짝수의 개수를 출력한다. 3 l r: l ≤ i ≤ www.acmicpc.net 알고리즘: Segment tree 시간복잡도: $O((N+M)logN)$ 접근: 1. 구간 쿼리 및 쿼리 개수 $(M\le 10^5)$ 정해진 구간 내의 짝수 및 홀수의 개수를 구하는 문제이다. $A_i$가 홀수이면 1, 짝수이면 0으로 segment tree의 리프 노드에 저장해두고, 부모 노드는 자식 노드들의 합으로 표현해주면 구..