unordered_map이 PS하는 블로그

Lazy propagation을 여러 가지 쿼리를 통해 전파하는 경우 어떤 것을 먼저 전파할지 결정하는 것이 매우 중요하다. 하지만 이 문제에서는 3개의 쿼리가 어떤 하나의 쿼리의 일부가 된다. 이를 인지하면 구현량도 많이 줄일 수 있어 실수도 덜 나오고 빠르게 풀 수 있다. 그리고 이 문제가 D5가 박혀있지만 플래 기여가 상당히 많고, 이제 플래로 내려올 때가 된 것 같다. D5 티어에 쫄지 말고 아이디어를 잡기 위해 노력해보자. 문제 요약 길이 10만 이하의 수열 A에 대해 다음 4가지 쿼리를 수행한다. 1 x y v : 구간 [x, y]에 속한 모든 i에 대해 A[i]=(A[i]+v)%MOD 적용 2 x y v : 구간 [x, y]에 속한 모든 i에 대해 A[i]=(A[i]*v)%MOD 적용 3 x..

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