Блог пользователя faiyaz26

Help on uva 12501 Bulky process of bulk reduction
Автор faiyaz26, 12 лет назад, По-английски

for this problem UVA 12501

How to solve this problem with segment tree ?

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    i have not understood your code!!

    can you give me the idea to solve the problem ?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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".

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.. :)

        → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится 
          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;
}
          → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

          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]

          → Ответить
          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      updated code

      → Ответить