华师一附中OI组

标题: P2710 数列 [打印本页]

作者: admin 时间: 2020-4-10 14:32
标题: P2710 数列
https://www.luogu.com.cn/problem/P2710

题目描述
维护一个数列,共 7 种操作:

I. INSERT x n a1 a2 .. an 在第 x 个数后插入 n 个数分别为 a1…an。

II. DELETE x n 删除第 x 个数开始的 n 个数。

III. REVERSE x n 翻转第 x 个数开始的 n 个数的区间。

IV. MAKE-SAME x n t 将第 x 个数开始的 n 个数统一改为 t。

V. GET-SUM x n 输出第 x 个数开始的 n 个数的和。

VI. GET x 输出第 x 个数的值。

VII. MAX-SUM x n 输出第 x 个数开始的 n 个数的最大连续子序列和。

输入格式
第一行为 N，M，N 表示初始序列中数的个数，M 表示操作的个数。

第二行为 N 个数 A1…An，表示初始序列。

第三行到第 M+2行，每行一个操作。

输出格式
输出每个GET-SUM，GET，MAX-SUM操作的结果。

输入输出样例
输入 #1复制
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM 1 9
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET 5
MAX-SUM 1 11
输出 #1复制
-1
10
-5
10
说明/提示
共 20 组数据，每组数据随机生成，
保证每个时刻数列里的数不超过 200000 个，
任何一个输入的数字均在 −1000～1000之间，结果不超过 2^30。

第 1～2 组 1≤N≤5，1≤M≤10。

第 3～4 组 1≤N≤10，1≤M≤20。

第 5～6 组 1≤N≤20，1≤M≤50。

第 7～8 组 1≤N≤50，1≤M≤100。

第 9～10 组 1≤N≤100，1≤M≤500。

第 11～12 组1≤N≤1000，1≤M≤1000。

第 13～14 组 1≤N≤5000，1≤M≤2000。

第 15～16 组 1≤N≤10^4，1≤M≤5000。

第 17～18 组 1≤N≤10^5，1≤M≤10^4。

第 19～20 组 1≤N≤2×10^5，1≤M≤2×10^5。

欢迎光临华师一附中OI组 (http://hsyit.cn/)