P0067 区间推平
题目描述
维护一个长度为 n 的序列 {a1,a2,…,an},共有 m 次操作。操作共有 2 种:
∙区间推平:将区间 [l,r] 中所有元素的值修改为 x;
∙区间求和:询问区间 [l,r] 中所有元素之和。
由于答案可能很大,区间求和的答案需要对 232 取模后输出。
保证所有数据随机生成。
输入格式
第一行输入两个整数 n,m(1≦n,m≦5×105) 代表序列长度与操作次数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$ 代表序列的初始元素。
此后 m 行,每行输入一个操作。每行先输入一个整数 op(1≦op≦2) 代表操作类型,随后在同一行:
∙若 op=1,输入三个整数 $l, r, x \left(1 \leqq l \leqq r \leqq n;\ 1 \leqq x \leqq 10^9\right)$ 代表将区间 [l,r] 的值修改为 x;
∙若 op=2,输入两个整数 l,r(1≦l≦r≦n) 代表询问区间 [l,r] 的元素之和。
输出格式
对于每次操作 2,在一行上输出一个整数,代表区间 [l,r] 的元素之和对 232 取模后的结果。
测试样例
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 解释
初始序列为 {1,2,3,4,5},操作过程如下:
∙执行 "2 1 5":区间 [1,5] 的元素之和为 1+2+3+4+5=15;
∙执行 "1 2 3 4":将区间 [2,3] 的值修改为 4,序列变为 {1,4,4,4,5};
∙执行 "2 1 5":区间 [1,5] 的元素之和为 1+4+4+4+5=18;
∙执行 "2 3 3":区间 [3,3] 的元素之和为 4;
∙执行 "2 2 4":区间 [2,4] 的元素之和为 4+4+4=12。
因此依次输出 15,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 解释
初始序列为 {7,7,2,9,4,1},操作过程如下:
∙执行 "2 1 6":区间 [1,6] 的元素之和为 7+7+2+9+4+1=30;
∙执行 "1 2 5 3":将区间 [2,5] 的值修改为 3,序列变为 {7,3,3,3,3,1};
∙执行 "2 2 4":区间 [2,4] 的元素之和为 3+3+3=9;
∙执行 "1 1 6 1":将区间 [1,6] 的值修改为 1,序列变为 {1,1,1,1,1,1};
∙执行 "2 1 6":区间 [1,6] 的元素之和为 6;
∙执行 "2 5 6":区间 [5,6] 的元素之和为 2。
因此依次输出 30,9,6,2。
提示
对于全部数据,1≦n,m≦5×105,1≦ai,x≦109,1≦l≦r≦n。
保证所有数据随机生成。