VMaksimoski008's blog

LIS with segment tree on a mutable array
By VMaksimoski008, history, 12 months ago, In English

I already know how to compute the LIS of an array using a Segment Tree. I've read different materials from different sources

on how to do this, but I've never encountered how to find LIS when the array is muatble. For example, if the array was

[1, 3, 2, 10], then the leaf nodes in the Segment Tree would look like [1, 2, 2, 3].

But if we have a query (pos = 0, new_val = 12), the array would be [12, 3, 2, 10],

and the tree leaf nodes are going to be [1, 1, 1, 2].

Thanks in advance!

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

»
12 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Does anyone have an idea?

→ Reply
»
12 months ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

this problem >2600* bcz its strictly harder than 650D

but 650D's sol is useless for this problem

sry i cant solve it i will try tmr

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks

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

      I know which problem you are trying to solve :), it’s the same as zip-line just stolen and rewritten.

      → Reply