bzoj#P3301. [USACO2011 Feb] Cow Line
[USACO2011 Feb] Cow Line
题目描述
头牛,编号为 ,正在与 Farmer John 玩一个疯狂的游戏。奶牛会排成一行(牛线),问 Farmer John 此时的行号是多少。之后,Farmer John 会给牛一个行号,牛必须按照新行号排列成线。
行号是通过以字典序对行的所有排列进行编号来分配的。比如说:Farmer John 有 头牛,让他们排为行号 ,排列顺序为:
st:
nd:
rd:
因此,牛将在牛线 中。
之后,奶牛排列为 ,并向 Farmer John 问他们的行号。继续列表:
th:
th:
Farmer John 可以看到这里的答案是 。
Farmer John 和奶牛希望你的帮助玩他们的游戏。他们需要 组查询,查询有两个部分:将是 P
或 Q
的命令。
-
如果 是
P
,则查询的第二部分将是一个整数 ,它是行号。此时,你需要回答正确的牛线。 -
如果 是
Q
,则查询的第二部分将是 个不同的整数 。这将表示一条牛线,此时你需要输出正确的行号。
输入格式
第 行两个整数 。
第 行:第 行,一个字符 P
或 Q
,指明类型。
如果第 行是 P
,则第 行是一个整数,表示行号;如果第 是 Q
,则第 行是 个空格隔开的整数,表示牛的排列方式。
输出格式
第 行:如果输入的第 行是 P
,则输出牛的排列方式;如果输入的第 行是 Q
,则输出行号。
5 2
P
3
Q
1 2 5 3 4
1 2 4 3 5
5
数据规模与约定
对于 的数据,,,,。
题目来源
Silver