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 <foramlakh...@gmail.com> 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 algogeeks+unsubscr...@googlegroups.com.
> 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 algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
