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

Автор NoTwo, история, 9 лет назад, По-английски

Hello,
I'm trying to solve 446C - DZY любит числа Фибоначчи and i can't debug my code. I'm simply using a segment tree to get the sums.I would really be happy if someone could tell me my mistakes.

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

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

I guess you misunderstood the problem, for each update you should do following from L to R: a[L] += f[L], a[L + 1] += f[L + 1] ... a[R] += f[R]

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

    nope it says for each l <= i <= r: a[i] += f[i-l+1] thus a[l] += f[1], a[l+1] += f[2], ..., a[r] += f[r-l+1]

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Ok, the wrong part is you add pf[q — p — 1] to all a[i] from l to r

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

        i tried pf[q-p] before, still wrong :(

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

          Yes, it must be wrong, you can not do updates correctly with this approach because every element doesn't get constant number and its correct solution isn't as simple as you think, try to look others code or tutorial to get the idea