unordered_map이 PS하는 블로그

수열에서 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로 나눈 나머지를 ..

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

멀다고 느꼈던 다이아2에 생각보다 금방 올라왔다. 2학년 2학기 때 내신을 챙기느라 PS를 거의 못하였고, 참고 있던 것들이 봇물 터지듯이 폭발하면서 종강 이후 미친듯이 PS를 했다. 물론 3학년 1학기 내신을 챙겨야할 시기이기 때문에 적당히 조절하고 있지만, 지금도 하루에 1시간~2시간 정도는 시간 내서 하려고 한다. 1월 1일~1월 9일 : 센트로이드 분할과 DnC Opt를 공부한 후 연습문제를 풀며 티어가 많이 올랐다. 당시 100문제 중 최저 티어가 P3이었는데, 센트로이드 분할 문제는 D5~D4, DnC Opt 문제는 P1 정도에 티어가 형성되어 있어 문제를 풀 때마다 레이팅이 올랐다. 그리고 CLASS 8을 따려는 마음은 없었는데, 어느새 14문제가 풀려 있어 6문제만 더 풀면 딸 수 있다는 ..