#P50487. 「NOI2007」 项链工厂

「NOI2007」 项链工厂

题目描述

T 公司是一家专门生产彩色珠子项链的公司,其生产的项链设计新颖、款式多样、价格适中,广受青年人的喜爱。最近 T 公司打算推出一款项链自助生产系统,使用该系统顾客可以自行设计心目中的美丽项链。
该项链自助生产系统包括硬件系统与软件系统,软件系统与用户进行交互并控制硬件系统,硬件系统接受软件系统的命令生产指定的项链。该系统的硬件系统已经完成,而软件系统尚未开发, T 公司的人找到了正在参加全国信息学竞赛的你,你能帮助 T 公司编写一个软件模拟系统吗?
一条项链包含 NN 个珠子,每个珠子的颜色是 1,2,,c1, 2, \dots , c 中的一种。项链被固定在一个平板上,平板的某个位置被标记位置 11 ,按顺时针方向其他位置被记为 2,3,,N2,3, \dots ,N

fff(1).png

你将要编写的软件系统应支持如下命令:

fa.png

试题澄清

  • 关于旋转和翻转 注意旋转命令旋转“珠子”但不改变“位置”的编号,而反转命令始终以位置 11 为对称轴。
  • 关于 CountSegment 命令 CS 命令表示查询一个“线段”中有多少个“部分”。尤其注意当查询的长度等于 NN 时,我们仍然将查询部分作为“线段”理解。

输入格式

输入第一行包含两个整数 N,cN, c ,分别表示项链包含的珠子数目以及颜色数目。
第二行包含 NN 个整数, x1,x2,,xnx_1, x_2 , \dots , x_n ,表示从位置 11 到位置 NN 的珠子的颜色,1xic1 \le x_i \le c
第三行包含一个整数 QQ ,表示命令数目。接下来的 QQ 行每行一条命令,如上文所述。

输出格式

对于每一个 CCCSCS 命令,应输出一个整数代表相应的答案。

样例

5 3
1 2 3 2 1
4
C
R 2
P 5 5 2
CS 4 1
4
1

数据范围与提示

对于 60%60\% 的数据, N1000,Q1000N \le 1000 , Q \le 1000
对于 100%100\% 的数据,N500000,Q500000,c1000N \le 500000 , Q \le 500000 , c \le 1000