unordered_map이 PS하는 블로그

수열과 쿼리 8, 9와 함께 풀면 좋은 문제이다. 아직 안 풀었다면 함께 풀어보는 것을 추천한다. 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. s e : 구간 [s, e]에 존재하는 iAj인 (i, j) 쌍의 수를 출력 사용 알고리즘 펜윅 트리 Mo's Algorithm 풀이 어떤 수열에 대해 쿼리 1 N을 처리해보자. 이를 처리하는 것은 어렵지 않다. 처음 원소부터 하나씩 세그먼트 트리에 넣으면서, 이미 들어간 원소 중 자신보다 큰 원소의 수를 쿼리로 세주면 된다. 시간복잡도는 O(NlogN)이다. 이를 통해 우리는 쿼리를 처리하기 위해서 어떤 구간의 모든 수를 담고 있는 세그먼트 트리가 있어야한다는 사실을 알 수 있다. 그렇다면 이를 Mo's Algorithm으로 쿼리와 쿼리 사..

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

Mo's Algorithm과 세그먼트 트리가 완전히 체화되어 있다면 쉽게 풀 수 있는 문제이지만, 그게 아니라면 아이디어를 떠올리기 조금 힘들다. 그래서 별 다른 아이디어 없이도 P1의 티어를 받은 것 같다. 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. l r : 구간 [l, r]에 있는 i, j(i

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