2

我正在尝试来自 spoj 的 HORRIBLE 问题，这是链接：http ://www.spoj.com/problems/HORRIBLE/我正在尝试用分段树自学惰性传播。以下是我编写的代码，我尽量使其简洁明了，如果有不清楚的地方请告诉我。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

ll tree[500010];
ll lazy[500010]={};

void buildST(ll A[], ll STidx, ll l, ll r)
{
    if(l==r)
    {
        tree[STidx]=A[l];
        return;
    }
    ll left=2*STidx, right=left+1, mid=(l+r)/2;
    buildST(A, left, l, mid);
    buildST(A, right, mid+1, r);
    tree[STidx]=tree[left]+tree[right];
}

void update(ll STidx, ll i, ll j, ll l, ll r, ll val)
{
    //printf("%lld %lld %lld %lld %lld\n", STidx, i, j, l, r);
    if(lazy[STidx]!=0)
    {
        tree[STidx]+=(l-r+1)*lazy[STidx];
        if(l!=r)
        {
            lazy[2*STidx]+=lazy[STidx];
            lazy[2*STidx+1]+=lazy[STidx];
        }
        lazy[STidx]=0;
    }
    //printf("1\n");
    if(l>r || l>j || r<i)
        return;
    //printf("1\n");
    if(l>=i && r<=j)
    {
        //printf("%lld\n", STidx);
        tree[STidx]+=(r-l+1)*val;
        if(l!=r)
        {
            lazy[2*STidx]+=val;
            lazy[2*STidx+1]+=val;
        }
        return;
    }
    ll mid=(l+r)/2;
    update(2*STidx, i, j, l, mid, val);
    update(2*STidx+1, i, j, mid+1, r, val);
    tree[STidx]=tree[2*STidx]+tree[2*STidx+1];
}

ll query(ll STidx, ll i, ll j, ll l, ll r)
{
    if(lazy[STidx]!=0)
    {
        tree[STidx]+=lazy[STidx]*(r-l+1);
        if(l!=r)
        {
            lazy[2*STidx]+=lazy[STidx];
            lazy[2*STidx+1]+=lazy[STidx];
        }
        lazy[STidx]=0;
    }
    if(l>r || l>j || r<i)
        return 0;
    if(l>=i && r<=j)
        return tree[STidx];
    ll mid=(l+r)/2;
    ll q1=query(2*STidx, i, j, l, mid);
    ll q2=query(2*STidx+1, i, j, mid+1, r);
    return q1+q2;
}

ll A[100010];

int main()
{
    ll T, N, C, type, p, q, v, i;
    scanf("%lld", &T);
    while(T--)
    {
        scanf(" %lld %lld", &N, &C);
        for(i=0; i<N; ++i)
            A[i]=0;
        for(i=0; i<4*N; ++i)
            lazy[i]=0;
        buildST(A, 1, 0, N-1);
        while(C--)
        {
            scanf(" %lld", &type);
            if(type==0)
            {
                scanf(" %lld %lld %lld", &p, &q, &v);
                update(1, p-1, q-1, 0, N-1, v);
                //for(i=1; i<=15; ++i)
                //  printf("%lld ", tree[i]);
                //printf("\n"); 
            }
            if(type==1)
            {
                scanf(" %lld %lld", &p, &q);
                printf("%lld\n", query(1, p-1, q-1, 0, N-1));
            }
        }
    }
    return 0;
}

提供的示例测试用例用我的代码给出了正确的答案，但是在提交时，我收到了错误的答案消息。我已经检查了很多次我的代码，但我找不到错误。

任何帮助表示赞赏。谢谢！

4

1 回答 1

0

我可以看到的错误之一是在更新功能中

而不是tree[STidx]+=(l-r+1)*lazy[STidx]; 它应该是tree[STidx]+=(r-l+1)*lazy[STidx];

于 2015-07-24T15:11:33.153 回答