Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

dotpie's blog

data structure problem
By dotpie, 9 years ago, In English

hello all, I wish to know how I solve this problem = link

The problem asks to count number of distinct elements in a range for many query. There can be also modification of single element. Is any online solution exist? Maybe with implicit cartesian tree? Pls help.

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

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

sorry wrong

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

  1. Let's pretend that there are no updates. In this case, it is a well-known problem. We can solve it offline using a BIT in O((n + m) log n) time(I can elaborate on it if necessary).

  2. Here is the trick: we will not really do any updates. Instead, we will process queries in batches of size B(let's choose B = sqrt(N)).

  3. For each batch, we can do the following:

    • Ignore all numbers that are involved in any update in this batch(let's call them special). For the rest of the elements the solution is described in 1.
    • There are at most 2 * B special numbers per batch. We can handle them naively(by maintaining a set of all occurrences).

The time complexity is O(N / B * N * log N)(for non-special numbers) + O(B * N * log n)(for special ones) = O(N * sqrt(N) * log(N))(I assume that N = M to keep it simple). It is fast enough to get accepted. Here is my code.

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

    I think Mo's Algorithm would also work for offline one. Can you please elaborate the solution with BIT?

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

      Let's iterate over the array from left to right. If the current element occurs for the first time, we simply add one to this position in the BIT. Otherwise, we also need to subtract one from the position of its last previous occurrence. After adding the i-th element, we can answer all the queries which have r = i(the answer is simply a sum of the [l, r] range). Mo's algorithm has an O(N * sqrt(N)) time complexity, so it is not feasible in this case because the total time complexity will be O(N^2), which seems to be too much(I haven't tried it, though).

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

        Why is it O(n^2)? What do you mean by saying total?

        UPD: Btw, thank you for clear explanation.

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

          To handle updates, we divide queries into blocks of size sqrt(N). Then we solve the problem for each block separately. If we use Mo's algorithm, we get an sqrt-decomposition inside an sqrt-decomposition. It's pretty bad. To be more precise, the term O(N / B * N * log N) becomes O(N / B * N * sqrt(N)) = O(N^2).

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

            You were talking about the one with the updates. I see now.

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

      BIT SOLUTION Can you please explain How this is to be done using MO's algo

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

    thank you very much. that was very helpful. I still wonder can there exist an nlogn or faster solution?

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

A funny fact: a naive O(N * M) solution gets accepted.

→ Reply