공작소

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

문제 Don Cherry has been hired to run 24-hour coverage of a series of single-elimination, bracket-style, furniture disassembly tourneys (tournaments). Each competitor has a furniture disassembly skill level, an integer between 1 and 1 000 000 000. In every head-to-head match, the competitor with the larger skill level wins and moves on, while the other is eliminated from the tourney. It is guarant..

문제 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 ..

문제 You are given a binary sequence a_1,a_2,…, a_n of length n. You will also be given q queries of two different types. p t: replace a_p with t. l r x y: Find any [s, e] satisfying the following conditions, or report that none exists: l = b.cnt0_all && a.cnt0_all >= a.cnt0_right + b.cnt0_left) { tmp.cnt0_all = a.cnt0_all; tmp.cnt0_all_pos[0] = a.cnt0_all_pos[0]; tmp.cnt0_all_pos[1] = a.cnt0_all_..

문제 가로 블록만 등장하는 테트리스 게임을 해보려고 한다. 가로 블록은 총 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번 블록부터 순서대로 주어진다. 출력 블록..

도입 이 글은 세그먼트 트리를 처음 접하거나, 세그먼트 트리의 기초적인 응용에 대한 solution idea를 얻고 싶은 분들을 위하여 제가 세그먼트 트리 태그를 풀면서 정립한 세그먼트 트리 개념을 설명하는 글입니다. 이 글을 읽은 뒤 세그먼트 트리의 기본적인 사용법을 익히고 기초 응용 문제를 풀 수 있도록 하는 것이 이 글의 목적입니다. 기초적인 응용 이후에 세그먼트 트리에 관련한 여러 응용 문제를 직접 풀어본다면, 세그먼트 트리를 깊이 이해하며 트리 구조를 변형할 수 있는 능력을 기름과 동시에 추후 Lazy Propagation with Segment Tree, Persistent Segment Tree 등의 알고리즘에 대한 배경 지식을 얻을 수 있을 것입니다. 본 글은 C를 기반으로 작성되었습니다...