Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

faiyaz26's blog

Help on uva 12501 Bulky process of bulk reduction
By faiyaz26, 14 years ago, In English

for this problem UVA 12501

How to solve this problem with segment tree ?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
14 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

something like that. you need to test it, there can be a lot of bugs.

→ Reply
  • »
    »
    14 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    i have not understood your code!!

    can you give me the idea to solve the problem ?

    → Reply
    • »
      »
      »
      14 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      all what you need to solve the problem: 1) you need to know how to combine segments. you can find this in my code
      2) google "lazy propagation segment tree".

      → Reply
      • »
        »
        »
        »
        14 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it

        i am not new to segment tree..

        I just want to know how to query for this problem. how to combine ? for this interval: [2,5] how to give the ans like this 1*a[2]+2*a[3]+3*a[4]+4*a[5]

        btw thanks for the help so far.. :)

        → Reply
        • »
          »
          »
          »
          »
          14 years ago, hide # ^ |
          ← Rev. 2  
          Vote: I like it +1 Vote: I do not like it 
          const TSegment operator + (const TSegment& d) const {
    TSegment res;
    res.toadd = 0;
    res.len = len + d.len;
    res.sum = Sum() + d.Sum();
    res.ansVal = AnsVal() + d.AnsVal() + len * d.Sum();
    return res;
}
          → Reply
        • »
          »
          »
          »
          »
          14 years ago, hide # ^ |
          ← Rev. 2  
          Vote: I like it +1 Vote: I do not like it

          let's divide interval [2, 5] into [2, 3] and [4, 5]
          1*a[2]+2*a[3]+3*a[4]+4*a[5] = 1*a[2]+2*a[3]+ 2*(a[4]+a[5]) +1*a[4]+2*a[5]

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            I didn't think of that! Thank you very much for the insight :)

            → Reply
    • »
      »
      »
      14 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      updated code

      → Reply