给出一个长为 n 的数列,以及 n 个操作,操作涉及区间加法,单点查值。 输入格式 第一行输入一个数字 n。 第二行输入 n 个数字,第 i 个数字为 a i ,以空格隔开。 接下来输入 n 行询问,每行输入四个数字 o p t opt、 l、 r、 c,以空格隔开。 若 o p t = 0 opt=0,表示将位于 [ , ] [l,r] 的之间的数字都加 c。 若 o p t = 1 opt=1,表示询问 a r 的值( l 和 c 忽略)。用差分做
时间: 2023-05-28 09:01:37 浏览: 59
题目描述
给出一个长为 $n$ 的数列,以及 $n$ 个操作,操作涉及区间加法,单点查值。
输入格式
第一行输入一个数字 $n$。
第二行输入 $n$ 个数字,第 $i$ 个数字为 $a_i$,以空格隔开。
接下来输入 $n$ 行询问,每行输入四个数字 $opt$、$l$、$r$、$c$,以空格隔开。
若 $opt=0$,表示将位于 $[l,r]$ 之间的数字都加 $c$。
若 $opt=1$,表示询问 $a_r$ 的值($l$ 和 $c$ 忽略)。
输出格式
对于每一个 $opt=1$ 的操作,输出一个查询结果,每行输出一个。
注意:不要输出任何多余的字符。
数据范围
$0\leq n\leq 10^5,0\leq a_i,c\leq 10^6,-10^6\leq l,r\leq 10^6$
样例
输入样例:
5
1 2 3 4 5
1 3 5
0 2 5 1
1 5 0
1 2 0
输出样例:
5
6
方法 1 差分
差分:差分可以对数组进行区间增减操作,减少时间复杂度,达到线性
1 4 3 7 8 6 原始数组
0 3 -1 4 1 -2 差分数组
0 3 2 6 7 5 差分数组前缀和。即原数组。
关于差分:差分 就是: 对原始数组的相邻两个元素进行一个前者减后者的操作,将得到的结果构成的数组成为 差分数组
将差分数组求前缀和就回到了原数组
C++ 代码
相关问题
给出一个长为 n 的数列,以及 n 个操作,操作涉及区间加法,单点查值。 输入格式 第一行输入一个数字 n。 第二行输入 n 个数字,第 i 个数字为 a i ,以空格隔开。 接下来输入 n 行询问,每行输入四个数字 o p t opt、 l、 r、 c,以空格隔开。 若 o p t = 0 opt=0,表示将位于 [ , ] [l,r] 的之间的数字都加 c。 若 o p t = 1 opt=1,表示询问 a r 的值( l 和 c 忽略)。用C++做出来
题目描述
给出一个长为 n 的数列,以及 n 个操作,操作涉及区间加法,单点查值。
输入格式
第一行输入一个数字 n。
第二行输入 n 个数字,第 i 个数字为 ai ,以空格隔开。
接下来输入 n 行询问,每行输入四个数字 opt、l、r、c,以空格隔开。
若 opt=0,表示将位于[l,r]之间的数字都加c。
若 opt=1,表示询问 ai 的值(l和c忽略)。
输出格式
对于每个查询,输出一个整数表示结果,每个结果占一行。
样例输入
5
1 2 3 4 5
1 1 1 0
1 2 2 1
1 3 3 2
1 4 4 3
1 5 5 4
样例输出
1
3
5
7
9
算法1
(树状数组) $O(nlogn)$
树状数组做区间修改,单点查询
时间复杂度
树状数组做区间修改,单点查询,时间复杂度为 $O(nlogn)$
C++ 代码
算法2
(线段树) $O(nlogn)$
线段树做区间修改,单点查询
时间复杂度
线段树做区间修改,单点查询,时间复杂度为 $O(nlogn)$
C++ 代码
定义一个fibonacci数列函数,从键盘输入一个整数n,求第n项的fibonacci数列值
题目要求编写一个 Fibonacci 数列的函数,通过输入一个整数 n,在 Fibonacci 数列中找到第 n 项的值。
Fibonacci 数列是指:前两项是 0 和 1,从第三项开始,每一项都等于前两项的和。
因此,我们可以使用递归方式来找到第 n 项的值,具体步骤如下:
1. 如果 n 等于 0,返回 0;
2. 如果 n 等于 1,返回 1;
3. 如果 n 大于 1,返回第 n-1 项和第 n-2 项的和。
代码如下所示:
```python
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
# 测试一下
print(fibonacci(0)) # 0
print(fibonacci(1)) # 1
print(fibonacci(2)) # 1
print(fibonacci(3)) # 2
print(fibonacci(4)) # 3
print(fibonacci(5)) # 5
```
输出结果为:
```
0
1
1
2
3
5
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)