#P8132. [ICPC2020 WF] Landscape Generator

[ICPC2020 WF] Landscape Generator

题目背景

ICPC2020 WF E

题目描述

Interactive Creative Players Collective (ICPC) is working on a new computer game for which they want to generate realistic landscapes. One of the ICPC engineers proposed an algorithm inspired by geological processes. The algorithm starts with a flat landscape and repeatedly modifies it by lifting or lowering continuous blocks, thus forming horsts (lifted blocks) and grabens (lowered blocks). The blocks to be lifted or lowered are selected at random. ICPC hopes to obtain realistic landscapes this way.

Your task is to interpret any sequence of such modifications and output the resulting landscape. The landscape is represented by a sequence of nn integer height values, one for each integer point from 11 to nn on the xx-axis. Figure E.1 illustrates an example by connecting the height values with line segments.

Initially the height is 00 at all nn points. This flat shape is subjected to a sequence of modifications. Each modification applies one of the following four operations with two integer parameters x1x2x_1 \leq x_2:

  • R\texttt{R}: Raise -- increase the height by 11 at all points between x1x_1 and x2x_2 inclusive.
  • D\texttt{D}: Depress -- decrease the height by 11 at all points between x1x_1 and x2x_2 inclusive.
  • H\texttt{H}: Hill -- add a new linearly shaped hill between x1x_1 and x2x_2.
  • V\texttt{V}: Valley -- add a new linearly shaped valley between x1x_1 and x2x_2.

Adding a hill to the current landscape works as follows. The heights at points x1x_1 and x2x_2 are increased by 11. If x2x1>1x_2 - x_1 > 1, the heights at points x1+1x_1 + 1 and x21x_2 - 1 are increased by 22. If x2x1>3x_2 - x_1 > 3, the heights at points x1+2x_1 + 2 and x22x_2 - 2 are increased by 33, and so on. Figure E.2 shows an example. Adding a valley works in the same way except the heights are decreased instead. The maximal change of height happens in the middle between x1x_1 and x2x_2. If x2x1x_2 - x_1 is odd, there will be two neighboring points with maximal change, otherwise just one.

输入格式

The first line of input contains two integers nn and kk, where nn (1n2000001 \leq n \leq 200\,000) is the number of points, and kk (0k2000000 \leq k \leq 200\,000) is the number of modifications. The nn points along the xx-axis are numbered from 11 to nn. The next kk lines describe the modifications. Each line contains one character cc and two integers x1x_1 and x2x_2, where cc (one of R\texttt{R}, D\texttt{D}, H\texttt{H} or V\texttt{V}) designates the operation and x1x_1 and x2x_2 (1x1x2n1 \leq x_1 \leq x_2 \leq n) specify its parameters.

输出格式

Output nn lines, where the ithi^{\text{th}} line contains the height at point ii after applying all modifications in the given order.

20 13
H 12 13
D 5 18
R 13 14
R 8 16
H 2 3
V 10 19
V 3 13
R 8 13
V 3 10
D 5 18
V 11 12
R 1 6
R 14 19
1
2
0
-3
-7
-9
-11
-9
-7
-6
-6
-5
-3
-4
-5
-4
-4
-3
0
0
7 1
H 1 6
1
2
3
3
2
1
0