POJ 3468 A Simple Problem with Integers （線段樹區間更新模闆題）

題目連結

POJ3468

題目大意

給N個數，Q個操作(1 ≤ N,Q ≤ 100000)

有兩種操作：

1.”C a b c”： Aa , Aa+1 , … , Ab 都加c

2.”Q a b”：求 Aa , Aa+1 , … , Ab 的和

分析

線段樹區間更新模闆題。

代碼

#include <iostream>
#include <cstring>
#include <string>
#define LL long long
using namespace std;
const int MAXN=;
LL a[MAXN],ans[MAXN<<],lazy[MAXN<<];

void PushUp(int rt)
{
    ans[rt]=ans[rt<<]+ans[rt<<|];
}
void Build(int l,int r,int rt)
{
    if (l==r)
    {
        ans[rt]=a[l];
        return;
    }
    int mid=(l+r)>>;
    Build(l,mid,rt<<);
    Build(mid+,r,rt<<|);
    PushUp(rt);
}
void PushDown(int rt,int ln,int rn)
{
    if (lazy[rt])
    {
        lazy[rt<<]+=lazy[rt];
        lazy[rt<<|]+=lazy[rt];
        ans[rt<<]+=lazy[rt]*ln;
        ans[rt<<|]+=lazy[rt]*rn;
        lazy[rt]=;
    }
}
void Update(int L,int R,int C,int l,int r,int rt)
{
    if (L<=l&&r<=R)
    {
        ans[rt]+=C*(r-l+);
        lazy[rt]+=C;
        return;
    }
    int mid=(l+r)>>;
    PushDown(rt,mid-l+,r-mid);
    if (L<=mid) Update(L,R,C,l,mid,rt<<);
    if (R>mid) Update(L,R,C,mid+,r,rt<<|);
    PushUp(rt);
}
LL Query(int L,int R,int l,int r,int rt)
{
    if (L<=l&&r<=R)
        return ans[rt];
    int mid=(l+r)>>;
    PushDown(rt,mid-l+,r-mid);
    LL ANS=;
    if (L<=mid) ANS+=Query(L,R,l,mid,rt<<);
    if (R>mid) ANS+=Query(L,R,mid+,r,rt<<|);
    return ANS;
}
int main()
{
    ios::sync_with_stdio(false);
    int n,q,i,x,y,z;
    string op;
    cin>>n>>q;
    for (i=;i<=n;i++)
        cin>>a[i];
    memset(ans,,sizeof(ans));
    memset(lazy,,sizeof(lazy));
    Build(,n,);
    while (q--)
    {
        cin>>op;
        if (op=="C")
        {
            cin>>x>>y>>z;
            Update(x,y,z,,n,);
        }
        if (op=="Q")
        {
            cin>>x>>y;
            cout<<Query(x,y,,n,)<<endl;
        }
    }
    return ;
}