POJ3468ASimpleProblemwithIntegers（线段树+区间修改，区间查询）

题意：

给出一段序列，两种操作。

Q L R ：查询【L,R】区间之和

C L R X ：将【L,R】区间中的每个数增加X

思路：

线段树模板题：区间修改+区间查询

lazy:懒标记

特别之处：增加push_down()

#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int maxn=100005;
struct node
{
ll l,r,sum,lazy;
void update(ll k)
{
sum+=(r-l+1)*k;
lazy+=k;
}
}tree[4*maxn];
ll n,m,a[maxn];
void push_up(ll id)
{
tree[id].sum=tree[id*2].sum+tree[id*2+1].sum;
}
void push_down(ll id)
{
if(tree[id].lazy)
{
tree[id*2].update(tree[id].lazy);
tree[id*2+1].update(tree[id].lazy);
tree[id].lazy=0;
}
}
void build(ll id,ll l,ll r)
{
tree[id].l=l;
tree[id].r=r;
if(l==r)
{
tree[id].sum=a[l];
return;
}
ll mid=l+(r-l)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
push_up(id);
}
void update(ll id,ll l,ll r,ll k)
{
ll L=tree[id].l,R=tree[id].r;
if(l<=L&&R<=r)
{
tree[id].update(k);
return;
}
if(l>R||r return;
push_down(id);
if(tree[id*2].r>=L)
{
update(id*2,l,r,k);
}
if(tree[id*2+1].l<=R)
{
update(id*2+1,l,r,k);
}
push_up(id);
}
ll query(ll id,ll l,ll r)
{
ll L=tree[id].l,R=tree[id].r;
if(l<=L&&R<=r)
{
return tree[id].sum;
}
if(l>R||r return 0;
push_down(id);
ll ans=0;
if(tree[id*2].r>=L)
{
ans+=query(id*2,l,r);
}
if(tree[id*2+1].l<=R)
{
ans+=query(id*2+1,l,r);
}
return ans;
}
int main()
{
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
char s[10];
ll x,y,k;
build(1,1,n);
while(m--)
{
scanf("%s",&s);
if(s[0]=='Q')
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",query(1,x,y));
}
else if(s[0]=='C')
{
scanf("%lld%lld%lld",&x,&y,&k);
update(1,x,y,k);
}
}
return 0;
}


• 
  
  点赞
  


• 
  
  收藏


• 
  
  分享


• 
  

  
  

  
  
  • 文章举报
  
  
  
  

AimerAimerAimer
发布了19 篇原创文章 · 获赞 0 · 访问量 176
私信

关注