FineLine's blog

Help Required In Timus Problem 1846
By FineLine, history, 8 years ago, In English

Hi everyone I have been trying to solve this problem for a lot of time Timus 1846()..I know that this is a problem of segment tree .Can anyone please help me regarding the same. REGARDS..

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

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

http://codeforces.net/blog/entry/3327

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

Initially, we will just read the input without processing it in order to apply coordinate compression. Now for every number in the input we know its position if all numbers are sorted. For example, if we have number 9,7,1,1,8,7, the position of 1 is 1, the position of 7 is 2, the position of 8 is 3 and the position of 9 is 4.

Notice that it only matters whether number X is in the set, not how many times it is actually present. So at any moment we can keep the number of occurences for each number. When the query is '+', we increase X's count and if it becomes 1, then we need to insert X into our data structure. When the query is '-', we decrease X's count and if it becomes 0, then we need to erase X from our data structure.

Now let's see how we will build our data structure. Say that P[X] is the position of X if the array is sorted (the thing we talked about in the first paragraph) and M is the maximum value of P[X] for some X. Then we can build segment tree over those positions (indices from 1 to M). Each node in the segment tree will store the GCD of its children and initially everything is set to zero. It's easy to see that the answer after performing each query will be stored in the root of the tree. When inserting a number X into our structure, we simply assign value X to index P[X] and when erasing a number X, we assign value 0 to index P[X].

Here is my code — http://ideone.com/uJ8ndT :)

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

    Thanks a lot P_Nyagolov :)

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Instead of compressing coordinates you can just store in map the vector of positions where you added alement X, and when you need to add element, you just put it in any (number of query, for example) position of segment tree, and when you need to remove element, peek the last number from map[X] and set that position in segment tree to zero. Note as well that this approach is online (if there's not enough space for new element, you can just build a bigger segment tree, in the same manner that vector expands itself in C++).

    //Treap also should work well for this problem, I think, though I don't know, would it fit in TL or not

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

Can It be done using square root decomposition also.. Regards.

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

    Yes, it's pretty much the same idea, just store the gcd for each block :)

    → Reply