Comet OJ

C1712 [CEOI2014Day2] Cake

内存限制：1024 MB 时间限制：2000 ms

题目描述

Leopold and Molly love cake: While Leopold loves eating cake, Molly loves watching Leopold eat cake. Today, they have bought $N$ pieces of seedcake. The pieces are on a narrow plate with $N$ cake piece positions in a row. From left to right, the positions are numbered from $1$ to $N$. Also the pieces are numbered, with piece $i$ on position $i$.

When eating cake, Leopold considers how delicious the pieces are. For each piece $i$, he exactly knows about its initial deliciousness value $d_i$. He starts with some piece $a$; then, position a is empty. After that, the next piece he eats is always the least delicious piece next to any empty position. Hence, at any time, all empty positions are from a single closed interval. To make things even more interesting, Molly occasionally adds a topping to some piece to enhance its deliciousness. She will always do so in a way that makes the piece one of the 10 most delicious pieces. At any time, no two pieces will be equally delicious.

Sometimes, Molly wonders how many of the pieces Leopold will eat before he eats a certain piece $b$—assuming there are no future enhancements. Help Molly and write a program that can process instructions of the form “enhance a piece” or “find the number of pieces Leopold will eat before a certain piece”.

输入格式

The first line contains the two integers $N (1 ≤ N ≤ 250000)$, the number of pieces, and $a (1 ≤ a ≤ N)$, the piece Leopold will eat first. The second line contains $N$ mutually distinct integers $1 ≤ d_1,...,d_N ≤ N$, the initial deliciousness values of the pieces. The third line contains $1 ≤ Q ≤ 500000$, the number of instructions to process. Each of the next $Q$ lines contains an instruction of one of the following two types:

  • E i e(the character “E” followed by two integers $1≤i ≤ N$ and $1≤e≤10$): an instruction of this type tells your program that piece $i$ is enhanced so that it becomes the unique $e$-th most delicious piece. The number of pieces that, before the enhancement, were more delicious than piece $i$ is guaranteed to be at least $e$.
  • F b(the character “F” followed by an integer $1≤b≤ N$): an instruction of this type requests your program to tell how many pieces Leopold will eat before he eats piece $b$.

输出

For each instruction of type “F”, in the order as these instructions appear in the input, output a line that contains a single integer: the requested number of pieces.

样例

样例输入 1

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

样例输出 1

4
1
0
2
3
4
3
0
1
2
4
3
0
1
2

提示

Constraints

$N ≤250000,Q≤500000$

Subtask 1 (15points). $N,Q≤10000$

Subtask 2 (15points). $N ≤25000$, and there are at most 500 instructions of type “F”.

Subtask 3 (20points). $Q≤100000$, and there are at most 100 instructions of type “E”.

Subtask 4 (50points). No further constraints.