#P0067. 区间推平

区间推平

P0067 区间推平

题目描述

\hspace{15pt}维护一个长度为 nn 的序列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\},共有 mm 次操作。操作共有 22 种:

∙ \hspace{23pt}\bullet\,区间推平:将区间 [l,r][l, r] 中所有元素的值修改为 xx;

∙ \hspace{23pt}\bullet\,区间求和:询问区间 [l,r][l, r] 中所有元素之和。

\hspace{15pt}由于答案可能很大,区间求和的答案需要对 2322^{32} 取模后输出。

\hspace{15pt}保证所有数据随机生成。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(1≦n,m≦5×105)n, m \left(1 \leqq n, m \leqq 5 \times 10^5\right) 代表序列长度与操作次数。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$ 代表序列的初始元素。

\hspace{15pt}此后 mm 行,每行输入一个操作。每行先输入一个整数 op(1≦op≦2)op \left(1 \leqq op \leqq 2\right) 代表操作类型,随后在同一行:

∙ \hspace{23pt}\bullet\,若 op=1op = 1,输入三个整数 $l, r, x \left(1 \leqq l \leqq r \leqq n;\ 1 \leqq x \leqq 10^9\right)$ 代表将区间 [l,r][l, r] 的值修改为 xx;

∙ \hspace{23pt}\bullet\,若 op=2op = 2,输入两个整数 l,r(1≦l≦r≦n)l, r \left(1 \leqq l \leqq r \leqq n\right) 代表询问区间 [l,r][l, r] 的元素之和。

输出格式

\hspace{15pt}对于每次操作 22,在一行上输出一个整数,代表区间 [l,r][l, r] 的元素之和对 2322^{32} 取模后的结果。

测试样例

5 5
1 2 3 4 5
2 1 5
1 2 3 4
2 1 5
2 3 3
2 2 4
15
18
4
12

样例 1 解释

\hspace{15pt}初始序列为 {1,2,3,4,5}\{1, 2, 3, 4, 5\},操作过程如下:

∙ \hspace{23pt}\bullet\,执行 "2 1 5"\texttt{"2 1 5"}:区间 [1,5][1, 5] 的元素之和为 1+2+3+4+5=151+2+3+4+5=15;

∙ \hspace{23pt}\bullet\,执行 "1 2 3 4"\texttt{"1 2 3 4"}:将区间 [2,3][2, 3] 的值修改为 44,序列变为 {1,4,4,4,5}\{1, 4, 4, 4, 5\};

∙ \hspace{23pt}\bullet\,执行 "2 1 5"\texttt{"2 1 5"}:区间 [1,5][1, 5] 的元素之和为 1+4+4+4+5=181+4+4+4+5=18;

∙ \hspace{23pt}\bullet\,执行 "2 3 3"\texttt{"2 3 3"}:区间 [3,3][3, 3] 的元素之和为 44;

∙ \hspace{23pt}\bullet\,执行 "2 2 4"\texttt{"2 2 4"}:区间 [2,4][2, 4] 的元素之和为 4+4+4=124+4+4=12。

\hspace{15pt}因此依次输出 15,18,4,1215, 18, 4, 12。

6 6
7 7 2 9 4 1
2 1 6
1 2 5 3
2 2 4
1 1 6 1
2 1 6
2 5 6
30
9
6
2

样例 2 解释

\hspace{15pt}初始序列为 {7,7,2,9,4,1}\{7, 7, 2, 9, 4, 1\},操作过程如下:

∙ \hspace{23pt}\bullet\,执行 "2 1 6"\texttt{"2 1 6"}:区间 [1,6][1, 6] 的元素之和为 7+7+2+9+4+1=307+7+2+9+4+1=30;

∙ \hspace{23pt}\bullet\,执行 "1 2 5 3"\texttt{"1 2 5 3"}:将区间 [2,5][2, 5] 的值修改为 33,序列变为 {7,3,3,3,3,1}\{7, 3, 3, 3, 3, 1\};

∙ \hspace{23pt}\bullet\,执行 "2 2 4"\texttt{"2 2 4"}:区间 [2,4][2, 4] 的元素之和为 3+3+3=93+3+3=9;

∙ \hspace{23pt}\bullet\,执行 "1 1 6 1"\texttt{"1 1 6 1"}:将区间 [1,6][1, 6] 的值修改为 11,序列变为 {1,1,1,1,1,1}\{1, 1, 1, 1, 1, 1\};

∙ \hspace{23pt}\bullet\,执行 "2 1 6"\texttt{"2 1 6"}:区间 [1,6][1, 6] 的元素之和为 66;

∙ \hspace{23pt}\bullet\,执行 "2 5 6"\texttt{"2 5 6"}:区间 [5,6][5, 6] 的元素之和为 22。

\hspace{15pt}因此依次输出 30,9,6,230, 9, 6, 2。

提示

\hspace{15pt}对于全部数据,1≦n,m≦5×1051 \leqq n, m \leqq 5 \times 10^5,1≦ai,x≦1091 \leqq a_i, x \leqq 10^9,1≦l≦r≦n1 \leqq l \leqq r \leqq n。

\hspace{15pt}保证所有数据随机生成。