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

How to solve a range query problem
Автор svg_af, история, 8 лет назад, По-английски

Hello there

I'm trying to solve this problem

I've thought alot about it and have no idea

Any clues would be appreciated

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

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

google static case, i.e. longest alternating subsequence problem. You will find several approaches, one of them is compatible with data structures like segment tree or sqrt decomposition. It's a bit tricky though

...ok, my submission received WA29, I believe it's just a minor bug, don't like these paperworks

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

    The approach being to count the number of peaks (ai - 1 < ai > ai + 1 or ai - 1 > ai < ai + 1).

    The real tricky part is dealing with groups of adjacent equal numbers, because you need to treat them as if they were a single number. I don't remember exactly how I did it, but I think it involved a few BITs to keep track of where each group starts. There's probably something simpler...

    EDIT: You should be able to do it with a single segment tree if you keep in each node whether the last change was increasing or decreasing (along with the number of peaks). Shouldn't have too many special cases. (Idea taken from desperado123)

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

      thanks a lot

      counting number of peaks never occurred to me ... will try to apply with a segment tree like you said

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

use binary indexed tree

→ Ответить