势能线段树模板题二

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

题目描述

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

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

若势能可被某种操作重置或者增加，则必须考虑最坏情况下能够提供操作总数 ${M}$ *|单次操作重置势能的节点总数|*|节点势能上限|的时间复杂度。

则势能线段树则总时间复杂度为 ${O(M \times |0势能时线段树操作时间复杂度|+N\times |节点势能上限降低至0势能时间复杂度|+M\times |线段树单次操作影响到的节点数目|\times|操作额外提供的势能|)}$ 。

一般来讲，在使用lazy_tag的情况下， |线段树单次操作影响到的节点数目|就是 ${logN}$ ，本题中节点势能上限近似是个 ${logN}$ （其实是6）所以总复杂度是 ${Mlog^2N}$ 级别的。

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

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

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

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

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

第一行输入两个正整数。
接下来一行输入个正整数。
接下来行，每行首先输入一个正整数。
当时，表示操作一，然后继续输入两个正整数表示对区间开根号向下取整。
当时，表示操作二，然后继续输入三个正整数表示给区间加上一个正整数。
当时，表示操作二，然后继续输入两个正整数表示求区间的区间和。

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

示例1

复制

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

复制

100
65

示例2

复制

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

复制