Duarte's blog

By Duarte, history, 9 years ago, In English

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; }
  • Vote: I like it
  • -2
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't understand, my mistake is here ?

    if(L != R)
    {
       lazy[left(p)] += newValue;
       lazy[right(p)] += newValue;
    }
    

    My code was based on this: http://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/ Is it wrong too ?

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      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];

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank's, my mistake was: Overflow, I changed my variables to long long and acc.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nope, as far as I understood lazy stores value to be added not sum of subtree.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is my awful code.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you, but you know where is my mistake ?