P3814 [FJOI2017] Ancient Mountain Range Problem

An ancient mountain range can be regarded as a sequence of mountain elements, each with a height. The evolution rules are as follows: 1. I h x: Insert a mountain element of height $h$ to the right of the $x$-th mountain element. 2. R l r: Reverse the heights of the mountain elements from the $l$-th to the $r$-th. For example, $a_1,a_2,a_3,a_4,a_5$, reversing $(2,5)$ becomes $a_1,a_5,a_4,a_3,a_2$. 3. M t x: Insert the $t$-th mountain to the right of the $x$-th mountain element. Mountain elements are numbered from $1$ from left to right. Initially there are no mountain elements, denoted as the $0$-th mountain. For the $i$-th mountain, after applying any one operation it becomes the $(i+1)$-th mountain. The mountain collects energy as follows: suppose the index of the highest mountain element is $x$. If there are $m$ elements with the same maximum height, take the $\left \lceil \frac{m}{2} \right \rceil$-th one from the left. Then the collected energy is: $$\sum_{i=l}^{x-1}\left\{\begin{matrix} x-i & if\ h_{i}>h_{i+1}\\ 0 & if\ h_{i}\leq h_{i+1} \end{matrix}\right.+\sum_{i=x+1}^{r}\left\{\begin{matrix} i-x & if\ h_{i}>h_{i-1}\\ 0 & if\ h_{i}\leq h_{i-1} \end{matrix}\right.$$ Here $h_{i}$ denotes the height of the $i$-th mountain element. The basic query to answer is: for the sub-mountain formed by the mountain elements from the $l$-th to the $r$-th, how much energy can be collected?

The first line contains a positive integer $n$ ($n\le 50000$), the total number of operations and queries. Then follow $n$ lines, each in one of the following four formats: 1. I h x: Insert a mountain element of height $h$ to the right of the $x$-th mountain element, $0\le h\le 20000$. 2. R l r: Reverse the heights from the $l$-th mountain element to the $r$-th mountain element. 3. M t x: Insert the $t$-th mountain to the right of the $x$-th mountain element. 4. Q l r: Query the energy collected by the sub-mountain formed by the $l$-th to the $r$-th mountain elements. For the $i$-th mountain, after applying any one operation it becomes the $(i+1)$-th mountain. All input integers fit in the range of long long.

For each query, output the answer on one line, modulo 1000000007.

Translated by ChatGPT 5