[FJOI2017] 远古山脉问题
题目描述
远古山脉可以看作是一个由山脉元素组成的序列,每个元素有一个高度,远
古山脉的变化规则如下:
1. I h x:在第x个山脉元素右边插入高度为h的山脉元素。
2. R l r:从第l个山脉元素到第r个山脉元素的高度翻转, 例如,$a_1,a_2,a_3,a_4,a_5$,对$(2,5)$翻转就变为$a_1,a_5,a_4,a_3,a_2$
3. M t x:在第x个山脉元素右边插入第t个山脉。
山脉元素按从左到右的顺序从$1$开始编号。一开始时没有山脉元素,记为第$0$个山脉。对于第$i$个山脉,经过任意一种变化后就变成第$i+1$个山脉。山脉中会收集山脉能量,假设山脉中最高的山脉元素的编号为$x$,如果有$m$个相同的高度,取左数第$\left \lceil \frac{m}{2} \right \rceil$个元素,那么山脉收集的能量为:
$$\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.$$
其中$h_{i}$代表第$i$个山脉元素的高度。
山脉序列问题需要回答的基本询问是:从第$l$个山脉元素到第$r$个山脉元素组成子山脉能收集的能量是多少?
输入输出格式
输入格式
文件的第一行有1个正整数$n$, ($n\le 50000$),表示山脉变化和询问的总次数。
接下来n行,每行是四种格式之一:
1. I h x: 在第$x$个山脉元素右边插入高度为$h$的山脉元素, $0\le h\le 20000$。
2. R l r: 从第$l$个山脉元素到第$r$个山脉元素的高度翻转。
3. M t x: 在第$x$个山脉元素右边插入第$t$个山脉。
4. Q l r: 询问由第l个山脉元素到第$r$个山脉元素组成子山脉能收集的能量是多少。
对于第$i$个山脉,经过任意一种变化后就变成第$i+1$个山脉。
保证以上所有输入整数在long long范围内
输出格式
对于每个询问,输出一行答案,答案对1000000007取模。
输入输出样例
输入样例 #1
10
I 1 0
I 2 1
I 3 1
Q 1 3
I 4 3
Q 1 4
R 2 4
Q 1 4
M 3 4
Q 2 7
输出样例 #1
0
2
2
6