Doby's Lab

https://www.acmicpc.net/problem/13925 13925번: 수열과 쿼리 13 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y) 2 x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y www.acmicpc.net 한 문제만 풀면 플레티넘이라서 멋지게 피날레를 장식하고 싶은 마음에 풀 수 있을 거 같은 다이아 문제를 골랐었다. (그러지 말 걸 그냥 플레 문제 2개 더 풀걸) 다이아다 보니 당연히 어려웠고, 아 이게 다이아인가 싶었다. 우선 쿼리의 종류는 4가지다. x y v: Ai = (Ai + v) % MOD를..

https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 구간합 lazy propagation으로 구현해주었다. >> 1번 쿼리 (구간 합 업데이트) 때문에 세그먼트 트리를 써야 했다. 그런데 구간 업데이트라서 lazy propagation이 필요했다. lazy propagation 개념 공부할 때와 똑같은 구성이라 그런지 어렵게 느껴지진 않았었다. #include #define MAX (100000 + 1) #define ll lo..

https://www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 이번 문제는 구간 합 lazy propagation을 조금만 응용하면 풀릴 줄 알았다. 하지만, 이 문제는 세그먼트 트리와 lazy propagation을 정확히 꿰뚫고 있어야 풀리는 문제다. 맨 처음에 떠올린 방법은 leaf노드에 도달하면 leaf노드가 0이면 1, 1이면 0의 방식으로 전환을 해주고, 업데이트를 하면 될 거라고 생각했다. 이렇게 되면 따져..

https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 앞선 세그먼트 트리 정리에서 구간 업데이트를 할 때는 Lazy Propagation을 통해 O(logN)으로 구현할 수 있다고 했다. 물론 구간합 함수를 참고하여 구간 업데이트를 할 수 있지만 이는 O(NlogN)으로 시간 초과가 난다. Lazy Propagation에 대해서는 다음 블로그를 참고하여 공부했다. (https://ya..