#6346. 线段树:关于时间

内存限制:256 MiB 时间限制:200 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Diogenes

题目描述

n 个整数 a_1, a_2, \dots, a_n 组成一个序列。有一个存储三元组的列表,开始时该列表为空。
m 个操作,这些操作分为两种:

  • \texttt{1 L R x}\:\: (L, R, x) 加入列表中。
  • \texttt{2 L R}\;\;\quad a_L + a_{L+1} + \cdots + a_R

每执行完一个操作,就读取一遍列表,对于其中的每一组 (L, R, x) a_L, a_{L+1},\ldots,a_R 都加上 x (这不算做操作)。

输入格式

第一行一个整数 n ,表示序列长度。
第二行 n 个整数。
第三行一个整数 m ,表示操作数。
然后 m 行,先输入一个数 D D 1 2

  • D 1 ,读入 3 个整数 L, R, x
  • D 2 ,读入 2 个整数 L, R

输出格式

对于每个操作 \texttt{2 L R} ,输出一行,一个整数, a_L + a_{L+1} + \cdots + a_R

样例

样例输入

3
1 2 3
4
1 1 3 1
2 1 1
1 2 3 2
2 2 3

样例输出

2
15

样例解释

列表 输出 a_i
开始   1 2 3
1 1 3 1 1 3 1<
读取列表 1 3 1   2 3 4
2 1 1  1 3 1  2
读取列表 1 3 1 3 4 5
1 2 3 2 1 3 1
2 3 2<
 
读取列表 1 3 1
2 3 2
4 7 8
2 2 3  1 3 1 
2 3 2
15
读取列表 1 3 1
2 3 2
5 10 11

数据范围与提示

对于 60 \% 的数据,暴力可过。
对于 100 \% 的数据, 1 \le n, m \le 10^5, 1 \le L \le R \le n, 1 \le a_i \le 10^4 , -10^4 \le x \le 10^4