풍경 생성기
시간 제한4초메모리 제한2048 MB
길이 n인 높이 배열에 k개의 구간 연산을 순서대로 적용한다. 각 연산은 구간 전체를 1만큼 올리거나 내리거나, 삼각형 모양의 언덕이나 골짜기를 더한다. 모든 연산이 끝난 뒤 각 지점의 높이를 출력한다.
문제
Interactive Creative Players Collective (ICPC)는 사실적인 풍경을 생성하는 새 컴퓨터 게임을 만들고 있다. ICPC의 엔지니어 한 명이 지질 작용에서 착안한 알고리즘을 제안했다. 이 알고리즘은 평평한 풍경에서 시작해 연속한 구간을 들어 올리거나 내리는 작업을 반복하며, 이렇게 해서 지루(융기된 구간)와 지구(침강된 구간)를 만든다. 들어 올리거나 내릴 구간은 무작위로 선택한다. ICPC는 이런 방식으로 사실적인 풍경을 얻기를 바란다.
여러분의 임무는 이런 작업이 임의의 순서로 주어졌을 때 그 결과 풍경을 출력하는 것이다. 풍경은 x축 위의 정수 좌표 1부터 n까지 각 점의 높이를 나타내는 n개의 정수로 표현한다. 그림 E.1은 높이 값을 선분으로 이은 예를 보여 준다.
그림 E.1: 예제 입력 1로 생성한 풍경.
처음에는 n개 점 모두 높이가 0이다. 이 평평한 지형에 일련의 작업을 적용한다. 각 작업은 두 정수 매개변수 x1 ≤ x2를 가지며 다음 네 가지 연산 중 하나를 수행한다.
R: Raise. x1부터 x2까지 모든 점의 높이를 1만큼 늘린다.D: Depress. x1부터 x2까지 모든 점의 높이를 1만큼 줄인다.H: Hill. x1과 x2 사이에 선형 모양의 언덕을 새로 더한다.V: Valley. x1과 x2 사이에 선형 모양의 골짜기를 새로 더한다.
언덕을 더하는 방법은 다음과 같다. 점 x1과 x2의 높이를 1만큼 늘린다. x2 − x1 > 1이면 점 x1 + 1과 x2 − 1의 높이를 2만큼 늘린다. x2 − x1 > 3이면 점 x1 + 2와 x2 − 2의 높이를 3만큼 늘리는 식으로 계속한다. 그림 E.2에 예가 나와 있다. 골짜기를 더하는 방법도 높이를 늘리는 대신 줄인다는 점만 빼면 같다. 높이 변화가 가장 큰 곳은 x1과 x2의 중간이다. x2 − x1이 홀수면 변화가 최대인 점이 이웃한 두 개이고, 짝수면 하나이다.
그림 E.2: 예제 입력 2로 생성한 풍경.
입력
첫째 줄에 두 정수 n과 k가 주어진다. n (1 ≤ n ≤ 200 000)은 점의 개수이고 k (0 ≤ k ≤ 200 000)는 작업의 개수이다. x축 위의 n개 점은 1부터 n까지 번호가 붙어 있다. 다음 k개 줄에 작업이 주어진다. 각 줄에는 문자 c 하나와 두 정수 x1, x2가 주어진다. c는 R, D, H, V 중 하나로 연산을 나타내고, x1과 x2 (1 ≤ x1 ≤ x2 ≤ n)는 그 매개변수이다.
출력
n개 줄을 출력한다. i번째 줄에는 주어진 순서대로 모든 작업을 적용한 뒤 점 i의 높이를 출력한다.