Poj(3468)——A Simple Problem with Integers(线段树)
发布日期:2021-09-19 06:09:09 浏览次数:17 分类:技术文章

本文共 3337 字,大约阅读时间需要 11 分钟。

A Simple Problem with Integers
Time Limit: 5000MS   Memory Limit: 131072K
Total Submissions: 72424   Accepted: 22343
Case Time Limit: 2000MS

Description

You have N integers, A1A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.

The second line contains N numbers, the initial values of A1A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of AaAa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of AaAa+1, ... , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 4

Sample Output

455915

这道题的大致题目意思是:

首先给你两个整数N,Q;N代表的是你有几个数,然后Q代表的是有几个操作:

然后只有两种操作类型,"C a b c"代表的意思是:给A[a]到A[b]的数都加上一个数c。 "Q a b”的意思是让你求下标为a到b的和。

线段树裸题,但是是第一次做,所以还是写写吧,而且网上线段树模板鱼龙混杂,我也是费了好大力气才找到一个适合我的模板的。

在此附上链接:http://www.tuicool.com/articles/BVVfi2E

如果不懂线段树的可以先去学习一下上面那个人写的内容然后这道题我想就很简单了吧。

这道线段树的题,我总共写了三遍,但是每一遍都会产生不同的错误,总共错了 两次,但是在写的过程中渐渐的找到了适合自己的写法,我想还是要总结一下:

1.总是会忘记打pushup和pushdown,或者说分不太清楚什么时候应该用什么函数,但是就我最近做过的题来看,当建立一棵线段树时,最后是要加上pushup的,因为你要把上面的结点也得更新到啊。

然后,update的时候,如果像是区间更新的问题的话,如果父节点上还带有lazy标志的话,那么就要pushdown,因为你要把那个lazy标志传下去。但是update的最后,因为你更新完了,所以你还要再继续pushup,别忘了把父节点也更新了。

2.是小问题,但是也是致命的问题,就是我经常会忘记打符号,比如说一个数在原来的基础上再加上一个数x,那么不是tree[v].x+=x吗,但是我有时候会不小心忘记打+号,这个问题虽然小,但是小的地方最难查,所以还是要注重细节!!!

以下是写了三遍之后个人认为比较满意的代码:

#include
#include
#include
#include
using namespace std;#define maxn 111111typedef long long ll;ll sum=0;ll a[maxn];struct node{ int l,r; ll x,add;}tree[maxn*4];void pushup(int v){ int temp=v<<1; tree[v].x=tree[temp].x+tree[temp+1].x;}void pushdown(int v){ int temp=v<<1; tree[temp].add+=tree[v].add; tree[temp+1].add+=tree[v].add; tree[temp].x+=tree[v].add*(tree[temp].r-tree[temp].l+1); tree[temp+1].x+=tree[v].add*(tree[temp+1].r-tree[temp+1].l+1); tree[v].add=0;}void build(int v,int l,int r){ tree[v].l=l; tree[v].r=r; tree[v].add=0; tree[v].x=0; if(l==r){ tree[v].x=a[l]; return ; } int mid=(l+r)>>1; int temp=v<<1; build(temp,l,mid); build(temp+1,mid+1,r); pushup(v);}void query(int v,int l,int r){ if(tree[v].l==l&&tree[v].r==r){ sum+=tree[v].x; return; } if(tree[v].add) pushdown(v); int mid=(tree[v].l+tree[v].r)>>1; int temp=v<<1; if(r<=mid) query(temp,l,r); else if(l>mid) query(temp+1,l,r); else{ query(temp,l,mid); query(temp+1,mid+1,r); }}void update(int v,int l,int r,int x){ if(tree[v].l==l&&tree[v].r==r){ tree[v].add+=x; tree[v].x+=x*(tree[v].r-tree[v].l+1); return ; } if(tree[v].add) pushdown(v); int mid=(tree[v].l+tree[v].r)>>1; int temp=v<<1; if(r<=mid) update(temp,l,r,x); else if(l>mid) update(temp+1,l,r,x); else{ update(temp,l,mid,x); update(temp+1,mid+1,r,x); } pushup(v); //!!!}int main(){ int n,Q; char ss[5]; scanf("%d%d",&n,&Q); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,1,n); while(Q--){ int a,b,c; scanf("%s",ss); if(ss[0]=='C'){ scanf("%d%d%d",&a,&b,&c); update(1,a,b,c); } else if(ss[0]=='Q'){ sum=0; scanf("%d%d",&a,&b); query(1,a,b); printf("%lld\n",sum); } }}

没有什么新的东西是刚开始就能够得心应手的,所以慢慢的进步吧,加油,hades!

转载地址:https://blog.csdn.net/ACMer_hades/article/details/46274825 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:Poj(2352)——Stars(树状数组)
下一篇:Poj(2182)——Lost Cows(线段树)

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月03日 05时49分00秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

android 动态毛玻璃,Android毛玻璃背景效果简单实现代码 2019-04-21
android 按钮提示,的Android按钮工具提示 2019-04-21
iphone通讯录 android,3个方法,教你如何快速而又有效的将联系人从iPhone转移到安卓... 2019-04-21
android horizontalscrollview 滑动事件,ScrollView的滑动监听(以HorizontalScrollView为例) 2019-04-21
win7自定义html为桌面,Win7系统自定义桌面主题的方法 2019-04-21
单系统 台电x80pro_台电x80 pro (ID:E3E6)安装remix OS系统教程整理 2019-04-21
linux存储pdf伟岸_python的reportlab库介绍、制作pdf和作图 2019-04-21
安徽信息技术初中会考上机考试模拟_2020年中小学寒假、考试时间定下了! 2019-04-21
ubuntu 退出anaconda环境_从零开始深度学习第15讲:ubuntu16.04 下深度学习开发环境搭建与配置... 2019-04-21
稳定币usda是哪个发行的_武夷山币装帧款曝光,共4款设计,你喜欢哪款? 2019-04-21
可变车道怎么走不违章_走ETC竟比人工车道贵50%!交警:这3点不知道,吃亏的是自己... 2019-04-21
苹果笔记本的end键_笔记本用户的大烦恼:触控板,想好好用你不容易 2019-04-21
趣玩机器人什么时候成立的_【直播回顾】当我们谈机器人集成调试的时候在谈什么... 2019-04-21
中考大数据大连79_中考大数据 | 大连部分初中2019年中考指标生录取最低分及人数统计!... 2019-04-21
vue 地理位置定位_HTML5地理位置 2019-04-21
pac代理模式什么意思_托管仓库租赁电商仓储运营模式托管什么意思 2019-04-21
validated 验证数组_在 Laravel 中处理请求验证的智能方法 2019-04-21
洞泾智能机器人产业基地_G60科创走廊洞泾人工智能产业基地(核心区块)暨洞泾镇招商人员培训班顺利开班... 2019-04-21
java 拼接路径优雅方式_Java安全编码实践总结 2019-04-21
realme x2 深度测试打不开_搭载65W超级闪充,realme真我X7手机充电评测 2019-04-21