网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
第二试-项链工厂
成绩 | 0 | 开启时间 | 2013年01月16日 星期三 10:35 |
折扣 | 0.8 | 折扣时间 | 2013年01月16日 星期三 10:35 |
允许迟交 | 是 | 关闭时间 | 2013年01月16日 星期三 10:35 |
输入文件 | necklace.in | 输出文件 | necklace.out |
【问题描述】
T公司是一家专门生产彩色珠子项链的公司,其生产的项链设计新颖、款式多样、价格适中,广受青年人的喜爱。最近T公司打算推出一款项链自助生产系统,使用该系统顾客可以自行设计心目中的美丽项链。
该项链自助生产系统包括硬件系统与软件系统,软件系统与用户进行交互并控制硬件系统,硬件系统接受软件系统的命令生产指定的项链。该系统的硬件系统已经完成,而软件系统尚未开发,T公司的人找到了正在参加全国信息学竞赛的你,你能帮助T公司编写一个软件模拟系统吗?
一条项链包含N个珠子,每个珠子的颜色是1, 2, …, c中的一种。项链被固定在一个平板上,平板的某个位置被标记位置1,按顺时针方向其他位置被记为2,3,…,N。
你将要编写的软件系统应支持如下命令:
命令 | 参数限制 | 内容 |
R k |
0 |
意为Rotate k。将项链在平板上顺时针旋转k个位置, 即原来处于位置1的珠子将转至位置k+1,处于位置2的珠子将转至位置k+2,依次类推。 |
F | 意为Flip。将平板沿着给定的对称轴翻转,原来处于位置1的珠子不动,位置2上的珠子与位置N上的珠子互换,位置3上的珠子与位置N-1上的珠子互换,依次类推。 | |
S i j | 1≤i , j≤N | 意为Swap i , j。将位置i上的珠子与位置j上的珠子互换。 |
P i j x | 1≤i , j≤N, x≤c | 意为Paint i , j , x。将位置i沿顺时针方向到位置j的一段染为颜色x。 |
C | 意为Count。查询当前的项链由多少个“部分”组成,我们称项链中颜色相同的一段为一个“部分” | |
CS i j | 1≤i , j≤N | 意为CountSegment i , j。查询从位置i沿顺时针方向到位置j的一段中有多少个部分组成。 |
【输入文件】
输入文件第一行包含两个整数N, c,分别表示项链包含的珠子数目以及颜色数目。第二行包含N个整数,x1, x2…, xn,表示从位置1到位置N的珠子的颜色,1 ≤xi ≤c。第三行包含一个整数Q,表示命令数目。接下来的Q行每行一条命令,如上文所述。
【输出文件】
对于每一个C和CS命令,应输出一个整数代表相应的答案。
【输入样例】
5 3 1 2 3 2 1 4 C R 2 P 5 5 2 CS 4 1
【输出样例】
4 1
【评分方法】
本题没有部分分,你的程序的输出只有和标准答案完全一致才能获得满分, 否则不得分。
【数据规模和约定】
- 对于60%的数据,N ≤1 000,Q ≤1 000;
- 对于100%的数据,N ≤500 000,Q ≤500 000,c ≤1 000。