#T2140. 区间更新与求和(Range Updates and Sums)

区间更新与求和(Range Updates and Sums)

链接: https://cses.fi/problemset/task/1735

板块: Range Queries

时限: 1.00 s | 内存: 512 MB

题目描述

你的任务是对一个包含 nn 个值的数组进行维护,并高效处理以下类型的查询:

  1. 将区间 [a,b][a,b] 中的每个值都增加 xx。
  2. 将区间 [a,b][a,b] 中的每个值都设为 xx。
  3. 计算区间 [a,b][a,b] 中数值的和。

输入

第一行输入包含两个整数 nn 和 qq:分别表示数组大小和查询数量。

下一行包含 nn 个值 t1,t2,…,tnt_1,t_2,\dots,t_n:数组的初始内容。

最后有 qq 行描述查询。每行格式为以下之一:"11 aa bb xx"、"22 aa bb xx" 或 "33 aa bb"。

输出

对每个求和查询输出其答案。

数据范围

1≤n,q≤2⋅1051 \le n, q \le 2 \cdot 10^5 1≤ti,x≤1061 \le t_i, x \le 10^6 1≤a≤b≤n1 \le a \le b \le n

样例输入

6 5
2 3 1 1 5 3
3 3 5
1 2 4 2
3 3 5
2 2 4 5
3 3 5

样例输出

7
11
15