首页 > 试题广场 >

区间 (interval)

[编程题]区间 (interval)

Apojacsleam喜欢数组。

他现在有一个n个元素的数组a，而他要对a[L]-a[R]进行M次操作：

操作一：将a[L]-a[R]内的元素都加上P

操作二：将a[L]-a[R]内的元素都减去P

最后询问a[l]-a[r]内的元素之和？

请认真看题干及输入描述。

输入共M+3行：

第一行两个数，n，M，意义如“题目描述”

第二行n个数，描述数组。

第3-M+2行，共M行，每行四个数，q，L，R，P，若q为1则表示执行操作2，否则为执行操作1

第4行，两个正整数l，r

一个正整数，为a[l]-a[r]内的元素之和

示例1

输入

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

，所有输入数据都在 int 范围内

算法知识视频讲解

小琢卷不动

发表于 2021-11-24 10:56:27

看完题第一反应线段树。然后 copy 了一个朴素板子过来发现数据范围 10610^6106，怀疑出题人可能卡常。然后就想到了 zkw 的非递归式写法，常数很小。复制完了模板之后反应过来好像可以差分数组 O(n)O(n)O(n) 做（大雾）线段树做法不讲了，来说说差分数组：设 d[i]=a 展开全文

离散化

难度：

0条回答 0收藏 55浏览

查看代码

区间 (interval)

扫一扫，把题目装进口袋