C - A Simple Problem with Integers

本文主要是介绍C - A Simple Problem with Integers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://cn.vjudge.net/contest/269834#problem/C

题目大意：区间更新和区间查询。

题解：lazy算法，加线段树。

代码：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define inf 0x3f3f3f3f3f3fusing namespace std;struct node
{int l,r;long long num,lazy;
} s[1000000];long long  h[1000000];long long int creat(int t,int l,int r)//建树
{int mid=(l+r)>>1;if(l==r){s[t].l=l;s[t].r=r;s[t].lazy=0;return s[t].num=h[l];}s[t].l=l;s[t].r=r;s[t].lazy=0;return s[t].num=creat(t*2,l,mid)+creat(t*2+1,mid+1,r);
}void addre(int t,int l,int r,int e)//区间更新
{int mid=(s[t].l+s[t].r)>>1;if(s[t].l==l&&s[t].r==r){s[t].lazy+=e;return ;}s[t].num+=(r-l+1)*e;//这里是核心if(s[t].lazy!=0)//这里是核心{s[t*2+1].lazy+=s[t].lazy;s[t*2].lazy+=s[t].lazy;s[t].num+=(s[t].r-s[t].l+1)*s[t].lazy;s[t].lazy=0;}if(mid>=r){addre(t*2,l,r,e);}else if(mid<l){addre(t*2+1,l,r,e);}else{addre(t*2,l,mid,e);addre(t*2+1,mid+1,r,e);}
}long long  query(int t,int l,int r)//区间查询
{if(s[t].l==l&&s[t].r==r){return s[t].num+(s[t].r-s[t].l+1)*s[t].lazy;}int mid=(s[t].l+s[t].r)>>1;if(s[t].lazy!=0)//这里是核心{s[t*2+1].lazy+=s[t].lazy;s[t*2].lazy+=s[t].lazy;s[t].num+=(s[t].r-s[t].l+1)*s[t].lazy;s[t].lazy=0;}if(r<=mid){return query(t*2,l,r);}else if(l>mid){return query(t*2+1,l,r);}else{return query(t*2+1,mid+1,r)+query(t*2,l,mid);}
}int main()
{int a,b,c,d,e;char mm;while(~scanf("%d %d",&a,&b)){for(int i=1; i<=a; i++){scanf("%lld",&h[i]);}creat(1,1,a);for(int i=1; i<=b; i++){getchar();scanf("%c",&mm);if(mm=='C'){scanf("%d %d %d",&c,&d,&e);addre(1,c,d,e);}else if(mm=='Q'){scanf("%d %d",&c,&d);printf("%lld\n",query(1,c,d));}}}return 0;
}

 

这篇关于C - A Simple Problem with Integers的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---