돌이 코딩하는 방

문제 링크 : www.acmicpc.net/problem/5916 문제 태그 더보기 HLD ,segment tree lazy propagation 문제 풀이 문제를 보자... 1번 트리다. 2번 쿼리가 주어진다. 3번 그 쿼리가 경로 쿼리이다.... 아무리 봐도 이 문제는 HLD를 사용하는 문제라고 밖에는 생각이 들지 않는다. 경로에 모두 하나씩 심기 때문에 segment tree part에서 lazy propagation을 같이 섞어주면 문제를 해결할 수 있을 것 처럼 보인다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 4..

문제 링크 : https://www.acmicpc.net/problem/1395 문제 태그 더보기 Segment Tree Lazy Propagation 문제 풀이 문제를 보자. 거의 Segment Tree Lazy Propagation 연습문제라고 해도 될 정도로 기본적인 연산을 요구하고 있다. 구간의 값을 바꾸는 연산과 구간의 값을 구하는 연산. 값을 바꾸는 연산은 구간 내의 1을 모두 0으로 바꾸고 0을 모두 1로 바꾸는 연산이다. 이때 기존의 s~e 구간을 담당하고 있는 구간의 값이 val이라면 연산을 한 후 새로운 값은 e-s+1-val 로 쉽게 구할 수 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2..

문제 태그 : https://www.acmicpc.net/problem/13925 문제 소개 x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y) x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y) x y v: Ai = v를 수행한다. (x ≤ i ≤ y) x y: (ΣAi) % MOD를 출력한다. (x ≤ i ≤ y) 의 4가지 쿼리를 처리해야하는 문제이다. 문제 풀이 일단 이런식으로 처리하는데에 있어 기본적으로 lazy segment tree를 생각할 수 있다. 하지만 여기서 lazy하게 처리하는 과정에서 걸리는 부분이 있다. 기존의 lazy 방식은 최대한 미루고 나중에 처리해 주는 방식이다. 따라서 한 노드에 처리해 주어야 할 양이 쌓이기도..

이 글은 Segment Tree에 대한 이해가 어느정도 완벽히 되어있다고 가정하고 쓰는 글입니다. Top-Down 방식으로 구현이 되며, Top-Down 세그트리에 대한 이해가 부족하면 이 글을 먼저 읽는 것을 추천합니다. 예제 - 구간 합 구하기 2 링크는 https://www.acmicpc.net/problem/10999 이다. 이번에도 문제에 대해서 이야기 하면서 Lazy Propagation에 대해서 소개해보려고 한다. 이 문제에서 요구하는 사항은 두 가지 이다. 1. 배열 중 구간에 일정 값을 더한다 2. 배열의 구간의 합을 구한다. Segment Tree를 생각해보자. 2번 쿼리는 기존 Segment Tree에 존재하는 기능이다. 하지만 여기서 문제가 되는 것은 1번 쿼리이다. 기존의 방식으로..

문제 태그 : https://www.acmicpc.net/problem/17955 나한테 잘 맞는 문제였다. 정말 좋은 문제라고 생각한다. 문제 소개 n,m이 주어진다. 이후 1 이상 m 이하의 수 n개가 주어진다. n개의 숫자는 원형으로 이루어져 있다. 이후 2가지 행동을 할 수 있다. 1. 어떤 한 칸을 골라 그 수를 max(원래 숫자, 왼쪽의 숫자, 오른쪽 숫자)로 바꾼다. 2. 어떤 한 칸을 골라 그 수를 min(원래 숫자, 왼쪽의 숫자, 오른쪽 숫자)로 바꾼다. 원형으로 이루어진 n개의 숫자를 모두 (1,2,3,...m)으로 만드는데 필요한 최소 행동의 횟수를 각각 구하시오. 만약 만들 수 없다면 -1을 출력한다. 문제 풀이 스포 주의! Step1. 문제 관찰 문제의 예제를 봄으로써 몇가지 사실..