5003 - 【模板】根号线段树

给定一个长度为n的序列a_1,a_2,\cdots,a_n,你需要维护m个操作,每个操作都是其中一个:

  1. 将区间[l,r]每个数都加上k
  2. 将区间[l,r]每个数都开平方根(向下取整)
  3. 求出区间[l,r]内每个数之和

输入

第一行包含两个整数n,m,分别表示该数列数字的个数和操作的总个数。

第二行包含n个用空格分隔的整数,其中第i个数字表示a_i

接下来m行,每行包含34个整数,表示一个操作,具体如下:

  1. 1 l r k:将区间[l,r]内每个数加上 k
  2. 2 l r:将区间[l,r]每个数都改成开平方根(向下取整)。
  3. 3 l r:输出区间[l,r]内每个数的和。

输出

输出包含若干行整数,即为所有操作3的结果。

样例

输入

5 5 
9 3 5 3 5
3 1 4
1 1 3 2
3 1 4
2 2 5
3 1 4

输出

20
26
16

提示

1\leq n,m\leq10^5,1\leq a_i,k\leq 10^5

没有部分分!

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题