svg_af's blog

How to solve a range query problem
By svg_af, history, 9 years ago, In English

Hello there

I'm trying to solve this problem

I've thought alot about it and have no idea

Any clues would be appreciated

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

Comments Comments (4)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    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)

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

      thanks a lot

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

      → Reply
»
9 years ago, # |
  Vote: I like it -16 Vote: I do not like it

use binary indexed tree

→ Reply