you can have this code for better understanding
#include<stdio.h>
long long v[500000];
long long a[500000];
inline long long getvalue( int index, int low, int high)
{
return a[index] + (high-low+1)*v[index];
}
long long update( long long index, long long down, long long up, long long
low, long long high,long long value)
{
long long mid = (low+high)/2;
if( down <= low && high <= up)
{v[index] += value;
return 0;
}
if(low> up || high < down)
return 0;
v[2*index] += v[index];
v[2*index+1] += v[index];
v[index] = 0;
update( 2*index, down,up, low,mid,value);
update(2*index+1 , down,up, mid+1, high,value);
a[index] = getvalue(2*index, low, mid) + getvalue(2*index+1 ,
mid+1,high);
return 0;
}
long long query( long long index, long long down, long long up, long long
low, long long high)
{
//printf("%lld %lld %lld %lld",low,high,up,down);
long long mid;
mid = (low+high)/2;
if( down <= low && high<=up)
return a[index] + v[index]*( high-low+1);
if( low > up || high < down)
return 0;
v[2*index] += v[index];
v[2*index+1] += v[index];
a[index] = getvalue(2*index, low, mid) + getvalue(2*index+1 ,
mid+1,high);
v[index] =0;
return query( 2*index,down,up, low, mid)+query(2*index+1, down,up,
mid+1, high);
}
int main()
{
long long t,n,p,quer,vr,val,i,q;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&quer);
for(i=0;i<=4*n;i++)
a[i] =0,v[i] =0;
while(quer--)
{
// for(i=1;i<8;i++)
//printf("%lld ",a[i]);
//printf("\n");
scanf("%lld%lld%lld",&vr,&p,&q);
if(!vr)
{scanf("%lld",&val);
update( 1,p,q,1,n,val);
}
else
printf("%lld\n",query( 1, p, q, 1, n));
}
//printf("bye");
}
return 0;
}
On Tue, Feb 26, 2013 at 12:24 PM, emmy <[email protected]> wrote:
> Problem statement <http://www.spoj.com/problems/HORRIBLE/>
>
> Here <http://ideone.com/NhDuYo> is my code. I am using segment trees +
> Lazy propagation. Please help me figure out my mistake.
> I am getting a WA
>
> Note:
> invariant : l <= p <=q <= r
>
> l and r are the limits of that node
> p and q is the query range.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
*Dheeraj Hasija*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
