prodipdatta7's blog

By prodipdatta7, 5 years ago, In English

How can I solve this problem? Any kind of help regarding this problem will be appreciated.

The abridged problem is:
Given a sequence of numbers. You have to perform 3 types of queries.

1 V: Add V to the end of the sequence.
2: remove an element from the end of the sequence.
3 l r: Find the K'th largest number in the range.
`

It is guaranteed that 1 <= l <= r <= the total number of elements in the current sequence.
Problem link

  • Vote: I like it
  • -2
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

you can use persistence segment tree.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use Merge Sort Tree.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

May be there are other solutions, but there is a relatively new and less used data structure called Wavelet Tree that supports all of these operations. I don't know how easy it is to use because I haven't implemented it yet. But if you are interested you can read about it in this IOI journal.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Interesting, I have never seen updates on wavelet trees.