即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

POJ – 3468 A Simple Problem with Integers(线段树 区间更新 区间查询)

编程语言 m0_37253730 95℃ 0评论

POJ – 3468 http://poj.org/problem?id=3468


思路:区间更新+区间查询 注意tag也是ll的。


代码:

#include 
#include 
#include 
#include 

using namespace std;
#define ll long long
const int maxn = 1e5+10;
int d[maxn];
struct node
{
    int l,r,len;
    ll v,tag;
}tr[maxn<<2];
void reset(int id,int l,int r)
{
    tr[id].l = l ; tr[id].r = r; tr[id].len = r-l+1;
    tr[id].v = 0 ; tr[id].tag = 0;
}
ll build(int l,int r,int id)
{
    reset(id,l,r);
    if(l == r)  return tr[id].v = d[l];
    int mid =  l+r>>1;
    build(l,mid,id<<1);
    build(mid+1,r,id<<1|1);

    return tr[id].v = tr[id<<1].v + tr[id<<1|1].v;
}
void chtag(int id,ll tag)
{
    tr[id].tag += tag;
    tr[id].v += tag*tr[id].len;
}
void push(ll tag,int id)
{
    if(tag)
    {
        chtag(id<<1,tag);
        chtag(id<<1|1,tag);
        tr[id].tag = 0;
    }
}
ll add(int al,int ar,int c,int id)
{
    int l = tr[id].l, r = tr[id].r;
    if(r < al || l > ar) return 0;
    if(l >= al && r <= ar)
        { tr[id].tag += c; return tr[id].v += c*(tr[id].len); }
    push(tr[id].tag,id);
    int mid = l+r>>1;
    add(al,ar,c,id<<1);
    add(al,ar,c,id<<1|1);
    return tr[id].v = tr[id<<1].v + tr[id<<1|1].v;
}
ll query(int ql, int qr, int id)
{
    int l = tr[id].l,  r = tr[id].r;

    if(qr < l || ql > r) return 0;
    if(l >= ql && r <= qr)  return tr[id].v;

    push(tr[id].tag,id);
    int mid = l+r>>1;
    ll ans = 0;
    if(ql <= mid)  ans += query(ql,qr,id<<1);
    if(qr > mid) ans += query(ql,qr,id<<1|1);
    return ans;
}
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i = 1; i <= n; i++)
        scanf("%d",&d[i]);
    build(1,n,1);
    for(int i = 1; i <= q; i++)
    {
        char s[3]; int a,b,c;
        scanf("%s%d%d",s,&a,&b);
        if(s[0] == 'Q')
            printf("%lld\n",query(a,b,1));
        else
        {
            scanf("%d",&c);
            add(a,b,c,1);
        }
    }
    return 0;
}

转载请注明:CodingBlog » POJ – 3468 A Simple Problem with Integers(线段树 区间更新 区间查询)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情