首页 > 代码库 > (简单) POJ 3468 A Simple Problem with Integers , 线段树+区间更新。
(简单) POJ 3468 A Simple Problem with Integers , 线段树+区间更新。
Description
You have N integers, A1, A2, ... , 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.
题意很好理解，就是标准的线段树区间更新问题，可以说是模板。
不过因为写的不熟练，被坑了两个WA，错的地方在代码里标出来了。。。
代码如下：
#include<iostream>#include<cstdio>#define lson L,M,po*2#define rson M+1,R,po*2+1using namespace std;long long BIT[100005*4];long long COL[100005*4];void pushUP(int po){ BIT[po]=BIT[po*2]+BIT[po*2+1];}void pushDown(int po,int len){ if(COL[po]) { BIT[po*2]+=(long long)COL[po]*(len-(len/2)); BIT[po*2+1]+=(long long)COL[po]*(len/2); COL[po*2]+=COL[po]; //注意是+=，不是= ！！！ COL[po*2+1]+=COL[po]; COL[po]=0; }}void build_tree(int L,int R,int po){ if(L==R) { COL[po]=0; cin>>BIT[po]; return; } int M=(L+R)/2; build_tree(lson); build_tree(rson); pushUP(po);}long long query(int ql,int qr,int L,int R,int po){ if(ql<=L&&qr>=R) return BIT[po]; pushDown(po,(R-L+1)); int M=(L+R)/2; if(qr<=M) return query(ql,qr,lson); if(ql>M) return query(ql,qr,rson); return query(ql,qr,rson)+query(ql,qr,lson);}void update(int ul,int ur,int add,int L,int R,int po){ if(ul<=L&&ur>=R) { BIT[po]+=(long long)add*(R-L+1); COL[po]+=(long long)add; return; } pushDown(po,R-L+1); int M=(L+R)/2; if(ul<=M) update(ul,ur,add,lson); if(ur>M) update(ul,ur,add,rson); pushUP(po);}int main(){ int N,Q; char C; int a,b,c; while(~scanf("%d %d",&N,&Q)) { build_tree(1,N,1); for(int i=0;i<Q;++i) { cin>>C; if(C==‘Q‘) { scanf("%d %d",&a,&b); cout<<query(a,b,1,N,1)<<endl; } else { scanf("%d %d %d",&a,&b,&c); update(a,b,c,1,N,1); } } } return 0;}
(简单) POJ 3468 A Simple Problem with Integers , 线段树+区间更新。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。