Skip to content

11402: 【原1402】upit

题目

题目描述

author: BreakVoid 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1402

Description

你需要维护数列,要支持一下几个操作:

1 A B X-------将区间[A,B]的数覆盖为X。

(9,8,7,6,5,4,3,2,1)
操作: 1 3 5 0
(9,8,0,0,0,4,3,2,1)

2 A B X-------将区间[A,B]的数依次加上一个以X为首项、X为公差的等差数列。

(9,8,7,6,5,4,3,2,1)
操作: 2 3 5 2
(9,8,9,10,11,4,3,2,1)

3 C X---------将数X插入到第C个数之前。

(9,8,7,6,5,4,3,2,1)
操作: 3 4 100
(9,8,7,100,6,5,4,3,2,1)

4 A B---------询问区间[A,B]所有数的和。

(2,18,7,6,1,4,7,7,2)
操作: 4 6 7
输出: 11

初始数列有n项,共计Q个操作。

Input Format

第一行两个整数n,Q 表示数列初始有n项,操作共有Q个。

第二行n个整数,表示数列中每个元素的初始值。

接下来的Q行按照表格中的命令格式给出每个操作。

Output Format

对于每一个操作4,输出一行,表示本次询问的答案。

Sample Input

5 5
1 2 3 4 5
1 5 5 0
4 4 5
4 5 5
2 1 5 1
4 1 5

Sample Output

4
0
25

数据规模与约定

40%的数据保证仅有单点修改。 对于所有的数据保证,数列初始元素个数和操作数量都不超过3*10^5。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!