공작소

도입 세그먼트 트리 이후 작성하는 알고리즘 튜토리얼 글입니다. 이 글은 세그먼트 트리의 응용 방식 중 하나인 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번으로 색칠되어 있다고 생각한다. 민호가 해야하는 작업을 시뮬레이션 해보는 프로그램을 작성하자. 입력 첫 번째 줄에 ..