序列操作

2019-11-06 06:09:59

字体：大中小

来源：转载

供稿：网友

题目描述

给出一个N个元素的正整数序列，现在有两种操作:

修改操作:给一段区间的每一个数加上一个正整数x查询操作:查询序列中当前第x个元素的值。

请写一个程序实现这两种操作。第一行，一个数N 第二行N个数，表示初始的序列，接下来一行一个数M，表示操作次数接下来M行，每行一个操作:

lrx表示把l到r的每一个数加上xx表示查询第x个元素的值

输入

第一行，一个数N 第二行N个数，表示初始的序列，接下来一行一个数M，表示操作次数接下来M行，每行一个操作:

lrx表示把l到r的每一个数加上xx表示查询第x个元素的值

输出

对于每一个查询操作输出一行结果

样例输入

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

样例输出

3 4

提示

数据范围

N, M <= 100000，初始数列中每个元素不超过1000，修改操作中的x不超过1000

分析

个人觉得这点题有点像 HDU 1556 的“小飞鸽”。它和树状数组有一些不同，就是是区间求和，所以面对这一问题，我们也可以把它做成“小飞鸽”那道题的样子。 “小飞鸽”那道题的意思是区间计算，而这道题只需要计算一个点，so。。。

初始化就不说了吧。我们先把初始的数据存起来，后面不用再处理的，或者update，否则很麻烦的，直接拿区间和加上即可。所以这道题的update就是针对一个区间的了。 update根据容斥原理，要让[l,r]区间的值增加x，就先把前r个地方的值加上x，再把前l个地方的值减去x，就行了。O(∩_∩)O哈哈哈~ 读入指令类型，如果是1，就区间更新值；如果是2，就先把树状数组的和求出来，再加上初始值即可。。。

源代码

#include<cstdio>#define lowbit(a) a&-aint n,arr[100005],a[100005];void update(int i,int d){ while(i<=n){ arr[i]+=d; i+=lowbit(i); }}int getsum(int i){ int s=0; while(i){ s+=arr[i]; i-=lowbit(i); } return s;}int main(){ int m,x,l,r,o; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%d",&o); if(o==1){ scanf("%d%d%d",&l,&r,&x); update(l,x); update(r+1,-x); } else{ scanf("%d",&x); PRintf("%d/n",getsum(x)+a[x]); } }}

上一篇：1054. 求平均值 (20)

下一篇：1046. 划拳(15)

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注