P6544 [CEOI 2014] Cake

CEOI 2014 Day 2 T2. Translator: Xiao Fen Tu.

Both Leopold and Molly like cakes: Leopold likes eating cakes, and Molly likes watching Leopold eat cakes. There are $n$ pieces of cake in a row. The $i$-th cake from left to right is labeled $i$, and each cake has a deliciousness value $d_i$. Leopold will first eat the cake labeled $a$, leaving position $a$ empty. After that, each time he will choose, among the cakes adjacent to the empty position, the cake with the smallest deliciousness and eat it (saving the tastier ones for later). You can observe that the empty positions will always form a continuous interval. To make things more interesting, Molly sometimes adds a bit of decoration to one cake to increase its deliciousness. She guarantees that after this operation, this cake’s deliciousness will become one of the top $10$ among all cakes. Also, at any time, the deliciousness values of any two cakes are different. Sometimes Molly is curious: before Leopold eats a specific cake labeled $b$, how many cakes will he have eaten? Please help Molly write a program that, given a sequence of operations, answers Molly’s queries.

The first line contains two positive integers $n, a$, representing the total number of cakes and which cake Leopold eats first. The second line contains $n$ pairwise distinct positive integers $d_1, d_2, \ldots, d_n$, representing the initial deliciousness values. The third line contains a positive integer $q$, representing the number of operations. The next $q$ lines each describe an operation in the form `E i e` or `F b`: - `E i e`: Increase the deliciousness of cake $i$ to be the $e$-th most delicious. It is guaranteed that before the operation, the number of cakes more delicious than cake $i$ is at least $e$. - `F b`: Ask how many cakes Leopold will eat before eating cake $b$.

For each `F` operation, output one line with one number, representing the answer.

**Sample Explanation** Before the first increase in deliciousness, the cakes labeled $3, 2, 4, 5, 1$ will be eaten in this order. But after that, cake $1$ becomes so delicious that it will not be eaten earlier, and cakes $4$ and $5$ are eaten first. Note that the last increase in deliciousness of cake $5$ will not change the eating order. **Constraints and Notes** For all testdata, it is guaranteed that $1 \le n \le 2.5 \times {10}^5$, $1 \le q \le 5 \times {10}^5$, $1 \le d_i, a, i, b \le n$, and $1 \le e \le 10$. | Subtask ID | Score | Special Constraints | | :-: | :-: | :-: | | $1$ | $15$ | $n, q \le {10}^4$ | | $2$ | $15$ | $n \le 2.5 \times {10}^4$ and the number of `F` operations does not exceed $500$ | | $3$ | $20$ | $q \le {10}^5$ and the number of `E` operations does not exceed $100$ | | $4$ | $50$ | No special constraints. | Translated by ChatGPT 5