nyan101's blog

How can I solve query problems like "count the number of different elements in [l, r]" on array?
By nyan101, history, 8 years ago, In English

sometimes I saw — unfortunately, I can't remember where I saw that — problems like below. I simplified the statement for clarity.

Problem)

You're given an array A with N elements, (A[0], A[1], ..., A[N-1]). and there are two kinds of queries

  • 1 x y : change A[x] to y

  • 2 l r : count the number of different elements in A[l], A[l+1], ..., A[r].

Condition)

  • 1<=N, Q<=100,000 (Q: total number of queries)

  • 1<=A[i]<=10^9 + 9 (A[i] : integer)

I tried to approach with segment tree but still have no idea.. How can I solve this kind of problems?

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

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

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

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

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

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

There is offline solution. Algorithm MO.

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

Mo's algorithm.

1 sort the query as follows.

(1) increasing order of l(i)/sqrt(N)

(2) if l(i)/sqrt(N) is same, increasing order of r(i)

2 start with L=R=0 and for each l(i), r(i)

(1) move L->l(i), R->r(i) and count.

(2) save the answer of the query.

total time complexity is O(Q log Q + N sqrt(N)).

→ Reply
»
8 years ago, # |
← Rev. 6   Vote: I like it +28 Vote: I do not like it

Other solutions here only solve offline version, but it's not enough since his problem has updates. I heard of a way to do Mo's algorithm with updates, but if I don't quite remember how to do it (and it certainly isn't explained in the other comments :P)

I will describe one way to solve this problem in time. First, compress all the elements in A and all the queries to the range 1, 2, 3, ..., N + Q.

Let's create an array B. Bi contains the first index j such that i < j and Ai = Aj, or ∞ if there is no such index. That is, it is the first index to the right which is equal to this element.

Now, also create N + Q BBSTs. The ith BBST should contain the indices of all the elements whose value is equal to i.

We should now create segment tree on B. If a node in the segment tree is responsible for the range [i, j], then it should contain a BBST with all the elements Bi, Bi + 1, Bi + 2, ..., Bj. Note that you cannot use C++ set for this, you must implement your own.

Now let's look at how to answer the queries.

  1. Change Ax to y. First, remove x from the set it was in (Ax). This results in changing the first element Bi to the left for which Ai = Ax. This is easy to do using the set. We need to change this to the index of the element to the right of x in the set Ax. Afterwards, we have to change Bx itself. Add x to the yth set it belongs to and then look for the first element to the right of it. In total, we change at most two elements in B. Update the corresponding segment tree.
  2. Given l and r, find the number of distinct elements in l and r. This problem reduces to finding the number of elements [l, r] which are greater than r (try to see this intuitively). This is easy to do using the segment tree, perform a search in all the relevant nodes.

You can try implementing it here: UVa 12345 — Dynamic len(set(a[L:R]))

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

    for the definition of array B, is the condition Bi = Bj ? instead of Ai=Aj? Thank you so much for the detail explanations

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

      Sorry, it's a typo. I've fixed it.

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

        uh... what about i>j and "it is the first index to the right ~". sorry but my English skill isn't enough so I'm confused between i>j and i <j. (is i <j right?)

        Edir: Nevermind. I got it

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

    You haven't used the N BBSTs in second query, right?

    If you need it in the first query to change Bx to the appropriate element (and also first index to the left of x which is equal to Ax), then it can also be done with a simple array, isn't it?

    So where are we using the N BBSTs?

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

      Yes, the BBSTs are only for the first query.

      I'm not quite sure how you can guarantee runtime per query using only a simple array. Maybe you can explain your approach for it, but I figured the BBSTs approach was the simplest. :)

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

    I heard of a way to do Mo's algorithm with updates

    Can someone please explain what this is? I haven't seen any way to do this myself. Wouldn't Mo's require a static array for processing queries offline? Thanks :)

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

      A red coder posted this as a comment a few months back. I have not implemented it myself and I don't really understand the idea behind it, but he is red, therefore he must be correct ;)

      The runtime is somewhere around O(N5 / 3), though, which is cutting it pretty close considering this probably has some constant factors. The benefit is that it can be used in other situations where Mo's algorithm is the only solution.

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

http://www.spoj.com/problems/DQUERY/

Simple version.

→ Reply