공작소

도입 세그먼트 트리 이후 작성하는 알고리즘 튜토리얼 글입니다. 이 글은 세그먼트 트리의 응용 방식 중 하나인 Lazy Propagation in Segment Tree ( 느리게 갱신되는 세그먼트 트리 ) 에 대한 원리 및 응용 방식을 다루고 있으며, 이 글을 읽은 후 느리게 갱신되는 세그먼트 트리를 이용하여 여러 문제를 풀 수 있도록 하는 것이 이 글의 목적입니다. Lazy 값을 이용한 느린 전파 테크닉을 이해하여 추후 더 나아가 Segment Tree Beats 등을 배우면서 어려운 구간 쿼리를 해결하는 능력을 기를 수 있을 것입니다. 본 글은 C를 기반으로 작성되었습니다. 세그먼트 트리에 대한 이해가 필요합니다! https://readytojoin.tistory.com/57 [ Algorithm ]..

문제 A binary array is an array which each element can be either 0 or 1. Aleka has a binary array B or length N. The elements of B are indexed from 1 to N. Aleka will play with her array. She will run Q queries one after another. Each query can be one of the following type : FLIP L R: Flip all bits of B from index L to R, inclusive. Flipping bit is changing the value of a bit from 0 to 1, or from ..

문제 가로 블록만 등장하는 테트리스 게임을 해보려고 한다. 가로 블록은 총 N개가 등장할 예정이고, 등장하는 순서대로 1, 2, ..., N번이다. i번 블록의 높이는 1이고, 너비는 Wi이다. i번 블록은 왼쪽 벽으로부터 거리가 Di 떨어진 곳에 떨어뜨려야 한다. 블록을 회전시키거나, 위치를 이동시키는 것은 불가능하다. 블록은 위에서부터 떨어지며, 다른 블록 또는 바닥을 만날때 까지 한 칸씩 떨어진다. N개의 블록 정보가 주어졌을 때, 블록이 쌓인 높이를 구해보자. 입력 첫째 줄에 블록의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 블록의 정보 Wi, Di (1 ≤ Wi, Di ≤ 1,000,000,000)가 한 줄에 하나씩 1번 블록부터 순서대로 주어진다. 출력 블록..

문제 아날로그 다이얼이란 0부터 9까지 각 숫자 중 하나를 항상 표시하고 있는 작은 기계이다. 다이얼에는 화면에 보이는 숫자를 1 증가시킬 수 있는 버튼도 있다. (9를 1 증가시키면 0이 된다) 상근이는 이러한 아날로그 다이얼을 N개 가지고 있고, 모두 책상에 일렬로 올려 놓았다. 왼쪽 기계부터 1번기계이며, 가장 오른쪽 기계는 N번 기계이다. 또, 기계의 앞에 무엇인가를 작성할 수 있도록 종이 두 장을 놓았다. 가장 처음에 상근이는 다이얼에 보이는 숫자를 첫 번째 종이에 적는다. 그 다음 다음과 같은 행동을 M번 반복한다. 1. 두 정수 A와 B를 고른 다음, 첫 번째 종이에 작성한다. (1 ≤ A ≤ B ≤ N) 2. A번째 다이얼부터 B번째 다이얼에 적혀있는 숫자의 합을 구한 다음에 두 번째 종이..

문제 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이다. S와 T가 올바른 괄호 문자열이라면, ST도 올바른 괄호 문자열이다. 모든 올바른 괄호 문자열은 위의 3개 규칙으로만 만들 수 있다. '('와 ')'로 이루어진 괄호 문자열 S = s1s2...sN과 M개의 쿼리가 주어진다. 쿼리는 정수 하나 index로 이루어져 있고, 쿼리가 의미하는 것은 다음과 같다. S의 i번째 문자가 '('면 ')'로, ')'면 '('로 변경한다. 쿼리의 수행은 누적되며, i번째 쿼리는 i-1번째 쿼리가 수행된 결과에 수행되어야 한다. 각 쿼리를 수행한 결과가 올바른 괄호 문..

문제 민호가 관리하는 천나라에는 N개의 집이 있다. 민호는 집을 쉽게 관리하기 위해 각각의 집을 1번, 2번, … N번으로 부르기로 했다. 어느 날 미적 감각에 눈을 뜬 민호는 특정 구간의 집들의 색들을 새롭게 칠하거나, 특정 구간의 집들에 존재하는 색의 수를 알고 싶어졌다. 작업은 다음과 같은 두가지로 이루어 진다. “C x y z” : x번과 y번, 그리고 그 사이에 있는 모든 집을 z번 색으로 색칠한다. “Q x y” : x번과 y번, 그리고 그 사이에 있는 모든 집에 존재하는 색의 가짓수를 출력한다. 민호가 사용할 색의 종류는 (1번, 2번, … T번) 이라 하고 처음 모든 집은 1번으로 색칠되어 있다고 생각한다. 민호가 해야하는 작업을 시뮬레이션 해보는 프로그램을 작성하자. 입력 첫 번째 줄에 ..

문제 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순서대로 1, 2, ..., N의 번호를 갖는다. 매일 밤 별들은 1, 2, ..., N의 연속한 부분 구간 [L, R]에 떨어진다. [L, R]에 별이 떨어지면, 각 점에는 순서대로 1, 2, ..., R-L+1개의 별이 떨어진다. 다시 말해, L에는 1개, L+1에는 2개, ..., R에는 R-L+1개의 별이 떨어진다. 욱제는 하늘에서 떨어지는 별들을 기록하다가 잠이 들어버렸다!! 혹시나 했지만 역시나, 여러분은 욱제를 대신해 아래의 쿼리를 수행해야 한다. (ㅎㅎ;; ㅈㅅ.. ㅋㅋ!!) 1 L R: [L, R]에 별..

문제 상근이는 유전자 조작을 통해 줄기 두 개로 이루어진 식물을 만들었다. 이 식물은 줄기의 x좌표 L, R과 높이 H로 나타낼 수 있다. 아래 그림은 L=2, R=5, H=4인 식물이다. 상근이는 매일 매일 화단에 식물을 하나씩 심는다. 첫 번째 날에 심은 식물의 높이는 1이고, 그 다음날에 심은 식물은 전날에 심은 식물의 높이보다 1 크다. 새 식물의 줄기가 다른 식물의 수평 선분과 교차하는 경우가 있다. 이러한 경우에 그 위치에는 꽃이 하나 피게 된다. (이미 꽃이 있는 경우에는 꽃이 더 피지 않는다) 점에서 접하는 경우에는 꽃이 피지 않는다. 아래 그림은 예제를 나타낸 것이다. 모든 식물의 좌표가 주어졌을 때, 매일 매일 피는 꽃의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 식물을 심은..

문제 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. 입력 첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 1,000,000) 셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 넷째 줄부터 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. 1번 쿼리의 경우 1 ≤ i ≤ j ≤ N, -1,000,000 ≤ k ≤ 1,000,000 이고, 2번 쿼리의 경우 1 ≤ x ≤ N이다. 2번 쿼리는 하나 이상 주어진다. 출력 2번 쿼리가 주어질 ..

문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째부터 4번째 수에 6을 더하면 1, 2, 9, 10, 5가 되고, 여기서 2번째부터 5번째까지 합을 구하라고 한다면 26을 출력하면 되는 것이다. 그리고 그 상태에서 1번째부터 3번째 수에 2를 빼고 2번째부터 5번째까지 합을 구하라고 한다면 22가 될 것이다. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다..