D-势能线段树模板题一_牛客竞赛数据结构专题班势能线段树、李超线段树（重现赛）@IR101

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

智乃酱最近在学习势能线段树

对于势能线段树，假设线段树的节点数为 ${N}$ ，操作数目为 ${M}$ 。

则势能线段树则总时间复杂度为 ${O(M \times |0势能时线段树操作时间复杂度|+N\times |节点势能上限降低至0势能时间复杂度|)}$ 。

使用势能线段树时要定义势能、势能初始值（势能最大值）、0势能点。

本题中有两种可以定义势能与0势能的方法，你可以都尝试一下。

--------------------------------------------------------------------------------------------------------------------------

给你一个长度大小为 ${N}$ 的正整数数组，进行 ${M}$ 次操作，操作有下列两种。

给定区间 ${[l,r]}$ 对区间中所有数字开根号向下取整，即 $a_i= \lfloor \sqrt{a_i} \rfloor(l \leq i \leq r)$ 。
查询给定区间 ${[l,r]}$ 的元素和，即求 $\sum_{i=l}^{r}a_{i}$ 。

第一行输入两个正整数。
接下来一行输入个正整数。
接下来行，每行输入三个正整数。
当时，表示操作一，对区间开根号向下取整。
当时，表示操作二，求区间的区间和。

对于每一个当，输出区间和。

示例1

复制

10 3
10 10 10 10 10 10 10 10 10 10
2 1 10
1 1 5
2 1 10

复制

100
65