c++ - 怠惰な伝播 - 恐ろしい話

Question

私は 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;
}

提供されたサンプル テストケースは、私のコードで正しい回答を提供しますが、送信すると、間違った回答メッセージが表示されます。コードを何度もチェックしましたが、バグが見つかりません。

どんな助けでも大歓迎です。ありがとう！