NOI2007项链工厂

2014年7月31日2,1350

Description

 

Input

输入文件第一行包含两个整数N, c,分别表示项链包含的珠子数目以及颜色 数目。第二行包含N 个整数,x1, x2…, xn,表示从位置1 到位置N 的珠子的颜色, 1 ≤ xi ≤ c。第三行包含一个整数Q,表示命令数目。接下来的Q 行每行一条命令, 如上文所述。

Output

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

Sample Input

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

Sample Output

4
1

HINT

  对于60%的数据,N ≤ 1 000,Q ≤ 1 000; 对于100%的数据,N ≤ 500 000,Q ≤ 500 000,c ≤ 1 000。

题解

真是神烦线段树

主要就是记录下整个项链是否翻转过以及旋转的度。。。

其它是线段树基本操作