#6099. 花神游历各国

题目描述

有一个长度为 $n$ 的序列，初始给出 $n$ 个正整数。
有两种操作：

1. 1 l r：查询区间 $[l, r]$ 中所有数的和。
2. 2 l r：将区间 $[l, r]$ 中每个数 $x$ 变为 $\lfloor \sqrt{x} \rfloor$（下取整开平方）。

给出 $m$ 次操作，对于每个查询输出结果。

输入格式

第一行一个整数 $n$。
第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$。
第三行一个整数 $m$。
接下来 $m$ 行，每行三个整数 $k\ l\ r$，表示一次操作。

输出格式

对于每个查询操作，输出一行，表示区间和。

样例

输入

10
1 2 3 4 5 6 7 8 9 10
5
2 1 10
1 1 10
1 1 5
2 5 8
1 4 8

输出

19
7
6

解释

• 初始：$[1,2,3,4,5,6,7,8,9,10]$
• 操作 1：对 $[1,10]$ 开平方 → $[1,1,1,2,2,2,2,2,3,3]$，和 $=1+1+1+2+2+2+2+2+3+3=19$
• 操作 2：查询 $[1,5]$ 和 $=1+1+1+2+2=7$
• 操作 3：对 $[5,8]$ 开平方（$[2,2,2,2]$ 变为 $[1,1,1,1]$）
• 操作 4：查询 $[4,8]$ → $[2,1,1,1,1]$ 和 $=2+1+1+1+1=6$

数据范围与提示

• $1 \le n \le 10^5$
• $1 \le m \le 2 \times 10^5$
• $0 \le a_i \le 10^9$

由于 $a_i$ 最大 $10^9$，对一个数不断开平方，只需 $O(\log \log a_i)$ 次就会变为 $1$（之后不再变化）。可以利用这个性质优化区间修改操作。