unordered_map이 PS하는 블로그

수열과 쿼리 3 문제는 머지 소트 트리를 이용해 해결할 수 있다. 아직 안 풀어봤다면 수열과 쿼리 3을 꼭 먼저 풀고, 수열과 쿼리 18에서 업데이트 쿼리를 어떻게 적용할 수 있을지 생각해보자. 여담으로, 이 문제는 수열과 쿼리 1.5와 완전히 같은 문제이다. 문제 요약 길이 10만 이하의 수열 A에서 다음 2가지 쿼리를 수행한다. 1 i j k : 구간 [i, j]에서 A의 원소 중 k보다 큰 것의 개수를 출력 2 i k : A[i]=k로 업데이트 사용 알고리즘 제곱근 분할법 풀이 k보다 큰 원소의 수를 lower_bound나 upper_bound를 이용하여 구하겠다는 발상까지는 머지 소트 트리와 같다. 하지만 업데이트 쿼리가 들어온다면 기존의 머지 소트 트리에서 O(logN)개의 정렬된 vector를..

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

수열에서 XOR 쿼리를 처리할 때 많이 사용하는 테크닉으로, 알아두면 좋다. 이 방법에 대해 조금 더 연습하고 싶다면 https://www.acmicpc.net/problem/20919 문제도 추천한다. 수열과 쿼리 20이 P2, 소개한 20919 문제가 P3로 되어있는데, 개인적으로 이 문제가 20919의 하위호환이라고 느껴 이 문제에는 P4를 기여했다. 그만큼 어려운 문제가 아니니 상위 플래 티어를 보고 쫄지 말고 스스로 고민하여 풀어보자. 문제 요약 0이 하나 포함되어 있는 배열 A에 다음 쿼리들을 20만 번 이하로 수행한다. 1 x : A에 x를 추가 2 x : A에 x를 제거(여러 개 있으면 하나만 제거) 3 x : A의 원소 A[i]들 중에서 A[i]^x의 최댓값을 출력 사용 알고리즘 트라이를..

수열과 쿼리 1과 정확히 같은 문제이지만 쿼리 정렬을 할 수 없다는 점만 다르다. 머지 소트 트리를 필수적으로 구현해야하는 문제이다. 수열과 쿼리 1을 머지 소트 트리로 풀었다면 그대로 제출하면 된다. 따라서 별도의 풀이는 적지 않고, 아래에 수열과 쿼리 1 풀이 링크를 걸어두겠다. 아직 수열과 쿼리 1을 풀지 못했다면 쿼리 정렬을 사용해서는 어떻게 풀 수 있는지 고민해보기 바란다. 수열과 쿼리 1 풀이링크 https://unorderedmap.tistory.com/23 수열과 쿼리 1 [BOJ 13537] 수쿼 시리즈의 화려한 도약을 알리는 매우 재미있는 문제이다. 머지 소트 트리 기본 문제이면서도, 이 문제는 머지 소트 트리 외에 별해가 존재한다. 개인적으로 별해의 아이디어가 상당히 의미 unorde..

수쿼 시리즈의 화려한 도약을 알리는 매우 재미있는 문제이다. 머지 소트 트리 기본 문제이면서도, 이 문제는 머지 소트 트리 외에 별해가 존재한다. 개인적으로 별해의 아이디어가 상당히 의미 있다고 생각한다. 아래 풀이에 별해와 관련된 내용은 모두 가려놓았으니, 최소 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

금광 세그를 연습하기에 매우 좋은 문제이다. 개인적으로 처음에는 아이디어 떠올리는 것이 어려웠기 때문에 풀이를 조금 읽다가 아이디어가 잡히면 남은 풀이는 혼자 완성해보는 것을 추천한다. 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. x1 y1 x2 y2 : 구간 [x1, y1]에 속하는 모든 i와 구간 [x2, y2]에 속하는 모든 j(>=i)에 대해서 수열의 [i, j] 구간합의 최댓값을 출력한다. 사용 알고리즘 금광 세그 풀이 금광 세그를 구현하면 임의의 구간 [i, j]에서 수열의 prefix 최대합, suffix 최대합, 부분 최대 합, 전체 합을 O(logN)에 구할 수 있다. 각 값을 구간의 left, right, ans, all이라고 하자. ① [x1, y1]과 [x2, ..

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

레이지 세그를 구현할 수 있는지를 테스트하는 문제이다. 문제 요약 길이 10만 이하의 수열 A에서 다음 2가지 쿼리를 처리한다. 1 i j k : 수열 A의 구간 [i, j]에 k를 더한다. 2 x : A[x]를 출력한다. 사용 알고리즘 Lazy propagation을 이용한 세그먼트 트리 풀이 Lazy propagation을 이용한 세그먼트 트리를 그대로 구현해주면 된다. 나도 처음에는 구현하기 힘들었는데, 구현이 힘들어도 너무 좌절하지 말고 계속 구현해보는 것을 추천한다. 초반에는 다른 사람의 코드를 거의 따라치다시피 해도 좋으니 정상적으로 작동하는 코드를 완성하는 것에 의의를 두는 것이 좋다. 한 번 이해하기 시작하면 활용도가 매우 높아 PS할 때 많은 도움이 된다. 코드 더보기 더보기 #inclu..

세그먼트 트리 기초 문제이다. 이 문제를 보고 풀이를 떠올리지 못했다면 세그먼트 트리에 대한 기초를 다시 공부하기를 추천한다. 문제 요약 길이 10만 이하의 수열 A에서 3가지 쿼리를 수행한다. 1 i x : A[i]를 x로 update 2 l r : 구간 [l, r]에 존재하는 A[i] 중 짝수의 개수 출력 3 l r : 구간 [l, r]에 존재하는 A[i] 중 홀수의 개수 출력 사용 알고리즘 세그먼트 트리 풀이 2번 쿼리와 3번 쿼리 중 하나만 해결하면 나머지 쿼리도 해결할 수 있다. 홀수의 개수를 알면 구간에 있는 전체 수의 개수에서 홀수의 개수를 빼서 짝수의 개수를 계산할 수 있기 때문이다. 우리가 알아야하는 것은 구간에 존재하는 '홀수의 개수'의 구간합이기 때문에, 각 수를 2로 나눈 나머지를 ..