unordered_map이 PS하는 블로그

수쿼 시리즈의 화려한 도약을 알리는 매우 재미있는 문제이다. 머지 소트 트리 기본 문제이면서도, 이 문제는 머지 소트 트리 외에 별해가 존재한다. 개인적으로 별해의 아이디어가 상당히 의미 있다고 생각한다. 아래 풀이에 별해와 관련된 내용은 모두 가려놓았으니, 최소 30분 정도는 별해에 대해 고민해보는 것을 추천한다. ** 수열과 쿼리 3 풀다가 오신 분들은 머지 소트 트리에 대한 풀이인 풀이 1만 읽으면 수열과 쿼리 3을 풀 수 있다. 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. i j k : 구간 [i, j]에서 k보다 큰 원소의 수를 출력한다. 사용 알고리즘 풀이 1) 머지 소트 트리 풀이 2) Hint : 오프라인 쿼리라는 점을 이용 더보기 스위핑 + 세그먼트 트리 풀이 풀이 ..

'쿼리를 정렬'한다는 것은 세그먼트 트리를 처음 배우는 입장에서 쉽게 떠올릴 수 있는 것은 아니다. 하지만 해당 문제처럼 쿼리의 순서가 무의미할 때나 업데이트가 없는 오프라인 쿼리일 때는 매우 자주 이용하며, Mo's Algorithm의 기둥 중 하나가 되기도 한다. 또한 퍼시스턴트 세그먼트 트리로 조금 더 어렵게 풀 수 있기 때문에 퍼시스턴트 세그먼트 트리를 처음 배우는 사람들에게도 매우 좋은 문제이다. 현재는 쿼리 정렬 풀이만 올려놓았는데, 나중에 기회가 되면 퍼시스턴트 세그먼트 트리를 이용한 풀이도 업로드할 예정이다. 문제 요약 길이 10만 이하의 수열 A에서 다음 2가지 쿼리를 수행한다. 1 i v : A[i]=v로 update 2 k i j : k번째 update 쿼리까지 적용되었을 때 수열 A..