반응형 offline query3 BOJ 13545 : 수열과 쿼리 0 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/13545 참고 - BOJ 2042 : 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) - 머지 소트 Merge Sort - BOJ 10866 : 덱 with Linked List - BOJ 13546 : 수열과 쿼리 4 수열과 쿼리 4에서 구해야하는 값은 아래와 같다. ● l r : max{|x - y| : l ≤ x, y ≤ r and Ax = Ay} 를 출력한다. 즉, 구간 [left, right]에서 같은 원소가 있는 경우 그 원소의 index의 차이가 가장 큰 값이다. 수열과 쿼리 0에서는 [left, right]에서 부분 수열 중 합이 0인 가장 긴 부분 수열의 길이를 구해야 한다. .. 2023. 2. 7. BOJ 13546 : 수열과 쿼리 4 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/13546 참고 - BOJ 2042 : 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) - 머지 소트 Merge Sort - BOJ 13547 : 수열과 쿼리 5 - BOJ 10866 : 덱 with Linked List 수열과 쿼리 5에서 사용한 방법으로 문제를 푼다. 여기서는 주어진 구간 [left, right]에서 값이 같은 원소의 index의 차이를 구한다. 제곱근 분할법으로 원소의 길이 저장하기 [left, right]를 Mo's로 한 칸씩 움직이면서 각 원소마다 가장 긴 길이를 갱신하면 된다. 예를 들어 5번 원소가 7번 구간에 존재하고, 이 원소가 추가된다면, 5번 덱에 index .. 2023. 2. 7. BOJ 13547 : 수열과 쿼리 5 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/13547 참고 - BOJ 2531, 15961 : 회전 초밥 - BOJ 2042 : 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) - 머지 소트 Merge Sort 원소의 개수 세기 구간에 업데이트가 없다면, 모스(Mo's) 알고리즘을 이용해 쿼리를 처리할 수 있다. 만약에 [left, right] 구간에 대한 답을 알고 있다면, [left, right ± 1]이나 [left ± 1, right]의 쿼리는 쉽게 처리할 수 있다. 즉, 이미 답을 구한 구간을 최대한 효율적으로 활용하는 방법이다. 위 문제는 회전 초밥에서 슬라이딩 윈도우를 사용했던 방법으로 원소의 개수를 셀 수 있다. 원소가 1.. 2023. 2. 7. 이전 1 다음 반응형
