LG#P13980. 数列分块入门 5

数列分块入门 5

P13980 数列分块入门 5

题目描述

\hspace{15pt}给定一个长度为 nn 的数列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\}。接下来需要依次执行 nn 次操作,操作分为以下两种:

∙ \hspace{23pt}\bullet\,开方操作:给定区间 [l,r][l, r],将区间内的每个数 aia_i 都变为 ⌊ai⌋\left\lfloor \sqrt{a_i} \right\rfloor,其中 ⌊x⌋\lfloor x \rfloor 表示不超过 xx 的最大整数;

∙ \hspace{23pt}\bullet\,求和操作:给定区间 [l,r][l, r],求出区间内所有数之和 ∑i=lrai\sum\limits_{i=l}^{r} a_i。

\hspace{15pt}对于每个求和操作,输出对应的结果。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦3×105)n \left(1 \leqq n \leqq 3 \times 10^5\right) 代表数列的长度,同时也是操作次数。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(0 \leqq a_i \leqq 2^{31}-1\right)$ 代表数列中的元素。

\hspace{15pt}此后 nn 行,第 ii 行输入三个整数 $\mathrm{opt}_i, l_i, r_i \left(\mathrm{opt}_i \in \{0, 1\};\ 1 \leqq l_i \leqq r_i \leqq n\right)$ 代表第 ii 次操作。其中 opti=0\mathrm{opt}_i = 0 表示对区间 [li,ri][l_i, r_i] 执行开方操作,opti=1\mathrm{opt}_i = 1 表示对区间 [li,ri][l_i, r_i] 执行求和操作。

输出格式

\hspace{15pt}对于每个求和操作,新起一行输出一个整数,代表该次查询的区间和。保证每个答案都不超过 263−12^{63}-1。

测试样例

4
1 2 2 3
0 1 3
1 1 4
0 1 2
1 1 2
6
2

样例 1 解释

\hspace{15pt}初始时,数列为 {1,2,2,3}\{1, 2, 2, 3\}。

∙ \hspace{23pt}\bullet\,第一次操作对区间 [1,3][1, 3] 开方,a1=1a_1=1、a2=2a_2=2、a3=2a_3=2 分别变为 1,1,11, 1, 1,数列变为 {1,1,1,3}\{1, 1, 1, 3\};

∙ \hspace{23pt}\bullet\,第二次操作查询区间 [1,4][1, 4] 的元素和,得到 1+1+1+3=61+1+1+3=6;

∙ \hspace{23pt}\bullet\,第三次操作对区间 [1,2][1, 2] 开方,a1=1a_1=1、a2=1a_2=1 开方后仍为 11,数列保持 {1,1,1,3}\{1, 1, 1, 3\};

∙ \hspace{23pt}\bullet\,第四次操作查询区间 [1,2][1, 2] 的元素和,得到 1+1=21+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 解释

\hspace{15pt}初始时,数列为 {0,1,4,9,16,2}\{0, 1, 4, 9, 16, 2\}。

∙ \hspace{23pt}\bullet\,第一次操作查询区间 [1,6][1, 6] 的元素和,得到 0+1+4+9+16+2=320+1+4+9+16+2=32;

∙ \hspace{23pt}\bullet\,第二次操作对区间 [2,4][2, 4] 开方,1,4,91, 4, 9 分别变为 1,2,31, 2, 3,数列变为 {0,1,2,3,16,2}\{0, 1, 2, 3, 16, 2\};

∙ \hspace{23pt}\bullet\,第三次操作查询区间 [1,6][1, 6] 的元素和,得到 0+1+2+3+16+2=240+1+2+3+16+2=24;

∙ \hspace{23pt}\bullet\,第四次操作对区间 [3,6][3, 6] 开方,2,3,16,22, 3, 16, 2 分别变为 1,1,4,11, 1, 4, 1,数列变为 {0,1,1,1,4,1}\{0, 1, 1, 1, 4, 1\};

∙ \hspace{23pt}\bullet\,第五次操作对区间 [1,6][1, 6] 开方,数列变为 {0,1,1,1,2,1}\{0, 1, 1, 1, 2, 1\};

∙ \hspace{23pt}\bullet\,第六次操作查询区间 [1,6][1, 6] 的元素和,得到 0+1+1+1+2+1=60+1+1+1+2+1=6。

提示

\hspace{15pt}本系列的测试数据范围与原题不同。

\hspace{15pt}本题共有两个子任务:

∙ \hspace{23pt}\bullet\,子任务 1(40 分):1≦n≦5×1041 \leqq n \leqq 5 \times 10^4,0≦ai≦231−10 \leqq a_i \leqq 2^{31}-1,0≦ans≦231−10 \leqq \mathrm{ans} \leqq 2^{31}-1;

∙ \hspace{23pt}\bullet\,子任务 2(60 分):1≦n≦3×1051 \leqq n \leqq 3 \times 10^5,0≦ai≦231−10 \leqq a_i \leqq 2^{31}-1,0≦ans≦263−10 \leqq \mathrm{ans} \leqq 2^{63}-1。

\hspace{15pt}其中 ans\mathrm{ans} 表示每次求和操作的答案。对于所有测试数据,每次操作后的 aia_i 都满足 0≦ai≦231−10 \leqq a_i \leqq 2^{31}-1。