Hello everyone, I'm trying to solve the problem http://www.spoj.com/problems/HORRIBLE/, I solved using BIT, but I'm learning about Lazy Propagation and I want to solve using this. I did a code but it is getting WA, and I don't know why. Anyone can help me ?
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef vector<lli> vl;
class SegmentTree
{
private:
vl st, lazy, A;
int n;
int left(int p) { return p << 1; }
int right(int p) { return (p << 1) + 1; }
lli rsq(int p, int L, int R, int i, int j)
{
if(lazy[p] != 0)
{
st[p] += (R - L + 1) * lazy[p]; //RMQ = st[p] += lazy[
if(L != R)
{
lazy[left(p)] += lazy[p];
lazy[right(p)] += lazy[p];
}
lazy[p] = 0;
}
if(i > R || j < L || R < L) return 0LL;
if(L >= i && R <= j) return st[p];
return rsq(left(p), L, (L + R) / 2, i, j) + rsq(right(p), (L + R) / 2 + 1, R, i, j);
}
void updateRange(int p, int L, int R, int i, int j, int newValue)
{
if(lazy[p] != 0)
{
st[p] += (R - L + 1) * lazy[p]; //RMQ = st[p] += lazy[p];
if(L != R)
{
lazy[left(p)] += lazy[p];
lazy[right(p)] += lazy[p];
}
lazy[p] = 0;
}
if(L > R || L > j || R < i)
return;
if(L >= i && R <= j)
{
st[p] += (R - L + 1) * newValue; //RMQ = st[p] += value;
if(L != R)
{
lazy[left(p)] += newValue;
lazy[right(p)] += newValue;
}
return;
}
updateRange(left(p), L, (L + R) / 2, i, j, newValue);
updateRange(right(p), (L + R) / 2 + 1, R, i, j, newValue);
st[p] = st[left(p)] + st[right(p)];
}
public:
SegmentTree(int _n)
{
n = _n;
st.assign(4 * n, 0);
lazy.assign(4 * n, 0);
}
lli rsq(int i, int j)
{
return rsq(1, 0, n - 1, i, j);
}
void updateRange(int i, int j, int newValue)
{
updateRange(1, 0, n - 1, i, j, newValue);
}
};
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int n, c;
scanf("%d %d", &n, &c);
SegmentTree st(n);
int x, p, q, v;
while(c--)
{
scanf("%d %d %d", &x, &p, &q);
if(x == 1)
printf("%lld\n", st.rsq(p - 1, q - 1));
else
{
scanf("%d", &v);
st.updateRange(p - 1, q - 1, v);
}
}
}
return 0;
}
lazy update is wrong. it should be like this : lazy[L(p)] += value*(mid — left_index + 1); because the update query contains the whole range update not just a single value
I didn't understand, my mistake is here ?
My code was based on this: http://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/ Is it wrong too ?
Solved it using the link. here's the AC code : http://ideone.com/kTHEpl Sorry I made a mistake. You can either Here's how I did it : http://ideone.com/nBUWgZ The only change in my code is that in my lazy update I'm updating the lazyval as the sum of subtree i.e : lazy[L] += ( lazy[stIndex]/(p.S — p.F + 1) )*(mid — p.F + 1); and icrementing the tree value by the lazy node i.e. tree[i] += lazy[i];
Thank's, my mistake was: Overflow, I changed my variables to long long and acc.
Nope, as far as I understood lazy stores value to be added not sum of subtree.
Here is my awful code.
Thank you, but you know where is my mistake ?