TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

66.7% (2/3)

Tags

Description

相信大家或多或少都有參與過一些團康活動像跳舞、玩節奏遊戲、甚至是大風吹等等遊戲吧!而在進行這些活動的時候,我們往往不會將所有人編排成一直列,而是讓大家「圍成一圈」吧?現在,我們就要來處理這個問題!

在某年某月某日的某個時刻,第97管理外世界極東地區的某個角落,有一位<b>魔法少年——阿思</b>正在與他的同伴玩著一個以魔力為基礎的遊戲,其名為「<b>HALLO☆GAME</b>」,規則如下:
----------------------------------------------------------------------
以一個人為中心,稱為「管理者」,為這場遊戲的控制權所在。
外圍環繞著其他玩家(某位玩家的編號為 1,再來沿順時針方向依序為2,3,…,N),
每個人需以魔力維持著一顆魔法水晶,使其漂浮在空中並顯現出特定的顏色代
表該玩家的屬性狀態,每位玩家必須盡量將魔力彈發射至與自身相同狀態的玩
家,而只要另一位被發射魔力彈的同狀態玩家以緩衝式的防禦魔法陣將魔力彈
反彈至中央管理者的感應範圍陣內的話,便稱為「HALLO!!」,而發出魔力彈
與反彈者各得一分。而每個玩家的水晶顏色會隨著管理者的一些操作 (如下表)
所改變,因此與自身相同狀態的玩家並不會一直是同一群人。
----------------------------------------------------------------------

在時間內得分最多者為勝家。


※管理者的操作: (指令皆為咒語,咒語皆由大寫字母組成,後面接的 k, i, j 為整數變數)

指令參數限制意義
RSXACZAE k
0 < k < N
將所有人的水晶顏色順時針旋轉 k 個位置,意即將原本編號 1 的人的顏色轉到編號 k+1 的人、編號 2 的人的顏色轉到編號 k+2 的人…etc.
FLPPITZ
無參數
將所有人的水晶顏色以編號 1做對稱軸做左右互換,意即編號 1的人顏色不動,將原本編號2 的人的顏色與編號N 的人的顏色互換、編號 3 的人的顏色轉到編號 N-1 的人的顏色互換…etc.
SNFANG i j
1<=i,j<=N
將原本編號i 的人的顏色與編號 j 的人的顏色互換
PASZTY i j k
1<=i,j<=N
k<=C
從編號i 的人開始沿順時針方向到編號j 的人的水晶顏色改成顏色 k
CUNTAT
無參數
查詢現在的水晶由幾個「相同顏色區段」組成,我們把連續的人顏色皆相同的部分稱做「相同顏色區段」
CSAQPL i j
1<=i,j<=N
查詢從編號i 的人開始沿順時針方向到編號j 的人的水晶由幾個「相同顏色區段」組成

Input Format

輸入的測試資料第一行包含兩個正整數 N, C (N<=500000, C<=1000)分別代表遊戲的人數(不含中央的管理者)和可能的水晶顏色種類數。 第二行有 N個整數 ci (1<=ci<=C) 表示從編號1的人到編號N的人的初始水晶顏色為何。第三行有一個整數 Q (0<=Q<=500000)代表管理者在遊戲過程中的操作次數,接下來有 Q 行,每一行都以一個咒語開頭,代表一個操作指令,詳細對應如上表。

Output Format

對於每次的 CUNTATCSAQPL 操作指令輸出一個相對應的答案。

Sample Input 1

3 2
1 2 1
3
CUNTAT
PASZTY 1 2 1
CSAQPL 1 3

Sample Output 1

2
1

Hints

Problem Source

原TIOJ1516 / Problem Setter: skyly

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5
5 5000 65536 262144 6
6 5000 65536 262144 7
7 5000 65536 262144 8
8 5000 65536 262144 9
9 5000 65536 262144 10