poj3468(线段树区间更新)

题目链接

解题说明：

裸题模板

ac代码：

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int MAXN=1e5+10;
typedef long long ll;
ll s[MAXN<<2],col[MAXN<<2];
void up(int p){
s[p]=s[p*2]+s[p*2+1];
}
void down(int p,int l,int r){
if(col[p]){
int mid=(l+r)/2;
s[p*2]+=(ll)col[p]*(mid-l+1);
s[p*2+1]+=(ll)col[p]*(r-mid);
col[p*2]+=col[p];
col[p*2+1]+=col[p];
col[p]=0;
}
}
void modify(int p,int l,int r,int x,int y,ll c){
if(x<=l&&y>=r){
s[p]+=(ll)c*(r-l+1);
col[p]+=(ll)c;
return;
}
down(p,l,r);
int mid=(l+r)/2;
if(x<=mid){
modify(p*2,l,mid,x,y,c);
}
if(y>mid){
modify(p*2+1,mid+1,r,x,y,c);
}
up(p);
}
ll query(int p,int l,int r,int x,int y){
if(x<=l&&y>=r){
return s[p];
}
down(p,l,r);
int mid=(l+r)/2;
ll res=0;
if(x<=mid){
res+=query(p*2,l,mid,x,y);
}
if(y>mid){
res+=query(p*2+1,mid+1,r,x,y);
}
return res;
}
int main(){
int n,m;
ios::sync_with_stdio(false);
cin>>n>>m;
int ip1,ip2;
ll ip3;
for(int i=1;i<=n;i++){
cin>>ip1;
modify(1,1,n,i,i,ip1);
}
string op;
for(int i=1;i<=m;i++){
cin>>op;
if(op=="Q"){
cin>>ip1>>ip2;
cout<<query(1,1,n,ip1,ip2)<<endl;
}
else {
cin>>ip1>>ip2>>ip3;
modify(1,1,n,ip1,ip2,ip3);
}
}
return 0;
}

最后

以上就是谦让早晨为你收集整理的poj3468(线段树区间更新)的全部内容，希望文章能够帮你解决poj3468(线段树区间更新)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。