c++ - 惰性传播 - 可怕的 spoj

Question

我正在尝试来自 spoj 的可怕问题，这里是链接: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;
}

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

感谢任何帮助。谢谢!

Answer 1

我能看到的一个错误是 在更新函数中

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