알고리즘 일지

문제 링크27173번: 수열과 쿼리 43 (acmicpc.net) 27173번: 수열과 쿼리 43길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i: Ai 를 출력한다. (1 ≤ i ≤ N) 2 x y t: 만약 Ax, Ax+1, ..., Ay 중 t 미만의 수가 있다면 이 쿼리를 무시www.acmicpc.net 문제 풀이 따끈따끈한 수열과 쿼리 43이 나왔다. 원래는 이 글을 쓸 생각이 없었지만, 지인이 풀이가 보고싶다고 해서, 기왕이면 잘 써볼려고 써보게 되었다. 일단, 이 문제를 풀 경지라고 생각하고 정말 대충 풀이를 적으려고 한다. Segment Tree Beats를 완벽하게 이해하고 있다면, 조금 더 이해가 쉬워 질 것이다. 일단..

문제 링크 10070번: 벽 (acmicpc.net) 10070번: 벽 지안지아는 똑같은 크기의 벽돌을 쌓아서 벽을 만들고 있다. 이 벽은 n열의 벽돌로 되어 있는데, 각 열은 왼쪽부터 오른쪽으로 차례대로 0부터 n-1까지 번호가 매겨져 있다. 각 열의 높이는 서로 www.acmicpc.net 문제 풀이 1번 쿼리는 지정된 높이 미달인 벽이 있으면 그 높이까지 벽을 쌓아주는 쿼리이다. 요약하면, $1$ $l$ $r$ $h$ 에 대하여, $A_i := max(A_i, h)$ $(l \leq i \leq r)$를 수행한다. 2번 쿼리는 지정된 높이를 초과하는 벽이 있으면, 그 높이까지 벽을 없애주는 쿼리이다. 요약하면, $2$ $l$ $r$ $h$ 에 대하여, $A_i := min(A_i, h)$ $(l \..