#XDS202. 【模板】线段树 2

【模板】线段树 2

题目描述

你需要维护一个长度为 nn 的数组,并支持以下三种操作:

  1. 将某一段区间内的每个数都加上一个指定的值;
  2. 将某一段区间内的每个数都设为某个指定的值;
  3. 查询某一段区间内所有数的和。

请你高效地处理这些操作。

输入格式

第一行两个整数 n,qn, q,分别表示数组的长度和操作的数量。

第二行 nn 个整数 a1,a2,,ana_1, a_2, \dots, a_n,表示初始数组的内容。

接下来 qq 行,每行描述一个操作,格式如下:

  • 1 x y k:表示将区间 [x,y][x,y] 内每个数加上 kk
  • 2 x y k:表示将区间 [x,y][x,y] 内每个数设置为 kk
  • 3 x y:表示查询区间 [x,y][x,y] 内所有数的和。

输出格式

对于每个查询操作 3 x y,输出一行一个整数,表示该区间的和。

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

数据规模与约定

对于 100%100\% 的数据,0n1070 \le n \le 10^7