P13980 数列分块入门 5
题目描述
给定一个长度为 n 的数列 {a1,a2,…,an}。接下来需要依次执行 n 次操作,操作分为以下两种:
∙开方操作:给定区间 [l,r],将区间内的每个数 ai 都变为 ⌊ai⌋,其中 ⌊x⌋ 表示不超过 x 的最大整数;
∙求和操作:给定区间 [l,r],求出区间内所有数之和 i=l∑rai。
对于每个求和操作,输出对应的结果。
输入格式
第一行输入一个整数 n(1≦n≦3×105) 代表数列的长度,同时也是操作次数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(0 \leqq a_i \leqq 2^{31}-1\right)$ 代表数列中的元素。
此后 n 行,第 i 行输入三个整数 $\mathrm{opt}_i, l_i, r_i \left(\mathrm{opt}_i \in \{0, 1\};\ 1 \leqq l_i \leqq r_i \leqq n\right)$ 代表第 i 次操作。其中 opti=0 表示对区间 [li,ri] 执行开方操作,opti=1 表示对区间 [li,ri] 执行求和操作。
输出格式
对于每个求和操作,新起一行输出一个整数,代表该次查询的区间和。保证每个答案都不超过 263−1。
测试样例
4
1 2 2 3
0 1 3
1 1 4
0 1 2
1 1 2
6
2
样例 1 解释
初始时,数列为 {1,2,2,3}。
∙第一次操作对区间 [1,3] 开方,a1=1、a2=2、a3=2 分别变为 1,1,1,数列变为 {1,1,1,3};
∙第二次操作查询区间 [1,4] 的元素和,得到 1+1+1+3=6;
∙第三次操作对区间 [1,2] 开方,a1=1、a2=1 开方后仍为 1,数列保持 {1,1,1,3};
∙第四次操作查询区间 [1,2] 的元素和,得到 1+1=2。
6
0 1 4 9 16 2
1 1 6
0 2 4
1 1 6
0 3 6
0 1 6
1 1 6
32
24
6
样例 2 解释
初始时,数列为 {0,1,4,9,16,2}。
∙第一次操作查询区间 [1,6] 的元素和,得到 0+1+4+9+16+2=32;
∙第二次操作对区间 [2,4] 开方,1,4,9 分别变为 1,2,3,数列变为 {0,1,2,3,16,2};
∙第三次操作查询区间 [1,6] 的元素和,得到 0+1+2+3+16+2=24;
∙第四次操作对区间 [3,6] 开方,2,3,16,2 分别变为 1,1,4,1,数列变为 {0,1,1,1,4,1};
∙第五次操作对区间 [1,6] 开方,数列变为 {0,1,1,1,2,1};
∙第六次操作查询区间 [1,6] 的元素和,得到 0+1+1+1+2+1=6。
提示
本系列的测试数据范围与原题不同。
本题共有两个子任务:
∙子任务 1(40 分):1≦n≦5×104,0≦ai≦231−1,0≦ans≦231−1;
∙子任务 2(60 分):1≦n≦3×105,0≦ai≦231−1,0≦ans≦263−1。
其中 ans 表示每次求和操作的答案。对于所有测试数据,每次操作后的 ai 都满足 0≦ai≦231−1。