POJ3468(用lazy标记进行延迟更新)

#include<stdio.h>
#define mid (l+r)/2
#define lson o*2,l,mid
#define rson o*2+1,mid+1,r
typedef long long ll;
const int N=1e5+100;
ll lazy[4*N],tree[4*N];int a[N];
void build(int o,int l,int r){
if(l==r){
tree[o]=a[l];
return ;
}
build(lson),build(rson);
tree[o]=tree[o*2]+tree[o*2+1];
}
int ql,qr;ll v;
void pushdown(int o,int m){
if(!lazy[o])return;
ll lz=lazy[o];
lazy[o*2]+=lz,lazy[o*2+1]+=lz,lazy[o]=0;
tree[o*2]+=lz*(m-m/2),tree[o*2+1]+=lz*(m/2);
}//线段树左边区间更长一些 
void updata(int o,int l,int r){
if(ql<=l&&r<=qr){
tree[o]+=(r-l+1)*v;
lazy[o]+=v;
return ;
}
pushdown(o,r-l+1);
if(ql<=mid) updata(lson);
if(qr>mid)	updata(rson);
tree[o]=tree[o*2]+tree[o*2+1];
}
ll query(int o,int l,int r){
ll ans=0;
if(ql<=l&&r<=qr)
return tree[o];
pushdown(o,r-l+1);
if(ql<=mid) ans+=query(lson);
if(qr>mid)
ans+=query(rson);
return ans;
}
int main(){
int n,q;
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
while(q--){
char ch;
scanf(" %c%d%d",&ch,&ql,&qr);
if(ch=='Q')
printf("%lldn",query(1,1,n));
else{
scanf("%lld",&v);
updata(1,1,n);
}
}
}

最后

以上就是朴实大门为你收集整理的POJ3468(用lazy标记进行延迟更新)的全部内容，希望文章能够帮你解决POJ3468(用lazy标记进行延迟更新)所遇到的程序开发问题。

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