National Olympiad in Informatics, China, 2007
Company T specializes in selling necklaces with colored beads. The produced necklaces have fashionable designs, varied styles, and affordable prices, making them widely popular amongst young people. Recently, company T decided to launch a necklace "buffet" production system so that customers can decide for themselves which necklace design is most beautiful.
The necklace buffet production system includes a hardware system and a software system. The software system interacts with the user to control the hardware system, while the hardware system receives the commands from the software system and produces the specified necklace. The hardware system has already been completed, however the software system has yet to be developed. Company T's people have found you, competing at the National Olympiad in Informatics. Can you help company T write a software simulation system?
A necklace contains beads, and each bead is a color from colors . The necklace is secured onto a flat board. Some place on the board is labeled as position , and going clockwise from there, other places on the board are labeled positions .
The program you design must support the following commands:
Command | Parameter Constraints | Details |
---|---|---|
R k |
Meaning Rotate . The necklace on the board is rotated clockwise by spots. The bead at position moves to position , the bead at position moves to position , and so on. | |
F |
Meaning Flip. The necklace is flipped along the given axis of symmetry. The bead at position does not move, the bead at position swaps places with the bead at position , the bead at position swaps places with the bead at position , and so forth. | |
S i j |
Meaning Swap . The bead at position swaps places with the bead at position . | |
P i j x |
; | Meaning Paint . The segment of beads starting at position , inclusive, and ending at position , inclusive, is painted color . |
C |
Meaning Count. Query how many "sections" form the current necklace. We consider a consecutive segment with all beads the same color to be a "section". | |
CS i j |
Meaning CountSegment . Query how many sections form the segment of the current necklace starting at position , inclusive, and ending at position , inclusive. |
Input Specification
The first line of input contains two integers and , respectively
representing the number of beads in the necklace and the number of
colors.
The second line contains integers ,
representing the color of the beads from locations through , where
.
The third line of input contains an integer , the number of queries
to follow.
The following lines each contain a single command in one of the
formats described above.
Output Specification
For each C
and CS
command, output on a separate line an integer
corresponding to the appropriate answer.
Sample Input
5 3
1 2 3 2 1
4
C
R 2
P 5 5 2
CS 4 1
Sample Output
4
1
Constraints
For of the test cases: , .
For of the test cases: , , .
Clarifications
Regarding Rotations and Flips
Note that the rotate command rotates the beads, not the numberings of the positions. Also, the flip command will always have position as its axis of symmetry.
For example, when , the position numberings are depicted in Fig. 1 below:
Fig. 1: The numbering of bead positions.
Fig. 2: The initial colors of the beads.
Assuming the necklace beads are initially colored like Fig. 2, we can say that only the bead at position is colored . The beads at all other positions are colored .
After performing an R 2
command, the colors of the beads will be as
depicted in Fig. 3 below:
Fig. 3: Bead colors after carrying out
R 2
.Fig. 4: Bead colors after carrying out
F
.Note that currently, the numbering of necklace positions still remains
the same as in Fig. 1, so the axis for flipping still remains
unchanged. Thus, after making an F
command, the bead colorings will
be as depicted in Fig. 4.
Regarding the CountSegment Command
The CS
command asks for how many "sections" are within a "segment".
Especially take note of when a length segment is queried. We still
have to treat the queried region as a "segment".
Take the scenario in Fig. 4 for example. Carrying out a CS 1 10
command, the query asks for how many "sections" make up the segment
starting at position and ending at position . This should result in
an output of . In comparison, just carrying out a C
command would
result in an output of .
Problem translated to English by .
Comments