UOJ Logo Universal Online Judge

UOJ

#228. 基础数据结构练习题

统计

sylvia 是一个热爱学习的女孩子,今天她想要学习数据结构技巧。

在看了一些博客学了一些姿势后,她想要找一些数据结构题来练练手。于是她的好朋友九条可怜酱给她出了一道题。

给出一个长度为 $n$ 的数列 $A$,接下来有 $m$ 次操作,操作有三种:

  1. 对于所有的 $i \in [l,r]$,将 $A_i$ 变成 $A_i+x$。
  2. 对于所有的 $i \in [l,r]$,将 $A_i$ 变成 $\lfloor \sqrt {A_i} \rfloor$。
  3. 对于所有的 $i \in [l,r]$,询问 $A_i$ 的和。

作为一个不怎么熟练的初学者,sylvia 想了好久都没做出来。而可怜酱又外出旅游去了,一时间联系不上。于是她决定向你寻求帮助:你能帮她解决这个问题吗。

输入格式

第一行两个数:$ n, m $。

接下来一行 $ n $ 个数 $A_i$。

接下来 $ m $ 行中,第 $ i $ 行第一个数 $ t_i $ 表示操作类型:

若 $ t_i = 1 $,则接下来三个整数 $ l_i, r_i, x_i $,表示操作一。

若 $ t_i = 2 $,则接下来三个整数 $ l_i, r_i$,表示操作二。

若 $ t_i = 3 $,则接下来三个整数 $ l_i, r_i$,表示操作三。

输出格式

对于每个询问操作,输出一行表示答案。

样例一

input

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

output

5
6

样例二

见样例数据下载。

限制与约定

测试点编号$n$ 的规模$m$ 的规模其他约定
1$n \leq 3000$$m \leq 3000$
2
3
4$n \leq 100000$$m \leq 100000$数据随机生成
5
6$t_i \neq 1$
7
8
9
10

对于所有数据,保证有 $1 \leq l_i \leq r_i \leq n,1 \leq A_i,x_i \leq 10^5$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载