raihatneloy's blog

Help needed in a Data Structure Problem
By raihatneloy, history, 9 years ago, In English

How to solve this problem? I tried a lot of ideas. I used here: 1. Segment tree in every node of segment tree (Gives MLE) 2. Segment Tree in every node of BIT (gives MLE) 3. Avl tree in every node of segment tree (gives TLE) 4. Splay tree in every node of segment tree (gives TLE)

Please, help needed. :( I want to solve this prpblem

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

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

Help needed please :'(

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

Use sqrt-decomposition

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

Use persistent segment tree--first see MKTHNUM on SPOJ. It's a fairly popular problem so there are numerous solutions online. MKTHNUM doesn't have update value queries, but this is also easily implemented with persistent segtrees--just decrement the frequency of the old number, and then increment the frequency of the new number. Both types of queries are log n time.

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

    But in persistent seg-tree, the values of later trees depend on previous. For example: Suppose the trees are at index 1,2,3,4,5,6 Now if i change the frequency of index 3, then the value for 4,5,6 should also be changed, how to handle this? i have no idea about handling this factor. Can you please explain a little bit?

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

This problem comes from 2015 Multi-University Training Contest 10. And you can find the solution here.

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

    Thanks a lot :) :) I got AC, using BST (Both AVL & Treap) in every node of BIT after seeing your link. Thanks for your help.

    → Reply