Блог пользователя Code_sprinter

Автор Code_sprinter, история, 4 года назад, По-английски

hello everyone,

Recently i came across this problem http://www.spoj.com/problems/DQUERY/en/. I solved the problem using Mo's algo and BST which is basically offline solution. Is there a way I can solve for each query online (and similarly for trees that involves queries on the subtree of its nodes)? If yes, please help me out.

Thanks in advance!!

  • Проголосовать: нравится
  • -24
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Code_sprinter (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

You can use merge Sort Tree to solve this problems. Here you can see sample code of merger sort tree

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

You could use a BIT (segment or fenwick tree) of size 1e6 and update the positions of the a[i] setting that to 1. Then query the range will tell the number of distinct elements.

Edit: But more simple would be to use prefix sums on an array of size 1e6.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    I didn't get how you gonna solve query with that.

    Can you please elaborate a bit on how to get answer for any given l and r using segment or fenwick tree?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -6 Проголосовать: не нравится

      Well, a simple BIT returns the sum of elements in the query range. Since the values of a[] are limited to 1e6, we use a BIT of size 1e6.

      Then set the values in the BIT at positions of all a[i] to 1. Note that if two a[i] are same, we maybe twice set the value at position a[i] to 1. We could implement this update as query of that position, and only update if it is 0.

      Then the query of a range l,r will return the sum of the numbers in that range. Since the sum of the ones equals the number of the ones, it is the number of distinct elements.

      But as written, doing the same on a prefix sum array would be simpler. I was irritated by the meaning of offline.

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

What an interesting coincidence!! Codechef has a very similar problem : https://www.codechef.com/JUNE20A/problems/DIFVAL

Please wait a few days more for contest to get over and you can read the editorial.

Feel free to research on your own till then, but please refrain asking someone about it since other contestants might get solution without working for it.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

You can use persistent data structures like persistent segment tree

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Yes! You can use Persistent Segment Tree for online answering to queries.

    You need to keep roots of versions and last positions for each value.

    1. Preprocessing:

        For each position i:
          - if we meet a[i] for first time, add 1 to position i
          - else add -1 to position of last a[i] and add 1 to current position
    

    2. Answering to queries

        Query: Left, Right
    
        We take sum from position Left to Right from version of Right position. Sum of ones in this segment will an answer for current query.
    
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Exactly

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Could u elaborate again, I could not understand the above explanation.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Alright. Firstly, you need to know using Persistent Segment Tree (update, etc.). Secondly, you need to keep only roots of updated versions in versions array. Thirdly, as I said above you should put 1 only in last seen position of current value (it means, keep positions in array last and do 0-1 update on positions). Fourthly, because of updating last position in r, we take answer from version[r] between l and r.

        Also, you may see my solution for better understanding.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          thanks, that means each query can be answered in logn time online which is better than using merge sort tree where it takes (logn)^2 for each query.