unordered_map이 PS하는 블로그

세그먼트 트리 응용을 막 시작한 사람들에게 추천하는 문제이다. 세그먼트 트리 배우고 얼마 지나지 않아서는 최댓값/최솟값/구간 합 말고는 세그먼트 트리를 떠올리기 어려운데, 더 심화된 응용의 세그먼트 트리를 쓰려면 이런 간단한 응용들로부터 시작하여야 한다고 생각한다. 문제 요약 길이 10만 이하의 수열 A에서 2가지 쿼리를 수행한다. 1 i v : A[i]를 v로 바꾼다 2 l r : l1; init(l,mid,node

이 문제는 내가 N달 동안 고민한 문제로, 자구충이라면 다4 수쿼 정도는 풀 수 있어야하지 않을까 싶어서 업솔빙도 안했다. 그리고 최근에 다시 고민을 하다가 문제를 푸는데에 핵심적인 아이디어를 떠올려 풀 수 있게 되었다. vector의 몇 안되는 다이아 이상 자력솔 중 하나이다. 문제 요약 길이 10만 이하의 수열 A, B에서 다음 쿼리를 수행한다. i j k : i

https://unorderedmap.tistory.com/12 수열과 쿼리 16 [BOJ 14428] https://unorderedmap.tistory.com/11 수열과 쿼리 15 [BOJ 14427] 오늘부터 1일 1수쿼 도전을 하려고 한다. 안 풀었던 수열과 쿼리 문제 중 하나를 풀거나, 푼 수열과 쿼리 문제 중 하나의 풀이를 작성하는 것 unorderedmap.tistory.com 수열과 쿼리 15, 16과 거의 같은 문제이다. 단, 최솟값의 인덱스가 아니라 최솟값만을 구한다는 점에서 조금 다르다. 문제 요약 길이 10만 이하의 수열에서 2가지 쿼리를 수행한다. 1 i v : i번째 값을 v로 바꾼다. 2 i j : 수열의 i번째 원소부터 j번째 원소까지 중에서 최솟값을 출력한다. https:..

https://unorderedmap.tistory.com/11 수열과 쿼리 15 [BOJ 14427] 오늘부터 1일 1수쿼 도전을 하려고 한다. 안 풀었던 수열과 쿼리 문제 중 하나를 풀거나, 푼 수열과 쿼리 문제 중 하나의 풀이를 작성하는 것 중 하나를 매일 할 것이다. (할 수 있을까...?) 문제 요 unorderedmap.tistory.com 수열과 쿼리 15와 거의 같은 문제이나, 조건 하나가 추가되었다. 문제 요약 길이 10만 이하의 수열에서 2가지 쿼리를 수행한다. 1 i v : i번째 값을 v로 바꾼다. 2 i j : 수열의 i번째 원소부터 j번 원소까지 중에서 가장 작은 값을 가지는 인덱스를 출력한다. 단, 최솟값이 여러 개일 경우 가장 작은 인덱스를 출력한다. https://www.a..

오늘부터 1일 1수쿼 도전을 하려고 한다. 안 풀었던 수열과 쿼리 문제 중 하나를 풀거나, 푼 수열과 쿼리 문제 중 하나의 풀이를 작성하는 것 중 하나를 매일 할 것이다. (할 수 있을까...?) 문제 요약 길이 10만 이하의 수열에서 2가지 쿼리를 수행한다. 1 i v : i번째 값을 v로 바꾼다. 2 : 수열에서 가장 작은 값을 가지는 인덱스를 출력한다. 단, 최솟값이 여러 개일 경우 가장 작은 인덱스를 출력한다. https://www.acmicpc.net/problem/14427 사용 알고리즘 세그먼트 트리 풀이 pair을 담는 세그먼트 트리를 잡자. first에는 해당 구간의 최솟값, second에는 해당 구간에서 최솟값을 가지는 가장 작은 인덱스를 저장한다. pair은 크기 비교 시 first가..