pikkupr's blog

Spoj: D-query
By pikkupr, history, 9 years ago, In English

Problem link: http://www.spoj.com/problems/DQUERY/en/

I was maintaining a map<int,int> for each node in the tree. Nd I'm getting WA with this approach. Plz help me fix this.

Solution link: http://ideone.com/1CcC8d

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

Comments Comments (7)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The easiest way to solve this problem is with square root decomposition. Divide the array into blocks of size , then sort the queries first by the block of the left end and then by ascending right end. The left pointer will move at most times for each query and the right pointer will move at most N times for each block, so total complexity is in the order of .

Since numbers are at most one million, you can keep track of how many elements you have in the current window with a simple array count[i]. Every time count[i] becomes zero, you have one less element and every time it becomes one with an increase operation, you have one more element.

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

    I don't agree with you!

    The easiest way to solve this problem is with Segment Tree.

    You can use persistent-segment-tree to solve this task online, or you can remember all queries and solve it offline, using standart segment tree.

    I solved this task in January. Here is my code.

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

      Do you really think segment tree is simpler?

      Take a look at the code of sqrt-decomposition: SQRT-Dec C++ Code

      If you think your code is simpler than that then we have really different perceptions of what's simple and what's not.

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

        Well, I think, my code is simpler than yours :) Also it's online.

        Here it is: #FUYCFc

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

          That's a really nice implementation of persistent segment tree. Good job!

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

          can you explain how u did it using persistent segment tree.I understand that we keep segment trees for every prefix, and for every prefix i we can generate the new segment tree by chaning log(n) nodes of prefix(i-1).But how are we calculating the number of distinct elements in the sement [l,r]?

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

            One way to do it:

            The idea is to keep only the last occurrence of each number in each prefix

            Let root[i] be the ith root/segment tree and corresponds to the prefix [0, i]

            How to get root[i + 1]?

            Let the (i + 1)th number in original array be X, if it isn't the first occurrence of X, update segment tree and make the number at the index of previous X = (0) and value at current index(i+1) = (1), otherwise just make the value at current index = (1)

            To answer query [l, r] do range sum query on (r)th root over the same range [l, r]

            This way each number will be counted only once, and since we are keeping only last occurrence, the answer for any [?, r] is present after processing root[r]

            In other words, you may reorder the queries by their right end point in ascending order and use a normal segment/bit tree to answer queries offline

            → Reply