Splay

参考题目

您需要写一种数据结构（可参考题目标题），来维护一个有序数列。

其中需要提供以下操作：翻转一个区间，例如原有序序列是 $5\ 4\ 3\ 2\ 1$ ，翻转区间是 $[2,4]$ 的话，结果是 $5\ 2\ 3\ 4\ 1$ 。

第一行两个正整数 $n,m$ ，表示序列长度与操作个数。序列中第 $i$ 项初始为 $i$ 。
接下来 $m$ 行，每行两个正整数 $l,r$ ，表示翻转的区间。

输出一行 $n$ 个正整数，表示原始序列经过 $m$ 次变换后的结果。

4 3 2 1 5

【数据范围】
对于 $100\%$ 的数据， $1 \le n, m \leq 100000$ ， $1 \le l \le r \le n$ 。

请写一个程序，要求维护一个数列，支持以下 $6$ 种操作：

编号	名称	格式	说明
1	插入	$\operatorname{INSERT}\ posi \ tot \ c_1 \ c_2 \cdots c_{tot}$	在当前数列的第 $posi$ 个数字后插入 $tot$ 个数字： $c_1, c_2 \cdots c_{tot}$ ；若在数列首插入，则 $posi$ 为 $0$
2	删除	$\operatorname{DELETE} \ posi \ tot$	从当前数列的第 $posi$ 个数字开始连续删除 $tot$ 个数字
3	修改	$\operatorname{MAKE-SAME} \ posi \ tot \ c$	从当前数列的第 $posi$ 个数字开始的连续 $tot$ 个数字统一修改为 $c$
4	翻转	$\operatorname{REVERSE} \ posi \ tot$	取出从当前数列的第 $posi$ 个数字开始的 $tot$ 个数字，翻转后放入原来的位置
5	求和	$\operatorname{GET-SUM} \ posi \ tot$	计算从当前数列的第 $posi$ 个数字开始的 $tot$ 个数字的和并输出
6	求最大子列和	$\operatorname{MAX-SUM}$	求出当前数列中和最大的一段子列，并输出最大和

第一行包含两个整数 $N$ 和 $M$ ， $N$ 表示初始时数列中数的个数， $M$ 表示要进行的操作数目。

第二行包含 $N$ 个数字，描述初始时的数列。以下 $M$ 行，每行一条命令，格式参见问题描述中的表格。

对于输入数据中的 $\operatorname{GET-SUM}$ 和 $\operatorname{MAX-SUM}$ 操作，向输出文件依次打印结果，每个答案（数字）占一行。

9 8 
2 -6 3 5 1 -5 -3 6 3 
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM

数据规模与约定

你可以认为在任何时刻，数列中至少有 $1$ 个数。
输入数据一定是正确的，即指定位置的数在数列中一定存在。
对于 $50\%$ 的数据，任何时刻数列中最多含有 $3 \times 10^4$ 个数。
对于 $100\%$ 的数据，任何时刻数列中最多含有 $5 \times 10^5$ 个数，任何时刻数列中任何一个数字均在 $[-10^3, 10^3]$ 内， $1 \le M \le 2 \times 10^4$ ，插入的数字总数不超过 $4 \times 10^6$ 。

题面由 @syksykCCC 提供。