[CEOI 2014] Cake
时间限制：20s 空间限制：1024MB
题目描述
Leopold买了n块蛋糕, 这些蛋糕排成一排，从左到右记为1到n，第i块蛋糕最初的美味度为di。
Leopold每次固定最先吃第k块蛋糕，于是位置k就空出来了。之后他吃的每一块蛋糕总是位于某个空的位置旁边，并且是美味度最低的一块。因此在任何时刻，所有空的位置是一段连续的区间。Leopold会装饰自己的蛋糕来增加它的美味度，被加过装饰的蛋糕一定会成为最美味的10个蛋糕之一，任何时候都不存在两块美味度相同的蛋糕。
Leopold想知道在他吃到某块蛋糕b之前需要吃掉多少块蛋糕。
输入格式
第一行两个整数n和k，表示蛋糕的数量和Leopold吃的第一块蛋糕的位置。
第二行n个不同的整数d1,d2...,dn，表示第i块蛋糕最初的美味度。
第三行一个整数q，表示操作的数量。
下面q行会包括以下两种操作。
(1)E i e 蛋糕i被装饰成了第e美味的蛋糕（即原来前e-1美味的蛋糕不变，原来第e美味的蛋糕变成了第e+1美味的蛋糕，以此类推）注意每次装饰一定会增加美味度。
(2)F b输出Leopold吃到蛋糕b之前需要吃掉多少块蛋糕。
输出格式
对于每个F操作，输出一行一个整数，表示蛋糕的数量。
样例输入
5 3 5 1 2 4 3 17 F 1 F 2 F 3 F 4 F 5 E 2 1 F 1 F 2 F 3 F 4 F 5 E 5 2 F 1 F 2 F 3 F 4 F 5
样例输出
4 1 0 2 3 4 3 0 1 2 4 3 0 1 2
提示
在第一次装饰前，蛋糕会按顺序3,2,4,5,1被吃掉。但装饰以后，由于蛋糕2美味度较高，它不会很快被吃掉，而蛋糕4和5会先被吃掉。但是第二次对蛋糕5的装饰对于吃掉蛋糕的顺序没有影响。
对于100%的数据满足
1≤k≤n≤250000
1≤q≤500000
1≤e≤10
题目来源
uploaded by dwellings